Saya punya tabel seperti ini:

CREATE TABLE products (
  id serial PRIMARY KEY, 
  category_ids integer[],
  published boolean NOT NULL,
  score integer NOT NULL,
  title varchar NOT NULL);

Suatu produk dapat menjadi bagian dari banyak kategori. category_idsKolom berisi daftar id dari semua kategori produk.

Kueri umum terlihat seperti ini (selalu mencari kategori tunggal):

SELECT * FROM products WHERE published
  AND category_ids @> ARRAY[23465]
ORDER BY score DESC, title
LIMIT 20 OFFSET 8000;

Untuk mempercepatnya saya menggunakan indeks berikut:

CREATE INDEX idx_test1 ON products
  USING GIN (category_ids gin__int_ops) WHERE published;

Yang satu ini sangat membantu kecuali ada terlalu banyak produk dalam satu kategori. Dengan cepat menyaring produk yang termasuk dalam kategori itu tetapi kemudian ada semacam operasi yang harus dilakukan dengan cara yang sulit (tanpa indeks).

btree_ginEkstensi yang sudah diinstal memungkinkan saya membuat indeks GIN multi-kolom seperti ini:

CREATE INDEX idx_test2 ON products USING GIN (
  category_ids gin__int_ops, score, title) WHERE published;

Tetapi Postgres tidak ingin menggunakannya untuk menyortir . Bahkan ketika saya menghapus DESCspecifier dalam kueri.

Setiap pendekatan alternatif untuk mengoptimalkan tugas sangat disambut.

Informasi tambahan:

• PostgreSQL 9.4, dengan ekstensi intarray
• total jumlah produk saat ini adalah 260 ribu tetapi diperkirakan akan tumbuh secara signifikan (hingga 10 juta, ini adalah platform multi-tenant e-commerce)
• produk per kategori 1..10000 (dapat tumbuh hingga 100rb), rata-rata di bawah 100 tetapi kategori-kategori dengan sejumlah besar produk cenderung menarik lebih banyak permintaan

Rencana kueri berikut diperoleh dari sistem pengujian yang lebih kecil (4680 produk dalam kategori yang dipilih, total produk 200k dalam tabel):

Limit  (cost=948.99..948.99 rows=1 width=72) (actual time=82.330..82.341 rows=20 loops=1)
  ->  Sort  (cost=948.37..948.99 rows=245 width=72) (actual time=80.231..81.337 rows=4020 loops=1)
        Sort Key: score, title
        Sort Method: quicksort  Memory: 928kB
        ->  Bitmap Heap Scan on products  (cost=13.90..938.65 rows=245 width=72) (actual time=1.919..16.044 rows=4680 loops=1)
              Recheck Cond: ((category_ids @> '{292844}'::integer[]) AND published)
              Heap Blocks: exact=3441
              ->  Bitmap Index Scan on idx_test2  (cost=0.00..13.84 rows=245 width=0) (actual time=1.185..1.185 rows=4680 loops=1)
                    Index Cond: (category_ids @> '{292844}'::integer[])
Planning time: 0.202 ms
Execution time: 82.404 ms

Catatan # 1 : 82 ms mungkin tidak terlihat menakutkan tapi itu karena penyortir semacam cocok ke dalam memori. Setelah saya memilih semua kolom dari tabel produk ( SELECT * FROM ...dan dalam kehidupan nyata ada sekitar 60 kolom) ia pergi ke Sort Method: external merge Disk: 5696kBmenggandakan waktu eksekusi. Dan itu hanya untuk 4680 produk.

Poin tindakan # 1 (berasal dari Catatan # 1): Untuk mengurangi jejak memori operasi sortir dan karenanya mempercepatnya sedikit akan lebih bijaksana untuk mengambil, mengurutkan dan membatasi id produk pertama, kemudian mengambil catatan penuh:

SELECT * FROM products WHERE id IN (
  SELECT id FROM products WHERE published AND category_ids @> ARRAY[23465]
  ORDER BY score DESC, title LIMIT 20 OFFSET 8000
) ORDER BY score DESC, title;

Ini membawa kita kembali ke Sort Method: quicksort Memory: 903kBdan ~ 80 ms untuk 4680 produk. Masih bisa lambat ketika jumlah produk tumbuh hingga 100 ribu.

Saya telah melakukan banyak percobaan dan inilah temuan saya.

GIN dan sortir

Indeks GIN saat ini (pada versi 9.4) tidak dapat membantu pemesanan .

Dari jenis indeks yang saat ini didukung oleh PostgreSQL, hanya B-tree yang dapat menghasilkan keluaran yang diurutkan - jenis indeks lainnya mengembalikan baris yang cocok dalam urutan yang tidak ditentukan, tergantung pada implementasi.

