Indeks apa yang digunakan dengan banyak nilai duplikat?

Mari kita membuat beberapa asumsi:

Saya punya tabel yang terlihat seperti ini:

 a | b
---+---
 a | -1
 a | 17
  ...
 a | 21
 c | 17
 c | -3
  ...
 c | 22

Fakta tentang set saya:

• Ukuran seluruh tabel adalah ~ 10 ¹⁰ baris.

• Saya memiliki ~ 100rb baris dengan nilai adalam kolom a, mirip dengan nilai-nilai lain (misalnya c).

• Itu berarti ~ 100k nilai berbeda di kolom 'a'.

• Sebagian besar pertanyaan saya akan membaca semua atau sebagian besar nilai untuk nilai yang diberikan dalam, misalnya select sum(b) from t where a = 'c'.

• Tabel ditulis sedemikian rupa sehingga nilai berturut-turut secara fisik dekat (baik itu ditulis dalam urutan, atau kami asumsikan CLUSTERdigunakan pada tabel dan kolom itu a).

• Tabel jarang jika pernah diperbarui, kami hanya khawatir tentang kecepatan baca.

• Tabel ini relatif sempit (katakan ~ 25 byte per tuple, + 23 byte overhead).

Sekarang pertanyaannya adalah, indeks seperti apa yang harus saya gunakan? Pemahaman saya adalah:

• BTree Masalah saya di sini adalah bahwa indeks BTree akan sangat besar karena sejauh yang saya tahu itu akan menyimpan nilai duplikat (harus, karena tidak dapat menganggap tabel diurutkan secara fisik). Jika BTree sangat besar, saya harus membaca indeks dan bagian tabel yang ditunjuk indeks. (Kita bisa gunakan fillfactor = 100untuk mengurangi ukuran indeks sedikit.)

• BRIN Pemahaman saya adalah bahwa saya dapat memiliki indeks kecil di sini dengan mengorbankan membaca halaman yang tidak berguna. Menggunakan yang kecil pages_per_rangeberarti bahwa indeksnya lebih besar (yang merupakan masalah dengan BRIN karena saya perlu membaca keseluruhan indeks), memiliki pages_per_rangesarana yang besar sehingga saya akan membaca banyak halaman yang tidak berguna. Apakah ada formula ajaib untuk menemukan nilai bagus pages_per_rangeyang memperhitungkan pengorbanan itu?

• GIN / GiST Tidak yakin itu relevan di sini karena sebagian besar digunakan untuk pencarian teks lengkap, tetapi saya juga mendengar bahwa mereka pandai menangani kunci duplikat. Apakah indeks GINatau GiSTbantuan di sini?

Pertanyaan lain adalah, akankah Postgres menggunakan fakta bahwa sebuah tabel sudah CLUSTERdiedit (dengan asumsi tidak ada pembaruan) dalam perencana kueri (mis. Dengan pencarian biner untuk halaman awal / akhir yang relevan)? Agak terkait, bisakah saya menyimpan semua kolom saya di BTree dan menjatuhkan tabel sama sekali (atau mencapai sesuatu yang setara, saya percaya itu adalah indeks yang dikelompokkan dalam SQL server)? Apakah ada indeks BTree / BRIN hybrid yang akan membantu di sini?

Saya lebih suka menghindari menggunakan array untuk menyimpan nilai-nilai saya karena permintaan saya akan berakhir kurang dapat dibaca dengan cara itu (saya mengerti ini akan mengurangi biaya 23 byte per tuple overhead dengan mengurangi jumlah tuple).

BTree

Masalah saya di sini adalah bahwa indeks BTree akan sangat besar karena afaict akan menyimpan nilai duplikat (juga, karena tidak dapat menganggap tabel diurutkan secara fisik). Jika BTree besar saya akhirnya harus membaca indeks dan bagian-bagian tabel yang indeksnya juga ...

Belum tentu - Memiliki indeks btree yang 'meliputi' akan menjadi waktu membaca tercepat, dan jika hanya itu yang Anda inginkan (yaitu jika Anda mampu membeli penyimpanan tambahan), maka itu adalah taruhan terbaik Anda.

BRIN

Pemahaman saya adalah bahwa saya dapat memiliki indeks kecil di sini dengan mengorbankan membaca halaman yang tidak berguna. Menggunakan yang kecil pages_per_rangeberarti bahwa indeksnya lebih besar (yang merupakan masalah dengan BRIN karena saya perlu membaca keseluruhan indeks), memiliki pages_per_rangesarana yang besar sehingga saya akan membaca banyak halaman yang tidak berguna.

Jika Anda tidak mampu membeli overhead penyimpanan dari indeks btree penutup, BRIN sangat ideal untuk Anda, karena Anda sudah memiliki pengelompokan (ini sangat penting bagi BRIN untuk berguna). Indeks BRIN kecil , sehingga semua halaman cenderung berada dalam memori jika Anda memilih nilai yang sesuai pages_per_range.

Apakah ada rumus ajaib untuk menemukan nilai pages_per_range yang bagus yang memperhitungkan pertukaran tersebut?

