Analisis Struktur Mesin SQL

• Mesin SQL adalah lapisan logis database yang bekerja di antara klien dan penyimpanan
• Penjelasan rinci tentang proses utama mesin SQL: parsing, binding, penyederhanaan plan, eksplorasi join dan evaluasi biaya, eksekusi, dan spooling hasil
  • Parsing mengubah kueri SQL menjadi abstract syntax tree (AST) yang terstruktur
  • Binding mencocokkan field dalam AST dengan simbol di katalog database saat ini
  • Penyederhanaan plan menormalkan sintaks SQL yang kompleks menjadi bentuk yang lebih sederhana untuk meningkatkan kecepatan eksekusi
  • Eksplorasi plan menelusuri berbagai variasi join, agregasi, dan window function untuk menemukan plan eksekusi terbaik
  • Eksekusi dan spooling hasil mengubah plan akhir ke bentuk yang dapat dieksekusi dan mengembalikan hasil ke klien

---

Gambaran umum mesin SQL

• Mesin SQL adalah lapisan perantara logis antara permintaan klien dan penyimpanan data
• Tahap utama
  • Parsing: mengubah kueri menjadi AST (abstract syntax tree)
  • Binding: menghubungkan identifier dalam AST ke simbol di katalog database
  • Plan Simplification: menyederhanakan beragam sintaks SQL menjadi bentuk plan yang terstandarisasi
  • Join Exploration & Costing: menelusuri berbagai urutan join dan mengevaluasi biayanya
  • Execution: menjalankan kueri menggunakan plan eksekusi terbaik
  • Spooling Results: mengembalikan hasil ke klien

Parsing

• Parsing adalah proses melakukan tokenisasi kueri input dan mengubahnya menjadi AST
• Parser rekursif kanan mudah dipahami dan di-debug, tetapi menggunakan banyak memori stack
• Parser rekursif kiri (berbasis Yacc) lebih efisien secara memori, tetapi memerlukan logika yang lebih kompleks
• Dolt menggunakan parser rekursif kiri untuk mendukung parsing yang cepat
• Jika parsing berhasil, struktur AST akan sesuai dengan aturan Yacc

Binding

• Binding adalah proses menghubungkan field dalam AST ke simbol tabel dan kolom yang sebenarnya di database
• Konsep utama
  • Definisi tabel: berperan sebagai sumber data
  • Definisi kolom: merujuk ke kolom tertentu dari sumber tabel
  • Alias: menggunakan nilai skalar baik sebagai sumber maupun sebagai sink
  • Subkueri skalar: berbagi scope induk sambil melakukan name binding
• Hasil binding adalah pembuatan node plan eksekusi dalam format sql.Node

Penyederhanaan plan

• Proses mengubah berbagai ekspresi SQL menjadi bentuk ternormalisasi untuk membantu optimasi eksekusi
• Optimasi yang umum
  • Filter Pushdown: menghapus baris yang tidak diperlukan
  • Column Pruning: menghapus kolom yang tidak diperlukan
• Optimasi plan join juga dilakukan melalui transformasi seperti subquery decorrelation

Type coercion

• Type coercion adalah proses mengubah tipe ekspresi secara otomatis sesuai konteks
• Tipe dapat berubah tergantung konteks seperti WHERE, INSERT, dan lainnya
• Dolt menangani konversi tipe secara bertahap pada tahap binding

Eksplorasi join

• Eksplorasi join adalah proses menghasilkan dan meninjau berbagai urutan join
• Dua strategi eksplorasi
  • Backtracking top-down: hanya menelusuri urutan join yang valid
  • Dynamic programming (DP) bottom-up: mencoba semua kombinasi untuk menemukan urutan join optimal
• Menggunakan struktur Memo untuk mengelola status perantara secara efisien

Functional dependencies

• Biaya dapat meningkat tajam saat melakukan join pada 5 tabel atau lebih
• Biaya eksplorasi dapat dikurangi dengan memanfaatkan relasi 1:1, seperti join berbasis primary key (PK)
• Optimasi dilakukan dengan terlebih dahulu memprioritaskan LOOKUP_JOIN

Ringkasan intermediate representation (IR)

• Ringkasan 3 tahap IR yang telah dibahas sejauh ini
  • AST: penataan token
  • Binding berbasis scope: validasi referensi kolom
  • Memo: representasi untuk eksplorasi join dan evaluasi biaya

Evaluasi biaya join

• Evaluasi biaya join adalah proses memperkirakan biaya eksekusi untuk semua plan yang mungkin
• Faktor biaya
  • Ukuran tabel input
  • Ukuran tabel hasil
  • Jenis operator join (LOOKUP_JOIN, HASH_JOIN, dll.)
• Dolt mengevaluasi biaya berdasarkan statistik tabel yang akurat (histogram)

Join hints

• Sistem mencoba menerapkan strategi join terlebih dahulu berdasarkan hint yang diberikan pengguna
• Hint yang saling bertentangan atau tidak tepat akan diabaikan

Eksekusi

• Plan terbaik diubah menjadi struktur iterator (Volcano Iterator) yang benar-benar dapat dieksekusi
• Karakteristik
  • Iterator non-materializing: langsung mengembalikan baris
  • Iterator materializing: mengumpulkan semua baris lalu mengembalikannya
• Referensi kolom dipetakan berdasarkan offset indeks sebelum eksekusi

I/O dan spooling hasil

• Hasil eksekusi diubah ke format protokol MySQL lalu dikirim ke klien
• Dalam beberapa kasus, hasil dibaca langsung dari lapisan penyimpanan key-value (KV) untuk optimasi
• Pemrosesan batch dan penggunaan ulang buffer meningkatkan kecepatan pemrosesan dan efisiensi memori

Rencana ke depan

• Dolt pada dasarnya menggunakan eksekusi berbasis baris (row-based execution) di server lokal
• Dolt mendukung penyusunan plan eksekusi optimal dengan memanfaatkan 3 tahap intermediate representation (IR) seperti AST, binding berbasis scope, dan eksplorasi join melalui struktur Memo
• Strategi join optimal ditentukan melalui Join Search dan Join Costing
• Ke depan, peningkatan performa direncanakan melalui integrasi IR dan optimasi penggunaan ulang memori