Visualisasi Indeks SQLite

 (mrsuh.com)
3 poin oleh GN⁺ 2024-11-16 | 1 komentar | Bagikan ke WhatsApp
  • Menganalisis struktur B-Tree untuk melihat bagaimana indeks SQLite sebenarnya ditempatkan di disk dan memori, lalu men-dump data indeks dan memvisualisasikannya
  • Indeks tersusun dari unit Page dan Cell; Page memiliki tautan ke anak kanan dan data Cell, sedangkan Cell memiliki data indeks, rowId, dan tautan ke anak kiri
  • Informasi dari sqlite3_analyzer seperti ukuran Page, jumlah entri, kedalaman B-tree, dan jumlah Page yang digunakan belum memadai, sehingga ditambahkan fungsi debug ke source SQLite
  • Eksperimen membandingkan jumlah record, ASC/DESC, indeks berbasis ekspresi, UNIQUE yang mencakup NULL, Partial Index, multi-kolom, serta kombinasi teks, REAL, dan integer+teks
  • Pada 1.000.000 record, jika indeks dibuat sebelum insert hasilnya 3.342 Pages, sedangkan jika dibuat setelah insert hasilnya 2.930 Pages; setelah VACUUM atau REINDEX juga turun menjadi 2.930 Pages

Alasan melihat langsung indeks SQLite

  • Ini adalah eksperimen untuk memeriksa struktur data, algoritme, dan cara penyimpanan di disk yang sebenarnya, melampaui struktur dasar indeks
  • Tujuannya adalah melihat bagaimana DBMS menyimpan indeks di disk dan memori, serta bagaimana indeks tersebut diakses dalam proses pencarian
  • SQLite dipilih sebagai objek eksperimen karena alasan berikut
    • DBMS ini banyak digunakan di browser, aplikasi mobile, dan sistem operasi
    • Mudah di-debug hanya dengan aplikasi klien tanpa server terpisah
    • Codebase-nya lebih kecil daripada MySQL atau PostgreSQL, tetapi menggunakan struktur data yang serupa untuk indeks
    • Bersifat open source

B-Tree yang terdiri dari Page dan Cell

  • Menurut dokumentasi SQLite, indeks disimpan sebagai struktur B-Tree
  • Di SQLite, unit yang setara dengan Node adalah Page
    • Page menyimpan data Cell
    • Page memiliki tautan ke Page anak kanan
  • Cell berisi data indeks, rowId, dan tautan ke Page anak kiri
  • Setiap baris dalam tabel SQLite pada dasarnya memiliki rowId unik, dan saat tidak ada primary key eksplisit, rowId bertindak seperti primary key
  • Setiap Page memiliki ukuran tetap, dengan rentang ukuran 512–65.536 bytes
  • Header Page dan Cell menggunakan 4 bytes untuk menyimpan tautan anak
    • Untuk mengetahui nomor Page anak, header harus dibaca secara terpisah dengan fungsi get4byte(...)
  • Contoh struktur internal SQLite adalah sebagai berikut
    • MemPage: berisi nomor Page pgno, jumlah Cell nCell, area indeks Cell aCellIdx, pointer citra disk data Page aData, dan lainnya
    • CellInfo: berisi pPayload yang menunjuk ke posisi awal payload, dan lainnya

Keterbatasan sqlite3_analyzer dan fungsi debug

  • Dengan sqlite3_analyzer, informasi umum indeks dapat dilihat
    • Contoh output mencakup ukuran Page 4096, jumlah entri 1000, kedalaman B-tree 2, jumlah Page yang digunakan 4, dan lainnya
  • Namun, untuk melihat langsung Cell internal dan payload dalam indeks, tool ini hanya memberikan informasi ringkasan
  • Setelah beberapa minggu bereksperimen, fungsi untuk analisis indeks dibuat
    • Kode: sqlite.patch
    • sqlite3DebugGetMemoryPayload(Mem *mem)
    • sqlite3DebugGetCellPayloadAndRowId(BtCursor *pCur, MemPage * pPage, int cellIndex)
    • sqlite3DebugBtreeIndexDump(BtCursor *pCur, int pageNumber)
  • Fungsi ini membaca isi indeks yang dipilih dan mencetaknya ke STDOUT
    • Alurnya adalah SQL query -> selected index -> stdout
    • Output mencakup nomor Page, nomor Page anak kanan, nomor Cell, nomor Page anak kiri, payload, dan rowId
  • Lingkungan eksperimen dapat dijalankan dengan Docker
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/dump-index.sh database.sqlite "SELECT * FROM table INDEXED BY index WHERE column=1" dump.txt

