Pada artikel sebelumnya kita membahas mesin pengindeksan PostgreSQL dan antarmuka metode akses, serta indeks hash , B-tree , GiST , SP-GiST , GIN , RUM , dan BRIN . Tapi kita masih perlu melihat indeks Bloom.

Bloom

Konsep umum

Filter Bloom klasik adalah struktur data yang memungkinkan kami memeriksa keanggotaan elemen dengan cepat. Filter ini sangat kompak, tetapi memungkinkan positif palsu: ia dapat secara keliru menganggap suatu elemen sebagai anggota suatu himpunan (false positive), tetapi itu tidak diizinkan untuk mempertimbangkan suatu elemen himpunan tidak menjadi anggota (false negative) .

Filter adalah array dari $$$m$ bit (juga disebut tanda tangan ) yang awalnya diisi dengan nol. $$$k$ dipilih fungsi hash yang berbeda yang memetakan setiap elemen set ke $$$k$ sedikit tanda tangan. Untuk menambahkan elemen ke set, kita perlu mengatur masing-masing bit ini di signature menjadi satu. Akibatnya, jika semua bit yang terkait dengan elemen diatur ke satu, elemen dapat menjadi anggota set, tetapi jika setidaknya satu bit sama dengan nol, elemen tidak pasti diatur.

Dalam kasus DBMS, sebenarnya kita miliki $$$N$ filter terpisah dibangun untuk setiap baris indeks. Sebagai aturan, beberapa bidang termasuk dalam indeks, dan nilainya dari bidang ini yang menyusun set elemen untuk setiap baris.

Dengan memilih panjang tanda tangan $$$m$ , kita dapat menemukan trade-off antara ukuran indeks dan probabilitas positif palsu. Area aplikasi untuk indeks Bloom adalah tabel besar, signifikan "lebar" yang akan ditanyakan menggunakan filter pada masing-masing bidang. Metode akses ini, seperti BRIN, dapat dianggap sebagai akselerator pemindaian sekuensial: semua kecocokan yang ditemukan oleh indeks harus diperiksa ulang dengan tabel, tetapi ada kemungkinan untuk menghindari mempertimbangkan sebagian besar baris sama sekali.

Struktur

Kami sudah membahas pohon tanda tangan dalam konteks metode akses GiST . Tidak seperti pohon-pohon ini, indeks Bloom adalah struktur datar. Ini terdiri dari metapage diikuti oleh halaman reguler dengan baris indeks. Setiap baris indeks berisi tanda tangan dan referensi ke baris tabel (TID), seperti yang ditunjukkan secara skematis dalam gambar.

Penciptaan dan pemilihan nilai parameter

Saat membuat indeks Bloom, ukuran total tanda tangan ("panjang") ditentukan, serta jumlah bit yang akan ditetapkan untuk setiap bidang individual yang termasuk dalam indeks ("col1" - "col32"):

create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...); 

Cara untuk menentukan jumlah bit terlihat aneh: angka-angka ini harus menjadi parameter kelas operator dan bukan indeks. Masalahnya adalah bahwa kelas operator tidak dapat dipisah-pisahkan saat ini, meskipun bekerja pada ini sedang berlangsung.

Sayangnya, tidak ada kemajuan lebih lanjut tentang ini.

Bagaimana kita bisa memilih nilai yang sesuai? Teori menyatakan bahwa diberi probabilitas $$$p$ dari filter untuk mengembalikan false positive, jumlah bit tanda tangan yang optimal dapat diperkirakan sebagai $$$m = −n \ log_2 p / \ ln 2$ dimana $$$n$ adalah jumlah bidang dalam indeks dan jumlah bit yang akan ditetapkan adalah $$$k = - \ log_2 p$ .

Tanda tangan disimpan di dalam indeks sebagai array angka integer dua-byte, jadi nilai $$$m$ dapat dengan aman dibulatkan ke $$$16$ .

Saat memilih probabilitas $$$p$ , kita perlu memperhitungkan ukuran indeks, yang kira-kira sama $$$(m / 8 + 6) N$ dimana $$$N$ adalah jumlah baris dalam tabel dan $$$6$ adalah ukuran pointer TID dalam bytes.

Beberapa hal yang perlu diperhatikan:

• Probabilitas $$$p$ dari false positive berhubungan dengan satu filter, oleh karena itu, kami berharap untuk mendapatkannya $$$Np$ false positive selama pemindaian tabel (tentu saja, untuk kueri yang mengembalikan beberapa baris). Misalnya, untuk tabel dengan satu juta baris dan probabilitas 0,01, dalam rencana kueri, rata-rata, kita dapat mengharapkan "Baris Dihapus oleh Indeks Periksa kembali: 10000".
• Filter Bloom adalah struktur probabilistik. Masuk akal untuk berbicara tentang angka-angka tertentu hanya ketika rata-rata nilai cukup banyak, sementara dalam setiap kasus tertentu, kita bisa mendapatkan apa pun yang dapat kita pikirkan.
• Perkiraan di atas didasarkan pada model matematika yang ideal dan beberapa asumsi. Dalam praktiknya, hasilnya cenderung lebih buruk. Jadi, jangan melebih-lebihkan rumus: mereka hanya sarana untuk memilih nilai awal untuk eksperimen di masa depan.
• Untuk setiap bidang secara individual, metode akses memungkinkan kita untuk memilih jumlah bit yang akan ditetapkan. Ada asumsi yang masuk akal bahwa sebenarnya angka optimal tergantung pada distribusi nilai-nilai dalam kolom. Untuk menyelam lebih dalam, Anda dapat membaca artikel ini (referensi untuk penelitian lain dipersilahkan). Tapi baca kembali item sebelumnya.

Memperbarui

Saat baris baru dimasukkan dalam tabel, tanda tangan dibuat: untuk nilai semua bidang yang diindeks, semua bit yang terkait diatur ke satu. Secara teori, kita harus memiliki k fungsi hash yang berbeda, sementara dalam praktiknya, generator bilangan pseudo-acak mencukupi, yang benihnya dipilih setiap kali dengan bantuan satu-satunya fungsi hash.

Filter Bloom biasa tidak mendukung penghapusan elemen, tetapi ini tidak diperlukan untuk indeks Bloom: ketika baris tabel dihapus, seluruh tanda tangan dihapus, bersama dengan baris indeks.

Seperti biasa, pembaruan terdiri dari penghapusan versi baris yang sudah usang dan penyisipan yang baru (tanda tangan dihitung dari awal).

Memindai

Karena satu-satunya hal yang dapat dilakukan filter Bloom adalah memeriksa keanggotaan suatu elemen dalam satu set, satu-satunya operasi yang didukung oleh indeks Bloom adalah pemeriksaan kesetaraan (seperti dalam indeks hash).

Seperti yang telah kami sebutkan, indeks Bloom datar, sehingga dalam perjalanan akses indeks, selalu dibaca berturut-turut dan seluruhnya. Dalam proses membaca, bitmap dibuat, yang kemudian digunakan untuk mengakses tabel.

Dalam akses indeks reguler, diasumsikan bahwa beberapa baris indeks harus dibaca dan, di samping itu, mereka dapat segera dibutuhkan lagi, oleh karena itu, mereka disimpan dalam cache buffer. Namun, pembacaan indeks Bloom sebenarnya adalah pemindaian berurutan. Untuk mencegah penggusuran informasi yang berguna dari cache, pembacaan dilakukan melalui cincin buffer kecil, persis sama seperti untuk pemindaian berurutan tabel.

Kita harus memperhitungkan bahwa semakin besar ukuran indeks Bloom, semakin tidak menarik bagi perencana. Ketergantungan ini linear, tidak seperti indeks seperti pohon.

Contoh

Meja

Mari kita lihat indeks Bloom dengan contoh tabel besar "flight_bi" dari artikel sebelumnya . Untuk mengingatkan Anda, ukuran tabel ini adalah 4 GB dengan sekitar 30 juta baris. Definisi tabel:

 demo=# \d flights_bi 

  Table "bookings.flights_bi" Column | Type | Collation | Nullable | Default --------------------+--------------------------+-----------+----------+--------- airport_code | character(3) | | | airport_coord | point | | | airport_utc_offset | interval | | | flight_no | character(6) | | | flight_type | text | | | scheduled_time | timestamp with time zone | | | actual_time | timestamp with time zone | | | aircraft_code | character(3) | | | seat_no | character varying(4) | | | fare_conditions | character varying(10) | | | passenger_id | character varying(20) | | | passenger_name | text | | | 

Pertama mari kita buat ekstensi: meskipun indeks Bloom termasuk dalam pengiriman standar dimulai dengan versi 9.6, itu tidak tersedia secara default.

 demo=# create extension bloom; 

Terakhir kali kami dapat mengindeks tiga bidang menggunakan BRIN ("dijadwalkan_time", "actual_time", "airport_utc_offset"). Karena indeks Bloom tidak bergantung pada urutan fisik data, mari kita coba untuk memasukkan hampir semua bidang tabel dalam indeks. Namun, mari kita mengecualikan bidang waktu ("schedule_time" dan "actual_time"): metode ini hanya mendukung perbandingan untuk kesetaraan, tetapi kueri untuk waktu yang tepat hampir tidak menarik bagi siapa pun (kita dapat, bagaimanapun, membangun indeks pada ekspresi, membulatkan waktu ke hari, tetapi kami tidak akan melakukan ini). Kami juga harus mengecualikan koordinat geografis bandara ("airport_coord"): melihat ke depan, tipe "titik" tidak didukung.