work_mem

Terima kasih Chris telah menunjukkan parameter konfigurasi ini . Ini default ke 4MB, dan dalam hal recordset Anda lebih besar, meningkatkan work_memke nilai yang tepat (dapat ditemukan dari EXPLAIN ANALYSE) dapat secara signifikan mempercepat operasi sortir.

ALTER SYSTEM SET work_mem TO '32MB';

Mulai ulang server agar perubahan diterapkan, lalu periksa kembali:

SHOW work_mem;

Permintaan asli

Saya telah mengisi basis data saya dengan produk 650k dengan beberapa kategori menampung hingga produk 40k. Saya sedikit menyederhanakan kueri dengan menghapus publishedklausa:

SELECT * FROM products WHERE category_ids @> ARRAY [248688]
ORDER BY score DESC, title LIMIT 10 OFFSET 30000;

Limit  (cost=2435.62..2435.62 rows=1 width=1390) (actual time=1141.254..1141.256 rows=10 loops=1)
  ->  Sort  (cost=2434.00..2435.62 rows=646 width=1390) (actual time=1115.706..1140.513 rows=30010 loops=1)
        Sort Key: score, title
        Sort Method: external merge  Disk: 29656kB
        ->  Bitmap Heap Scan on products  (cost=17.01..2403.85 rows=646 width=1390) (actual time=11.831..25.646 rows=41666 loops=1)
              Recheck Cond: (category_ids @> '{248688}'::integer[])
              Heap Blocks: exact=6471
              ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=10.140..10.140 rows=41666 loops=1)
                    Index Cond: (category_ids @> '{248688}'::integer[])
Planning time: 0.288 ms
Execution time: 1146.322 ms

Seperti yang bisa kita lihat work_memtidak cukup jadi kita punya Sort Method: external merge Disk: 29656kB(angka di sini adalah perkiraan, perlu sedikit lebih dari 32MB untuk memori cepat di memori).

Kurangi jejak memori

Jangan pilih catatan lengkap untuk disortir, gunakan id, terapkan sortir, offset dan batas, lalu muat hanya 10 catatan yang kita butuhkan:

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000
) ORDER BY score DESC, title;

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=707.861..707.862 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=707.764..707.803 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=707.744..707.746 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=707.732..707.734 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=704.163..706.955 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.587..35.076 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.883..9.883 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.682 ms
Execution time: 707.973 ms

Catatan Sort Method: quicksort Memory: 7396kB. Hasilnya jauh lebih baik.

GABUNG dan indeks B-tree tambahan

Seperti yang disarankan Chris, saya telah membuat indeks tambahan:

CREATE INDEX idx_test7 ON products (score DESC, title);

Pertama saya mencoba bergabung seperti ini:

SELECT * FROM products NATURAL JOIN
  (SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000) c
ORDER BY score DESC, title;

Paket kueri sedikit berbeda tetapi hasilnya sama:

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=700.747..700.747 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=700.651..700.690 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=700.630..700.630 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=700.619..700.619 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=697.304..699.868 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=10.796..32.258 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.234..9.234 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 1.015 ms
Execution time: 700.918 ms

Bermain dengan berbagai offset dan jumlah produk saya tidak bisa membuat PostgreSQL menggunakan indeks B-tree tambahan.

Jadi saya pergi cara klasik dan membuat tabel persimpangan :

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id FROM products;
CREATE INDEX idx_prodcats_cat_prod_id ON prodcats (category_id, product_id);

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 30000;

Limit  (cost=122480.06..122480.09 rows=10 width=1390) (actual time=1290.360..1290.362 rows=10 loops=1)
  ->  Sort  (cost=122405.06..122509.00 rows=41574 width=1390) (actual time=1264.250..1289.575 rows=30010 loops=1)
        Sort Key: p.score, p.title
        Sort Method: external merge  Disk: 29656kB
        ->  Merge Join  (cost=50.46..94061.13 rows=41574 width=1390) (actual time=117.746..182.048 rows=41666 loops=1)
              Merge Cond: (p.id = c.product_id)
              ->  Index Scan using products_pkey on products p  (cost=0.42..90738.43 rows=646067 width=1390) (actual time=0.034..116.313 rows=210283 loops=1)
              ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..1187.98 rows=41574 width=4) (actual time=0.022..7.137 rows=41666 loops=1)
                    Index Cond: (category_id = 248688)
                    Heap Fetches: 0
Planning time: 0.873 ms
Execution time: 1294.826 ms

Masih tidak menggunakan indeks B-tree, resultset tidak cocok work_mem, karenanya hasilnya buruk.