Perubahan metode visualisasi

  • Awalnya d3-org-tree digunakan untuk memvisualisasikan struktur indeks
  • Saat tree menjadi lebih dalam dan jumlah Page di tiap level bertambah, sulit mengatur jarak antar-Page, sehingga gambar menjadi terlalu besar dan sulit dibaca
  • Upaya penyesuaian dengan JavaScript dan CSS tidak berjalan baik, sehingga sempat beralih ke tampilan struktur berbasis teks
  • Output teks menampilkan jumlah total Page, jumlah total Cell, jumlah Page dan Cell per level, informasi Page, serta informasi Cell dan payload
  • Kemudian visualisasi dikembangkan menjadi output gambar dengan kontrol desain dan jarak yang lebih detail menggunakan ekstensi ImageMagick untuk PHP
  • Gambar akhir mencakup informasi berikut
    • Menampilkan informasi umum indeks di kiri atas
    • Menampilkan jumlah total Page dan Cell di tiap level
    • Untuk setiap Page, menampilkan nomor Page, tautan anak kanan, serta informasi Cell pertama dan terakhir
    • Hanya sebagian Page di tiap level yang ditampilkan, dengan menyertakan Page pertama dan terakhir
    • Root Page berada di level pertama
  • Perintah untuk membuat gambar dari dump adalah sebagai berikut
    • php bin/console app:render-index --dumpIndexPath=dump.txt --outputImagePath=image.webp

Bentuk indeks yang berubah sesuai jumlah record

  • Struktur diperiksa dengan membuat tabel column1 INT NOT NULL, membuat indeks column1 ASC, lalu mengubah jumlah record
  • Indeks dengan 1 record terdiri dari 1 level, 1 Page, dan 1 Cell
  • Indeks dengan 1.000 record juga dibuat dan divisualisasikan dengan cara yang sama
  • Indeks dengan 1.000.000 record memiliki struktur berikut
    • 3 level
    • 2.930 Pages
    • 1.000.000 Cells
  • Karena data ditambahkan secara berurutan, saat rowId = 1, column1 = 1

Arah pengurutan dan indeks ekspresi

  • Untuk data yang sama, dibuat idx_asc dan idx_desc untuk membandingkan indeks ASC/DESC
  • Indeks ASC sama seperti indeks sebelumnya karena pengurutan default adalah ASC
    • Item dengan rowId=1.000.000, column1=1.000.000, payload=1.000.000 berada di Cell terakhir pada Page paling kanan
    • Item dengan rowId=1, column1=1, payload=1 berada di Cell pertama pada Page paling kiri
  • Indeks DESC ditempatkan sebaliknya
    • Item dengan rowId=1, column1=1, payload=1 berada di Cell terakhir pada Page paling kanan
    • Item dengan rowId=1.000.000, column1=1.000.000, payload=1.000.000 berada di Cell pertama pada Page paling kiri
  • Indeks berbasis ekspresi menyimpan string yang dihasilkan oleh ekspresi
    • Contohnya membuat indeks ASC dengan mengekstrak $.timestamp dari teks JSON, lalu mengubahnya menggunakan strftime('%Y-%m-%d %H:%M:%S', ..., 'unixepoch')
    • Ekspresi yang lebih kompleks juga dapat digunakan, dan indeks hanya menyimpan hasilnya