Tidak ada rumus ajaib, tetapi mulai dengan pages_per_range sedikit kurang dari ukuran rata-rata (dalam halaman) yang ditempati oleh nilai rata-rata a. Anda mungkin mencoba memperkecil: (jumlah halaman BRIN dipindai) + (jumlah halaman tumpukan yang dipindai) untuk kueri yang khas. Cari Heap Blocks: lossy=ndalam rencana eksekusi pages_per_range=1dan bandingkan dengan nilai-nilai lain untuk pages_per_range- yaitu melihat berapa banyak heap block yang tidak perlu sedang dipindai.

GIN / GiST

Tidak yakin itu relevan di sini karena sebagian besar digunakan untuk pencarian teks lengkap, tetapi saya juga mendengar bahwa mereka pandai menangani kunci duplikat. Apakah salah satu GIN/ GiSTindeks membantu di sini?

GIN mungkin layak dipertimbangkan, tetapi mungkin bukan GST - namun jika pengelompokan alami benar-benar baik, maka BRIN mungkin akan menjadi taruhan yang lebih baik.

Berikut ini adalah perbandingan sampel antara berbagai jenis indeks untuk data tiruan sedikit seperti milik Anda:

tabel dan indeks:

create table foo(a,b,c) as
select *, lpad('',20)
from (select chr(g) a from generate_series(97,122) g) a
     cross join (select generate_series(1,100000) b) b
order by a;
create index foo_btree_covering on foo(a,b);
create index foo_btree on foo(a);
create index foo_gin on foo using gin(a);
create index foo_brin_2 on foo using brin(a) with (pages_per_range=2);
create index foo_brin_4 on foo using brin(a) with (pages_per_range=4);
vacuum analyze;

ukuran hubungan:

select relname "name", pg_size_pretty(siz) "size", siz/8192 pages, (select count(*) from foo)*8192/siz "rows/page"
from( select relname, pg_relation_size(C.oid) siz
      from pg_class c join pg_namespace n on n.oid = c.relnamespace
      where nspname = current_schema ) z;

nama | ukuran | halaman | baris / halaman
: ----------------- | : ------ | ----: | --------:
foo | 149 MB | 19118 | 135
foo_btree_covering | 56 MB | 7132 | 364
foo_btree | 56 MB | 7132 | 364
foo_gin | 2928 kB | 366 | 7103
foo_brin_2 | 264 kB | 33 | 78787
foo_brin_4 | 136 kB | 17 | 152941

meliputi btree:

explain analyze select sum(b) from foo where a='a';

| RENCANA QUERY |
| : ------------------------------------------------- -------------------------------------------------- ------------------------------------------- |
| Agregat (biaya = 3282.57..3282.58 baris = 1 lebar = 8) (waktu aktual = 45.942..45.942 baris = 1 loop = 1) |
| -> Indeks Hanya Memindai menggunakan foo_btree_covering on foo (biaya = 0,43..3017,80 baris = lebar 105907 = 4) (waktu aktual = 0,038..27.286 baris = 100000 putaran = 1) |
| Indeks Cond: (a = 'a' :: text) |
| Heap Fetches: 0 |
| Waktu perencanaan: 0,099 ms |
| Waktu pelaksanaan: 45.968 ms |

btree polos:

drop index foo_btree_covering;
explain analyze select sum(b) from foo where a='a';

| RENCANA QUERY |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregat (biaya = 4064,57..4064.58 baris = 1 lebar = 8) (waktu aktual = 54.242..54.242 baris = 1 loop = 1) |
| -> Pemindaian Indeks menggunakan foo_btree on foo (biaya = 0,43..3799,80 baris = lebar 105907 = 4) (waktu aktual = 0,037..33.084 baris = 100000 putaran = 1) |
| Indeks Cond: (a = 'a' :: text) |
| Waktu perencanaan: 0.135 ms |
| Waktu pelaksanaan: 54.280 ms |

BRIN pages_per_range = 4:

drop index foo_btree;
explain analyze select sum(b) from foo where a='a';

| RENCANA QUERY |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregat (biaya = 21595.38..21595.39 baris = 1 lebar = 8) (waktu aktual = 52.455..52.455 baris = 1 loop = 1) |
| -> Bitmap Heap Scan pada foo (biaya = 888.78..21330.61 baris = lebar 105907 = 4) (waktu aktual = 2.738..31.967 baris = 100000 putaran = 1) |
| Periksa kembali Cond: (a = 'a' :: text) |
| Baris Dihapus oleh Indeks Periksa kembali: 96 |
| Heap Blocks: lossy = 736 |
| -> Indeks Bitmap Memindai pada foo_brin_4 (biaya = 0,00..862,30 baris = lebar 105907 = 0) (waktu aktual = 2,720..2,720 baris = 7360 loop = 1) |
| Indeks Cond: (a = 'a' :: text) |
| Waktu perencanaan: 0,101 ms |
| Waktu pelaksanaan: 52.501 ms |

BRIN pages_per_range = 2:

drop index foo_brin_4;
explain analyze select sum(b) from foo where a='a';