Tetapi dalam beberapa keadaan, memiliki sejumlah besar produk dan offset kecil PostgreSQL sekarang memutuskan untuk menggunakan indeks B-tree:

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 300;

Limit  (cost=3986.65..4119.51 rows=10 width=1390) (actual time=264.176..264.574 rows=10 loops=1)
  ->  Nested Loop  (cost=0.98..552334.77 rows=41574 width=1390) (actual time=250.378..264.558 rows=310 loops=1)
        ->  Index Scan using idx_test7 on products p  (cost=0.55..194665.62 rows=646067 width=1390) (actual time=0.030..83.026 rows=108037 loops=1)
        ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..0.54 rows=1 width=4) (actual time=0.001..0.001 rows=0 loops=108037)
              Index Cond: ((category_id = 248688) AND (product_id = p.id))
              Heap Fetches: 0
Planning time: 0.585 ms
Execution time: 264.664 ms

Ini sebenarnya cukup logis karena indeks B-tree di sini tidak menghasilkan hasil langsung, hanya digunakan sebagai panduan untuk pemindaian sekuensial.

Mari kita bandingkan dengan permintaan GIN:

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 300
) ORDER BY score DESC, title;

Sort  (cost=2519.53..2519.55 rows=10 width=1390) (actual time=143.809..143.809 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2435.14..2519.36 rows=10 width=1390) (actual time=143.693..143.736 rows=10 loops=1)
        ->  HashAggregate  (cost=2434.71..2434.81 rows=10 width=4) (actual time=143.678..143.680 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2434.56..2434.59 rows=10 width=72) (actual time=143.668..143.670 rows=10 loops=1)
                    ->  Sort  (cost=2433.81..2435.43 rows=646 width=72) (actual time=143.642..143.653 rows=310 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: top-N heapsort  Memory: 68kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.625..31.868 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.916..9.916 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.630 ms
Execution time: 143.921 ms

Hasil GIN jauh lebih baik. Saya memeriksa dengan berbagai kombinasi jumlah produk dan mengimbangi, dalam keadaan apa pun pendekatan tabel persimpangan tidak lebih baik .

Kekuatan indeks nyata

Agar PostgreSQL dapat sepenuhnya menggunakan indeks untuk menyortir, semua WHEREparameter kueri dan juga ORDER BYparameter harus berada dalam indeks B-tree tunggal. Untuk melakukan ini, saya telah menyalin bidang sortir dari produk ke tabel persimpangan:

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id, score, title FROM products;
CREATE INDEX idx_prodcats_1 ON prodcats (category_id, score DESC, title, product_id);

SELECT * FROM products WHERE id in (SELECT product_id FROM prodcats WHERE category_id=248688 ORDER BY score DESC, title LIMIT 10 OFFSET 30000) ORDER BY score DESC, title;

Sort  (cost=2149.65..2149.67 rows=10 width=1390) (actual time=7.011..7.011 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2065.26..2149.48 rows=10 width=1390) (actual time=6.916..6.950 rows=10 loops=1)
        ->  HashAggregate  (cost=2064.83..2064.93 rows=10 width=4) (actual time=6.902..6.904 rows=10 loops=1)
              Group Key: prodcats.product_id
              ->  Limit  (cost=2064.02..2064.71 rows=10 width=74) (actual time=6.893..6.895 rows=10 loops=1)
                    ->  Index Only Scan using idx_prodcats_1 on prodcats  (cost=0.56..2860.10 rows=41574 width=74) (actual time=0.010..6.173 rows=30010 loops=1)
                          Index Cond: (category_id = 248688)
                          Heap Fetches: 0
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.003..0.003 rows=1 loops=10)
              Index Cond: (id = prodcats.product_id)
Planning time: 0.318 ms
Execution time: 7.066 ms

Dan ini adalah skenario terburuk dengan sejumlah besar produk dalam kategori yang dipilih dan offset besar. Ketika offset = 300 waktu eksekusi hanya 0,5 ms.

Sayangnya mempertahankan tabel persimpangan seperti itu membutuhkan usaha ekstra. Ini dapat dilakukan melalui tampilan terindeks yang terindeks, tetapi itu hanya berguna ketika data Anda jarang diperbarui, karena menyegarkan tampilan terwujud semacam itu adalah operasi yang cukup berat.

Jadi saya tetap dengan indeks GIN sejauh ini, dengan peningkatan work_memdan pengurangan kueri jejak memori.

Berikut adalah beberapa kiat cepat yang dapat membantu meningkatkan kinerja Anda. Saya akan mulai dengan tip termudah, yang hampir tidak mudah di pihak Anda, dan pindah ke tip yang lebih sulit setelah yang pertama.

1. work_mem