NULL, Partial Index, dan multi-kolom

  • SQLite mendukung indeks UNIQUE yang mencakup nilai NULL
    • Contohnya memasukkan nilai 1, banyak NULL, dan 1000000, lalu menjalankan CREATE UNIQUE INDEX idx ON table_test (column1 ASC)
    • Indeks yang divisualisasikan tampak seperti hanya menyimpan nilai non-NULL
  • Partial Index dengan kondisi WHERE column1 IS NOT NULL memfilter nilai NULL
    • Indeks ini hanya berisi satu Page
    • Ini menghasilkan pencarian yang lebih cepat dibandingkan contoh UNIQUE sebelumnya
  • Indeks multi-kolom menyimpan semua data field secara berurutan di dalam Cell
    • Contohnya adalah indeks (column1 ASC, column2 ASC)
    • Dalam visualisasi, field dipisahkan dengan titik dua :

Waktu pembuatan indeks dan efek rekonstruksi

  • Dibandingkan kasus ketika indeks dibuat sebelum data dimasukkan dan ketika indeks dibuat setelah semua data dimasukkan
  • Saat data baru ditambahkan, tree harus melakukan rebalance sendiri
  • Membuat indeks sekaligus untuk data yang sudah ada bisa jauh lebih efisien
  • Kedua indeks terlihat mirip, tetapi indeks kedua dengan jumlah Page lebih sedikit bisa lebih cepat
  • Hasil perbandingan untuk 1.000.000 Cells adalah sebagai berikut
Kategori Total Pages Total Cells
Dibuat sebelum insert 3342 1000000
Dibuat setelah insert 2930 1000000
  • Optimasi serupa dapat dilakukan dengan VACUUM atau REINDEX
    • VACUUM membuat ulang indeks dan tabel beserta datanya
    • REINDEX idx hanya membuat ulang indeks
  • Dalam contoh, kedua perintah mengurangi jumlah Page dari 3342 menjadi 2930

Penyimpanan indeks berdasarkan tipe data

  • Untuk data teks, string pendek disimpan langsung di Cell indeks, tetapi teks panjang harus disimpan secara terpisah
    • Contohnya memasukkan text-1 hingga text-1000000 dan membuat indeks column1 ASC
    • Dapat dilihat bahwa string sebenarnya disimpan langsung di indeks
  • Data REAL juga disimpan dalam indeks dan divisualisasikan
    • Contohnya menggunakan nilai 1.14, 2.14, ..., 1000000.14
  • Indeks komposit yang menggunakan integer dan teks bersama-sama juga diperiksa
    • Contohnya membuat indeks (column1 ASC, column2 ASC) pada tabel (column1 INT, column2 TEXT)
    • Integer dan string disimpan bersama dalam Cell yang sama sesuai urutan yang ditentukan saat membuat indeks

Cara mereproduksi dan pekerjaan berikutnya

  • Eksperimen ini menunjukkan bagaimana indeks SQLite distrukturkan, bagaimana data record disimpan di memori, serta bagaimana B-Tree menyusun dan mengakses data
  • Visualisasi digunakan untuk menganalisis dan membandingkan berbagai indeks
  • Semua contoh dapat direproduksi dengan perintah berikut
    • docker run -it --rm -v "$PWD":/app/data --platform linux/x86_64 mrsuh/sqlite-index bash
    • sh bin/test-index.sh
  • Kode dan contoh tersedia di mrsuh/sqlite-index
  • Pekerjaan berikutnya adalah visualisasi pencarian berbasis indeks dan eksplorasi beberapa query SQL

Bacaan terkait

