Memahami “bitmap heap scan” dan “bitmap index scan”

Saya akan mencoba menjelaskan kesalahpahaman saya dengan contoh berikut.

Saya tidak mengerti dasar - dasarBitmap Heap Scan Node . Pertimbangkan kueri SELECT customerid, username FROM customers WHERE customerid < 1000 AND username <'user100';rencananya:

Bitmap Heap Scan on customers  (cost=25.76..61.62 rows=10 width=13) (actual time=0.077..0.077 rows=2 loops=1)
  Recheck Cond: (((username)::text < 'user100'::text) AND (customerid < 1000))
  ->  BitmapAnd  (cost=25.76..25.76 rows=10 width=0) (actual time=0.073..0.073 rows=0 loops=1)
        ->  Bitmap Index Scan on ix_cust_username  (cost=0.00..5.75 rows=200 width=0) (actual time=0.006..0.006 rows=2 loops=1)
              Index Cond: ((username)::text < 'user100'::text)
        ->  Bitmap Index Scan on customers_pkey  (cost=0.00..19.75 rows=1000 width=0) (actual time=0.065..0.065 rows=999 loops=1)
              Index Cond: (customerid < 1000)

Pemahaman saya tentang simpul ini :

Seperti yang dijelaskan di sana , bitmap heap scantabel membaca memblokir secara berurutan, sehingga tidak menghasilkan overhead tabel acak yang terjadi hanya sebagai melakukan Index Scan.

Setelah Index Scanselesai, PostgreSQL tidak tahu cara mengambil baris secara optimal, untuk menghindari yang tidak perlu heap blocks reads(atau hitsjika ada cache panas). Jadi untuk mencari tahu itu menghasilkan struktur ( Bitmap Index Scan) yang disebut bitmapdalam kasus saya sedang dihasilkan dengan menghasilkan dua bitmap dari indeks dan melakukan BITWISE AND. Karena bitmap telah dihasilkan sekarang dapat membaca tabel secara optimal dalam urutan berurutan, menghindari yang tidak perlu heap I/O-operations.

Di situlah banyak pertanyaan datang.

PERTANYAAN: Kami hanya memiliki bitmap. Bagaimana PostgreSQL tahu hanya sedikit bitmap tentang urutan fisik baris? Atau menghasilkan bitmap sehingga elemen apa pun dapat dipetakan ke pointer ke halaman dengan mudah? Jika demikian, itu menjelaskan segalanya, tetapi itu hanya dugaan saya.

Jadi, dapatkah kita katakan secara sederhana bahwa bitmap heap scan -> bitmap index scanini seperti pemindaian berurutan tetapi hanya bagian yang sesuai dari tabel?

Bagaimana PostgreSQL tahu hanya sedikit bitmap tentang urutan fisik baris?

Bitmap adalah satu bit per heap page. Pemindaian indeks bitmap menetapkan bit berdasarkan alamat halaman heap yang ditunjuk oleh entri indeks.

Jadi ketika akan melakukan pemindaian tumpukan bitmap, ia hanya melakukan pemindaian tabel linear, membaca bitmap untuk melihat apakah ia harus repot dengan halaman tertentu atau mencari di atasnya.

Atau menghasilkan bitmap sehingga elemen apa pun dapat dipetakan ke pointer ke halaman dengan mudah?

Tidak, bitmap sesuai dengan 1: 1 untuk menumpuk halaman.

Saya menulis lebih banyak tentang ini di sini .

OK, sepertinya Anda mungkin salah paham apa arti "bitmap" dalam konteks ini.

Ini bukan string sedikit seperti "101011" yang dibuat untuk setiap halaman tumpukan, atau setiap indeks dibaca, atau apa pun.

Seluruh bitmap adalah array bit tunggal , dengan bit sebanyak-banyaknya karena ada tumpukan halaman dalam relasi yang dipindai.

Satu bitmap dibuat oleh pemindaian indeks pertama, dimulai dengan semua entri 0 (salah). Setiap kali entri indeks yang cocok dengan kondisi pencarian ditemukan, alamat heap yang ditunjuk oleh entri indeks tersebut dilihat sebagai offset ke dalam bitmap, dan bit itu diatur ke 1 (benar). Jadi daripada melihat halaman tumpukan secara langsung, pemindaian indeks bitmap mencari posisi bit yang sesuai dalam bitmap.