Jadi, saya langsung melihat bahwa jenis yang dilaporkan dalam paket penjelasan Anda Sort Method: external merge Disk: 5696kBmengonsumsi kurang dari 6 MB, tetapi tumpah ke disk. Anda perlu meningkatkan work_mempengaturan Anda dalam postgresql.conffile Anda menjadi cukup besar sehingga jenisnya dapat masuk ke dalam memori.

EDIT: Selain itu, pada pemeriksaan lebih lanjut, saya melihat bahwa setelah menggunakan indeks untuk memeriksa catgory_idsyang sesuai dengan kriteria Anda, pemindaian indeks bitmap dipaksa untuk menjadi "lossy" dan harus memeriksa kembali kondisi ketika membaca baris dari dalam halaman tumpukan yang relevan . Lihat posting ini di postgresql.org untuk penjelasan yang lebih baik daripada yang saya berikan. : P Poin utamanya adalah Anda work_memterlalu rendah. Jika Anda belum menyetel pengaturan default di server Anda, itu tidak akan berfungsi dengan baik.

Perbaikan ini pada dasarnya tidak akan membawa Anda waktu. Satu perubahan ke postgresql.conf, dan Anda pergi! Lihat halaman penyesuaian kinerja ini untuk tips lebih lanjut.

2. Perubahan skema

Jadi, Anda telah membuat keputusan dalam desain skema Anda untuk mendenormalkan category_idsmenjadi array integer, yang kemudian memaksa Anda untuk menggunakan indeks GIN atau GIST untuk mendapatkan akses cepat. Dalam pengalaman saya, pilihan Anda untuk indeks GIN akan lebih cepat untuk dibaca daripada GIST, jadi dalam hal ini Anda membuat pilihan yang tepat. Namun, GIN adalah indeks yang tidak disortir; pikir itu lebih seperti sebuah kunci-nilai, di mana predikat kesetaraan mudah untuk memeriksa, tapi operasi seperti WHERE >, WHERE <atau ORDER BYtidak difasilitasi oleh indeks.

Pendekatan yang layak adalah menormalkan desain Anda dengan menggunakan tabel jembatan / tabel persimpangan , yang digunakan untuk menentukan hubungan banyak ke banyak dalam basis data.

Dalam hal ini, Anda memiliki banyak kategori dan satu set integer yang sesuai category_id, dan Anda memiliki banyak produk dan product_ids yang sesuai . Alih-alih kolom dalam tabel produk Anda yang merupakan array integer category_ids, hapus kolom array ini dari skema Anda, dan buat tabel sebagai

CREATE TABLE join_products_categories (product_id int, category_id int);

Kemudian, Anda dapat menghasilkan indeks B-tree pada dua kolom dari tabel bridge,

CREATE INDEX idx_products_in_join_table ON join_products_categories (product_id);
CREATE INDEX idx_products_in_join_table ON join_products_categories (category_id);

Hanya pendapat saya yang sederhana, tetapi perubahan ini dapat membuat perbedaan besar bagi Anda. Cobalah work_memhal pertama yang berubah, paling tidak.

Semoga berhasil!

EDIT:

Buat indeks tambahan untuk membantu penyortiran

Jadi, jika seiring waktu lini produk Anda meluas, permintaan tertentu dapat menghasilkan banyak hasil (ribuan, puluhan ribu?) Tetapi yang mungkin masih hanya sebagian kecil dari total lini produk Anda. Dalam kasus ini, penyortiran bahkan mungkin cukup mahal jika dilakukan dalam memori, tetapi indeks yang dirancang dengan tepat dapat digunakan untuk membantu penyortiran.

Lihat dokumentasi PostgreSQL resmi yang menggambarkan Indeks dan ORDER OLEH .

Jika Anda membuat indeks yang cocok dengan ORDER BYpersyaratan Anda

CREATE INDEX idx_product_sort ON products (score DESC, title);

maka Postgres akan mengoptimalkan dan memutuskan apakah menggunakan indeks atau melakukan pengurutan eksplisit akan lebih hemat biaya. Perlu diingat bahwa tidak ada jaminan bahwa Postgres akan menggunakan indeks; itu akan berusaha untuk mengoptimalkan kinerja dan memilih antara menggunakan indeks atau pengurutan secara eksplisit. Jika Anda membuat indeks ini, pantau untuk melihat apakah itu digunakan cukup untuk membenarkan pembuatannya, dan jatuhkan jika sebagian besar jenis Anda dilakukan secara eksplisit.

Namun, pada titik ini, peningkatan 'ledakan terbesar untuk uang' Anda mungkin akan menggunakan lebih banyak work_mem, tetapi ada beberapa kasus di mana indeks dapat mendukung penyortiran.