1 komentar

 
GN⁺ 2024-11-16
Komentar di Hacker News

  • Setiap baris di tabel SQLite pada dasarnya memiliki rowId unik, dan dikatakan bertindak seperti primary key jika tidak ada primary key eksplisit, tetapi sebenarnya rowid tetap digunakan meskipun ada primary key
    Akan menarik kalau indeks primary key pada tabel WITHOUT ROWID divisualisasikan. Indeks semacam itu khususnya menarik
    Meski dua indeks terlihat mirip, bukan berarti indeks kedua langsung lebih cepat hanya karena jumlah halamannya lebih sedikit. Yang penting adalah tinggi tree, lalu setelah menemukan nilai di indeks, apakah sisa data harus dibaca dari tabel terpisah (rowid), atau datanya sudah ada langsung seperti pada WITHOUT ROWID. Perbedaannya besar terutama pada range query seperti where 50 <= col <= 100

    • Kalau hanya melihat satu kali akses, tinggi tree memang tepat, tetapi jika indeks sering diakses, ukuran total juga bisa sangat penting untuk cache hit rate
    • Pernyataan bahwa rowid dipakai meskipun ada primary key punya satu pengecualian. Jika membuat INTEGER PRIMARY KEY, SQLite akan menggunakan ini sebagai gantinya [1]
      [1]: https://sqlite.org/rowidtable.html

  • SQLite cukup unik dalam hampir semua cara pemrosesannya, dan menurut saya terutama dalam pemrosesan query
    SQLite cenderung lebih memilih kesederhanaan daripada performa, sehingga sering mengimplementasikan sesuatu dengan cara yang berbeda dari database lain yang pernah saya tangani. SQLite bersaing bukan dengan database lain, melainkan dengan file JSON/XML untuk penyimpanan persisten. Jadi melihat implementasi SQLite tidak banyak memberi tahu bagaimana database sebenarnya melakukan hal yang sama

    • SQLite bersaing dengan keduanya. Jelas SQLite dipakai sebagai penyimpanan persisten lokal, tetapi dalam situasi yang tidak membutuhkan proses server terpisah, ia juga bersaing dengan sistem manajemen basis data relasional lain
      Itu memang berarti kebutuhannya sangat berbeda, tetapi penggunaannya tidak hanya berhenti sebagai pengganti file JSON/XML
    • SQLite adalah database engine sungguhan. Mungkin maksudnya lebih ke tidak bersaing dengan server database
    • Cara server sistem manajemen basis data lain menangani storage dan indeks tidak terlalu jauh berbeda. Prinsipnya hampir sama, terutama ketika SQLite berjalan dalam mode WAL

  • Situs webnya begitu nyaman dibaca sampai saya benar-benar jadi ingin membacanya

    • Saat dilihat di iPhone, ukuran font teks utama terlalu besar. Teks penting di dalam diagram jauh lebih kecil, jadi terasa canggung karena untuk membaca teks utama ponsel harus dijauhkan dari wajah, lalu untuk membaca diagram harus didekatkan lagi
    • Sangat nyaman bisa melihat konten tanpa iklan yang padat. Tulisannya juga sangat bagus

  • “indexes” adalah bentuk present tense orang ketiga tunggal dari verba “to index” sekaligus bentuk jamak nomina dari “index”. Sementara itu “indices” adalah bentuk jamak tradisional, dan banyak dipakai terutama dalam konteks matematika dan sains
    Dalam bahasa Inggris umum, “indexes” lazim dipakai, tetapi di bidang teknis ada kalanya indices lebih disukai demi ketepatan linguistik. Dalam konteks seperti ini, penggunaan “indices” meningkatkan kejelasan dengan membedakan tindakan pengindeksan dari bentuk jamak indeks

    • Keduanya boleh (https://www.nasdaq.com/articles/indexes-or-indices-whats-the...). Dokumentasi SQLite dan PostgreSQL juga menggunakan indexes sebagai contoh representatif
    • Coba bentuk jamak dari “time series”; itu tidak mudah
      Di Finlandia, saya pernah melihat “time series” dipakai sebagai bentuk jamak, dan “time serie” sebagai bentuk tunggal
    • Saya tidak tahu atas otoritas apa Anda mengatakan itu
      Semua sistem manajemen basis data relasional utama menggunakan istilah indexes
    • Tergantung pembaca sasaran. Jika ditujukan untuk akademisi, gunakan indices; jika ditujukan untuk pembaca umum, “indices” bisa terlihat sok

  • Saya juga ingin melihat bagaimana PostgreSQL melakukan hal yang sama. Sepertinya ada banyak hal yang bisa dipelajari lewat perbandingan

  • Untuk melihat berbagai tata letak dengan lebih sedikit usaha, bisa juga dibuat agar menghasilkan TGF untuk yEd