| RENCANA QUERY |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregat (biaya = 21659,38..21659,39 baris = 1 lebar = 8) (waktu aktual = 53.971..53.971 baris = 1 loop = 1) |
| -> Bitmap Heap Scan pada foo (biaya = 952,78..21394.61 baris = lebar 105907 = 4) (waktu aktual = 5.286..33.492 baris = 100000 putaran = 1) |
| Periksa kembali Cond: (a = 'a' :: text) |
| Baris Dihapus oleh Indeks Periksa kembali: 96 |
| Heap Blocks: lossy = 736 |
| -> Indeks Bitmap Memindai pada foo_brin_2 (biaya = 0,00..926,30 baris = lebar 105907 = 0) (waktu aktual = 5,275.,5.275 baris = 7360 loop = 1) |
| Indeks Cond: (a = 'a' :: text) |
| Waktu perencanaan: 0,095 ms |
| Waktu pelaksanaan: 54.016 ms |

GIN:

drop index foo_brin_2;
explain analyze select sum(b) from foo where a='a';

| RENCANA QUERY |
| : ------------------------------------------------- -------------------------------------------------- ------------------------------ |
| Agregat (biaya = 21687.38..21687.39 baris = 1 lebar = 8) (waktu aktual = 55.331..55.331 baris = 1 putaran = 1) |
| -> Bitmap Heap Scan pada foo (biaya = 980.78..21422.61 baris = lebar 105907 = 4) (waktu aktual = 12.377..33.956 baris = 100000 putaran = 1) |
| Periksa kembali Cond: (a = 'a' :: text) |
| Heap Blocks: tepat = 736 |
| -> Pemindaian Indeks Bitmap pada foo_gin (biaya = 0,00..954,30 baris = lebar 105907 = 0) (waktu aktual = 12,271..12,271 baris = 100000 loop = 1) |
| Indeks Cond: (a = 'a' :: text) |
| Waktu perencanaan: 0.118 ms |
| Waktu pelaksanaan: 55.366 ms |

Aku di sini

Selain btree dan brin yang tampaknya merupakan opsi yang paling masuk akal, beberapa opsi eksotis lainnya yang mungkin layak diselidiki - mungkin bermanfaat atau tidak dalam kasus Anda:

• INCLUDEindeks . Mereka akan - semoga - dalam versi utama berikutnya (10) dari Postgres, di suatu tempat sekitar bulan September 2017. Indeks pada (a) INCLUDE (b)memiliki struktur yang sama dengan indeks pada (a)tetapi termasuk dalam halaman daun, semua nilai b(tetapi tidak tertata). Yang berarti Anda tidak dapat menggunakannya misalnya untuk SELECT * FROM t WHERE a = 'a' AND b = 2 ;. Indeks mungkin digunakan tetapi sementara (a,b)indeks akan menemukan baris yang cocok dengan pencarian tunggal, indeks sertakan harus melalui nilai (mungkin 100K seperti pada kasus Anda) yang cocok a = 'a'dan memeriksa bnilai.
  Di sisi lain, indeks sedikit lebih lebar dari (a,b)indeks dan Anda tidak perlu urutan buntuk kueri Anda untuk menghitung SUM(b). Anda juga bisa memiliki misalnya(a) INCLUDE (b,c,d) yang dapat digunakan untuk kueri yang serupa dengan milik Anda yang mengumpulkan 3 kolom.

• Indeks yang disaring (sebagian) . Saran yang mungkin terdengar agak gila ^* pada awalnya:

  CREATE INDEX flt_a  ON t (b) WHERE (a = 'a') ;
  ---
  CREATE INDEX flt_xy ON t (b) WHERE (a = 'xy') ;

  Satu indeks untuk setiap anilai. Dalam kasus Anda, indeks sekitar 100 ribu. Walaupun ini terdengar banyak, pertimbangkan bahwa setiap indeks akan sangat kecil, baik dalam ukuran (jumlah baris) dan lebar (karena hanya akan menyimpan bnilai). Dalam semua aspek lain, itu (indeks 100K bersama-sama) akan bertindak sebagai indeks b-tree (a,b)saat menggunakan ruang (b)indeks.
  Kerugiannya adalah Anda harus membuat dan memeliharanya sendiri, setiap kali nilai baru aditambahkan ke dalam tabel. Karena meja Anda agak stabil, tanpa banyak (atau ada) sisipan / pembaruan, itu tidak tampak seperti masalah.

• Tabel ringkasan. Karena tabelnya agak stabil, Anda selalu dapat membuat dan mengisi tabel ringkasan dengan agregat paling umum yang Anda perlukan ( sum(b), sum(c), sum(d), avg(b), count(distinct b), dll). Ini akan menjadi kecil (hanya 100K baris) dan hanya perlu diisi sekali dan diperbarui hanya ketika baris dimasukkan / diperbarui / dihapus pada tabel utama.

^{*: ide disalin dari perusahaan ini yang menjalankan 10 juta indeks dalam sistem produksi mereka: Heap: Menjalankan 10 Juta Indeks Postgresql Dalam Produksi (dan terus bertambah) .}