Untuk memilih nilai parameter, mari kita atur probabilitas false positive ke 0,01 (mengingat bahwa sebenarnya kita akan mendapatkan lebih banyak). Rumus di atas untuk $$$n = 9$ dan $$$N = 30 \, 000 \, $ 00$ berikan ukuran tanda tangan 96 bit dan sarankan pengaturan 7 bit per elemen. Ukuran perkiraan indeks adalah 515 MB (sekitar seperdelapan tabel).

(Dengan ukuran tanda tangan minimal 16 bit, rumus menjanjikan ukuran indeks yang dua kali lebih kecil, tetapi mengizinkan untuk hanya mengandalkan probabilitas 0,5, yang sangat buruk.)

Kelas operator

Jadi, mari kita coba membuat indeks.

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 ERROR: data type character has no default operator class for access method "bloom" HINT: You must specify an operator class for the index or define a default operator class for the data type. 

Sayangnya, ekstensi hanya memberi kami dua kelas operator:

 demo=# select opcname, opcintype::regtype from pg_opclass where opcmethod = (select oid from pg_am where amname = 'bloom') order by opcintype::regtype::text; 

  opcname | opcintype ----------+----------- int4_ops | integer text_ops | text (2 rows) 

Namun untungnya, cukup mudah untuk membuat kelas yang serupa untuk tipe data lainnya juga. Kelas operator untuk metode akses Bloom harus mengandung tepat satu operator - kesetaraan - dan satu fungsi bantu - hashing. Cara paling sederhana untuk menemukan operator dan fungsi yang diperlukan untuk tipe arbitrer adalah dengan melihat katalog sistem untuk kelas operator dari metode "hash":

 demo=# select distinct opc.opcintype::regtype::text, amop.amopopr::regoperator, ampr.amproc from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr where am.amname = 'hash' and opc.opcmethod = am.oid and amop.amopfamily = opc.opcfamily and amop.amoplefttype = opc.opcintype and amop.amoprighttype = opc.opcintype and ampr.amprocfamily = opc.opcfamily and ampr.amproclefttype = opc.opcintype order by opc.opcintype::regtype::text; 

  opcintype | amopopr | amproc -----------+----------------------+-------------- abstime | =(abstime,abstime) | hashint4 aclitem | =(aclitem,aclitem) | hash_aclitem anyarray | =(anyarray,anyarray) | hash_array anyenum | =(anyenum,anyenum) | hashenum anyrange | =(anyrange,anyrange) | hash_range ... 

Kami akan membuat dua kelas yang hilang menggunakan informasi ini:

 demo=# CREATE OPERATOR CLASS character_ops DEFAULT FOR TYPE character USING bloom AS OPERATOR 1 =(character,character), FUNCTION 1 hashbpchar; demo=# CREATE OPERATOR CLASS interval_ops DEFAULT FOR TYPE interval USING bloom AS OPERATOR 1 =(interval,interval), FUNCTION 1 interval_hash; 

Fungsi hash tidak didefinisikan untuk titik (tipe "titik"), dan untuk alasan inilah kita tidak dapat membangun indeks Bloom pada bidang seperti itu (seperti halnya kita tidak dapat melakukan gabungan hash pada bidang jenis ini).

Coba lagi:

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 CREATE INDEX 

Ukuran indeks adalah 526 MB, yang agak lebih besar dari yang diharapkan. Ini karena rumus tidak memperhitungkan overhead halaman.

 demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom')); 

  pg_size_pretty ---------------- 526 MB (1 row) 

Pertanyaan

Kami sekarang dapat melakukan pencarian menggunakan berbagai kriteria, dan indeks akan mendukungnya.

Seperti yang telah kami sebutkan, filter Bloom adalah struktur probabilistik, oleh karena itu, efisiensi sangat tergantung pada setiap kasus tertentu. Misalnya, mari kita lihat baris yang terkait dengan dua penumpang, Miroslav Sidorov:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1) Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Rows Removed by Index Recheck: 38562 Heap Blocks: exact=21726 -> Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1) Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Planning time: 0.109 ms Execution time: 3010.736 ms 

dan Marfa Soloveva:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MARFA SOLOVEVA'; 

  QUERY PLAN --------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1) Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Rows Removed by Index Recheck: 3950168 Heap Blocks: exact=45757 lossy=67332 -> Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1) Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Planning time: 0.157 ms Execution time: 10142.730 ms 