Scan indeks bitmap kedua dan selanjutnya melakukan hal yang sama dengan indeks lain dan kondisi pencarian pada mereka.

Kemudian setiap bitmap adalah ANDed bersama. Bitmap yang dihasilkan memiliki satu bit untuk setiap halaman heap, di mana bit benar hanya jika benar dalam semua pemindaian indeks bitmap individu, yaitu kondisi pencarian yang cocok untuk setiap pemindaian indeks. Ini adalah satu-satunya halaman tumpukan yang perlu kita susahkan untuk memuat dan memeriksa. Karena setiap halaman tumpukan mungkin berisi beberapa baris, kami kemudian harus memeriksa setiap baris untuk melihat apakah itu cocok dengan semua kondisi - itulah yang dimaksud dengan bagian "periksa kembali kond".

Satu hal penting untuk dipahami dengan semua ini adalah bahwa alamat tuple dalam entri indeks menunjuk ke baris ctid, yang merupakan kombinasi dari nomor halaman tumpukan dan offset di dalam halaman tumpukan. Pemindaian indeks bitmap mengabaikan offset, karena tetap akan memeriksa seluruh halaman, dan menetapkan bit jika ada baris pada halaman yang cocok dengan kondisi tersebut.

Contoh grafis

Heap, one square = one page:
+---------------------------------------------+
|c____u_____X___u___X_________u___cXcc______u_|
+---------------------------------------------+
Rows marked c match customers pkey condition.
Rows marked u match username condition.
Rows marked X match both conditions.


Bitmap scan from customers_pkey:
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
+---------------------------------------------+
One bit per heap page, in the same order as the heap
Bits 1 when condition matches, 0 if not

Bitmap scan from ix_cust_username:
+---------------------------------------------+
|000001000001000100010000000001000010000000010| bitmap 2
+---------------------------------------------+

Setelah bitmap dibuat, bitwise DAN dilakukan pada mereka:

+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
|000001000001000100010000000001000010000000010| bitmap 2
 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
|000000000001000000010000000000000010000000000| Combined bitmap
+-----------+-------+--------------+----------+
            |       |              |
            v       v              v
Used to scan the heap only for matching pages:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+

Bitmap heap scan kemudian mencari bagian awal setiap halaman dan membaca halaman:

+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
seek------->^seek-->^seek--------->^
            |       |              |
            ------------------------
            only these pages read

dan setiap halaman baca kemudian diperiksa ulang terhadap kondisi karena mungkin ada> 1 baris per halaman dan tidak semua harus sesuai dengan kondisi.

Silakan lihat posting blog saya https://rajeevrastogi.blogspot.in/2018/02/bitmap-scan-in-postgresql.html?showComment=1518410565792#c4647352762092142586 untuk rincian deskripsi pemindaian bitmap di PostgreSQL.

Ikhtisar fungsionalitas cepat keseluruhan dari pemindaian bitmap:

1. Bitmap Heap scan meminta tuple dari Bitmap Index Scan.

2. Pemindaian Indeks Bitmap memindai indeks sesuai kondisi yang hampir sama seperti yang dilakukan dalam Pemindaian Indeks normal. Tetapi alih-alih mengembalikan TID (terdiri dari halaman no dan offset di dalamnya) yang sesuai dengan data heap, itu menambahkan TID itu dalam bitmap. Untuk pemahaman sederhana, Anda dapat mempertimbangkan bitmap ini berisi hash dari semua halaman (hash berdasarkan halaman no) dan setiap entri halaman berisi larik semua offset dalam halaman tersebut.

3. Kemudian Pemindaian Tumpukan Bitmap membaca bitmap untuk mendapatkan data tumpukan yang sesuai dengan nomor halaman yang disimpan dan diimbangi. Kemudian memeriksa visibilitas, kualifikasi dll dan mengembalikan tuple berdasarkan hasil dari semua cek ini.