Dalam satu kasus, filter hanya mengizinkan 40 ribu positif palsu dan sebanyak 4 juta di antaranya ("Baris Dihapus oleh Indeks Periksa kembali"). Waktu pelaksanaan kueri berbeda sesuai.

Dan berikut ini adalah hasil pencarian baris yang sama dengan ID penumpang daripada nama. Miroslav:

 demo=# explain(costs off,analyze) demo-# select * from flights_bi where passenger_id='5864 006033'; 

  QUERY PLAN ------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '5864 006033'::text) Rows Removed by Index Recheck: 9620258 Heap Blocks: exact=50510 lossy=165722 -> Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1) Index Cond: ((passenger_id)::text = '5864 006033'::text) Planning time: 0.110 ms Execution time: 16907.423 ms 

Dan marfa:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_id='2461 559238'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '2461 559238'::text) Rows Removed by Index Recheck: 30669 Heap Blocks: exact=27513 -> Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1) Index Cond: ((passenger_id)::text = '2461 559238'::text) Planning time: 0.120 ms Execution time: 3934.517 ms 

Efisiensinya jauh berbeda lagi, dan kali ini Marfa lebih beruntung.

Perhatikan bahwa pencarian oleh dua bidang secara bersamaan akan dilakukan jauh lebih efisien karena kemungkinan false positive $$$p$ berubah menjadi $$$p ^ 2$ :

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV' and passenger_id='5864 006033'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1) Recheck Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Rows Removed by Index Recheck: 357 Heap Blocks: exact=356 -> Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1) Index Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Planning time: 0.524 ms Execution time: 877.967 ms 

Namun, pencarian dengan Boolean "atau" tidak didukung sama sekali; ini adalah batasan perencana daripada metode akses. Tentu saja, opsi tetap membaca indeks dua kali, membangun dua bitmap, dan bergabung dengan mereka, tetapi ini kemungkinan besar terlalu mahal untuk rencana ini untuk dipilih.

Perbandingan dengan BRIN dan Hash

Area aplikasi dari indeks Bloom dan BRIN jelas bersinggungan. Ini adalah tabel besar yang diinginkan untuk memastikan pencarian dengan bidang yang berbeda, akurasi pencarian dikorbankan untuk kekompakan.

Indeks BRIN lebih kompak (katakanlah, hingga puluhan megabyte dalam contoh kami) dan dapat mendukung pencarian berdasarkan rentang, tetapi memiliki batasan kuat terkait dengan pemesanan fisik data dalam file. Indeks Bloom lebih besar (ratusan megabita), tetapi tidak memiliki batasan kecuali ketersediaan fungsi hash yang sesuai.

Seperti indeks Bloom, indeks hash mendukung satu-satunya operasi pemeriksaan kesetaraan. Indeks hash memastikan akurasi pencarian yang tidak dapat diakses untuk Bloom, tetapi ukuran indeks jauh lebih besar (dalam contoh kami, satu gigabyte untuk hanya satu bidang, dan indeks hash tidak dapat dibuat di beberapa bidang).

Properti

Seperti biasa, mari kita lihat properti Bloom (kueri sudah disediakan ).

Berikut ini adalah properti dari metode akses:

  amname | name | pg_indexam_has_property --------+---------------+------------------------- bloom | can_order | f bloom | can_unique | f bloom | can_multi_col | t bloom | can_exclude | f 

Jelas, metode akses memungkinkan kami untuk membuat indeks pada beberapa kolom. Sangat tidak masuk akal untuk membuat indeks Bloom pada satu kolom.

Properti lapisan indeks berikut tersedia:

  name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | f bitmap_scan | t backward_scan | f 

Satu-satunya teknik pemindaian yang tersedia adalah pemindaian bitmap. Karena indeks selalu dipindai seluruhnya, tidak masuk akal untuk menerapkan akses indeks reguler yang mengembalikan baris TID oleh TID.

  name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | f search_array | f search_nulls | f 

Hanya tanda hubung di sini; metode ini bahkan tidak dapat memanipulasi NULLs.

Dan akhirnya:

Bukan tidak mungkin seri artikel ini akan dilanjutkan di masa mendatang, ketika jenis indeks minat baru muncul, tetapi sekarang saatnya untuk berhenti.

Saya ingin menyampaikan penghargaan kepada kolega-kolega saya dari Postgres Professional (beberapa di antaranya adalah penulis dari banyak metode akses yang dibahas) karena membaca draf dan memberikan komentar mereka. Dan saya, tentu saja, berterima kasih kepada Anda atas kesabaran dan komentar Anda yang berharga. Perhatian Anda mendorong saya untuk mencapai titik ini. Terima kasih