Bahasa Data dengan SQL Query Engine untuk Database Terdistribusi

Bagian ini mengkaji lapisan teratas: SQL engine yang menerjemahkan kueri deklaratif menjadi tindakan imperatif. Setelah sebelumnya kita membahas Storage Engine, Konsensus menggunakan Raft, dan Jaminan Transaksi dengan ACID/MVCC.

Bahasa Data (SQL Query Engine) untuk Database Terdistribusi.

Kueri Deklaratif (Declarative Query) adalah cara Anda sebagai pengguna menyatakan apa yang Anda inginkan, tanpa perlu merinci bagaimana cara mendapatkannya. SQL adalah bahasa yang sepenuhnya deklaratif.

Contoh SQL

SELECT nama, kota FROM pelanggan WHERE negara = ‘Indonesia’ AND saldo > 1000;

Dalam kueri ini, Anda hanya mendeskripsikan hasil akhir yang Anda inginkan:

• Saya mau kolom nama dan kota.

• Dari tabel pelanggan.

• Dengan syarat negara adalah ‘Indonesia’ dan saldo di atas 1000.

Anda tidak memberi tahu database bagaimana cara melakukannya. Anda tidak memerintahkan: “Buka file tabel pelanggan, baca baris per baris, periksa kolom negara, lalu periksa kolom saldo, simpan yang cocok, lalu ekstrak kolom nama dan kota.”

Tindakan Imperatif (Imperative Actions) adalah serangkaian langkah-langkah spesifik dan berurutan yang harus dilakukan untuk mencapai suatu hasil. Ini adalah resepnya, bukan nama masakannya. Dalam konteks database, rencana eksekusi (execution plan) yang dihasilkan oleh query planner adalah tindakan imperatif tersebut.

• Untuk kueri deklaratif di atas, sebuah rencana eksekusi (tindakan imperatif) bisa terlihat seperti ini (disederhanakan):

  1. Gunakan indeks pada kolom negara untuk menemukan semua baris di mana negara = ‘Indonesia’.

  2. Dari hasil langkah 1, lakukan filter untuk hanya menyertakan baris di mana saldo > 1000.

  3. Untuk setiap baris yang lolos filter, ambil (proyeksikan) hanya nilai dari kolom nama dan kota.

  4. Kirimkan hasilnya kembali ke klien.

Jadi, tugas query planner adalah mengambil permintaan “apa” (deklaratif) dari Anda dan secara cerdas mengubahnya menjadi serangkaian langkah “bagaimana” (imperatif) yang paling efisien.

Alur Pemrosesan Kueri SQL

Setiap kueri SQL melewati tiga tahap kanonis (canonical stages adalah langkah standar yang hampir secara universal dilalui oleh setiap kueri SQL di dalam sebuah database) sebelum menghasilkan hasil.

Tahap Parser

• Input: String SQL

• Tugas Utama: Pemeriksaan Sintaks & Semantik

• Output: Abstract Syntax Tree (AST)

Tahap Planner/Optimizer

• Input: AST

• Tugas Utama: Menghasilkan & Menilai Rencana Eksekusi

• Output: Rencana Fisik Optimal

Tahap Executor

• Input: Rencana Fisik

• Tugas Utama: Mengiterasi rencana dan mengambil data

• Output: Set Hasil

Deskripsi dari tugasnya:

• Parser: Mengambil string SQL mentah dan mengubahnya menjadi representasi terstruktur yang disebut Abstract Syntax Tree (AST). Tahap ini memeriksa apakah kueri tersebut secara sintaksis benar menurut dialek SQL yang digunakan.

• Planner/Optimizer: Mengambil AST dan menghasilkan rencana eksekusi fisik yang efisien. Ini adalah bagian paling kompleks dari query engine. Planner mempertimbangkan berbagai cara untuk mengeksekusi kueri—misalnya, menggunakan pemindaian tabel penuh versus pemindaian indeks, algoritma join yang berbeda (misalnya, nested loop join vs. hash join), dan urutan operasi. Optimizer berbasis biaya (cost-based) akan memperkirakan “biaya” (dalam hal I/O disk dan penggunaan CPU) dari setiap rencana yang memungkinkan dan memilih yang termurah.

• Executor: Mengambil rencana eksekusi optimal dari planner dan menjalankannya. Ini adalah komponen yang benar-benar mengambil data dari storage engine, memfilternya, menggabungkannya, dan menghasilkan set hasil akhir yang dikirim kembali ke klien.

Rencana Fisik adalah cetak biru atau resep langkah-demi-langkah yang sangat detail yang dibuat oleh query optimizer untuk dieksekusi oleh executor. Rencana ini memberitahu database bagaimana cara secara fisik mengambil, menggabungkan, dan memfilter data dari disk atau memori untuk memenuhi permintaan kueri SQL Anda.

Perbedaan Rencana Logis vs. Rencana Fisik

Pikirkan proses ini seperti merencanakan perjalanan:

• Kueri SQL Anda (Deklaratif): “Saya ingin pergi dari Jakarta ke Tokyo.” Anda menyatakan apa yang Anda mau, bukan bagaimana caranya.

• Rencana Logis (Logical Plan): Ini adalah representasi abstrak dari permintaan Anda. Secara konseptual, ini adalah “Perjalanan(Jakarta, Tokyo)”. Rencana ini hanya menangkap esensi dari apa yang harus dilakukan, tanpa detail implementasi. Ia belum memutuskan apakah akan naik pesawat, kapal, atau mobil.

• Rencana Fisik (Physical Plan): Ini adalah serangkaian instruksi konkret dan dapat dieksekusi. Optimizer akan mempertimbangkan berbagai opsi (rute penerbangan, maskapai, jadwal) dan memilih yang terbaik. Rencana Fisik bisa jadi:

  1. Naik taksi ke Bandara Soekarno-Hatta.

  2. Naik pesawat Garuda Indonesia GA874 ke Bandara Narita.

  3. Naik kereta Narita Express ke Stasiun Tokyo.

  Atau, bisa juga ada Rencana Fisik alternatif:

  1. Naik kereta bandara ke Soekarno-Hatta.

  2. Naik pesawat Japan Airlines JL726 ke Narita.

  3. Naik bus Limousine ke pusat kota Tokyo.

Optimizer memilih rencana fisik yang paling efisien (paling murah biayanya) untuk diberikan kepada Executor.

Hubungan dengan Planner dan Executor

• Planner/Optimizer: Menerima Rencana Logis (representasi abstrak dari kueri) dan menghasilkan banyak kemungkinan Rencana Fisik. Ia kemudian memperkirakan “biaya” (estimasi penggunaan CPU, I/O disk, memori) untuk setiap rencana fisik tersebut dan memilih satu dengan biaya terendah. Rencana Fisik optimal inilah yang diteruskan ke tahap selanjutnya.

• Executor: Menerima satu Rencana Fisik yang sudah terpilih. Tugasnya adalah menjalankan rencana tersebut langkah demi langkah, seperti mesin yang mengikuti instruksi dari sebuah cetak biru. Ia akan “berjalan” di pohon rencana, melakukan pemindaian, join, dan filter sesuai yang diperintahkan, hingga hasil akhir terbentuk dan dikirim kembali ke klien.

Model Eksekusi Volcano/Iterator

toydb menggunakan query engine berbasis iterator. Ini adalah implementasi dari

model Volcano¹, sebuah desain klasik dan elegan untuk eksekutor kueri. Dalam model ini, setiap operator dalam rencana eksekusi (misalnya, TableScan, Filter, Join) diimplementasikan sebagai sebuah “iterator”. Setiap iterator mengimplementasikan sebuah trait (antarmuka) yang memiliki metode next(). Metode next() mengembalikan baris berikutnya dalam set hasilnya, atau None jika tidak ada lagi baris.

Kueri dieksekusi dengan memanggil next() pada iterator akar dari pohon rencana. Iterator ini, pada gilirannya, akan memanggil next() pada iterator anaknya untuk mendapatkan data yang dibutuhkannya, dan seterusnya ke bawah pohon. Model ini sangat modular dan mudah untuk disusun.

Mengapa Disebut “Volcano”?

Nama ini berasal dari cara data “mengalir”. Dalam model ini, setiap operasi dalam rencana eksekusi (seperti TableScan, Filter, Join) diimplementasikan sebagai sebuah iterator. Setiap iterator memiliki metode next() yang dipanggil oleh iterator di atasnya. Data ditarik ke atas dari sumbernya (tabel di bagian bawah) melalui pohon operator hingga mencapai akar (hasil akhir), mirip seperti material yang dimuntahkan ke atas dari gunung berapi. Ini adalah model berbasis tarikan (pull-based).

Model ini disebut klasik karena merupakan salah satu desain fundamental pertama yang sangat modular dan dapat diperluas. Hampir semua sistem database relasional modern terinspirasi atau pada awalnya dibangun di atas prinsip-prinsip model Volcano.

Kelemahan utama model Volcano klasik adalah ia memproses data satu baris pada satu waktu (tuple-at-a-time). Setiap panggilan next() hanya mengembalikan satu baris, yang menyebabkan overhead pemanggilan fungsi yang tinggi. Model yang lebih modern dan dianggap lebih baik untuk perangkat keras saat ini adalah Eksekusi Vektorisasi (Vectorized Execution) atau Pemrosesan Batch (Batch Processing).

Penelusuran Kode: SQL di toydb

• Parsing (src/sql/parser/parser.rs): Sejalan dengan tujuan edukasinya untuk menunjukkan segalanya dari awal, toydb tidak menggunakan crate parser eksternal. Sebaliknya, ia mengimplementasikan parser rekursif turun (recursive descent parser) kustomnya sendiri. File parser.rs berisi logika untuk mengubah aliran token SQL menjadi Abstract Syntax Tree (AST). Ini adalah pilihan desain yang penting karena memungkinkan pelajar untuk melihat secara langsung bagaimana string kueri dianalisis dan diubah menjadi struktur data yang dapat dipahami oleh mesin.

• Planning & Optimization (src/sql/planner/): Logika untuk mengubah AST menjadi rencana eksekusi berada di modul ini.

  • planner.rs: Mengambil AST dari parser dan mengubahnya menjadi pohon rencana logis awal.

  • optimizer.rs: Mengambil rencana logis dan menerapkan optimisasi heuristik. Seperti yang disebutkan sebelumnya, ini adalah bentuk optimisasi berbasis aturan, seperti predicate pushdown, yang menyederhanakan rencana tanpa melakukan analisis biaya yang kompleks. Ini adalah pilihan pedagogis yang sangat baik.

• Execution (src/sql/execution/executor.rs): File ini berisi implementasi konkret dari model iterator Volcano. Di sini Anda akan menemukan berbagai struct (seperti Scan, Filter, Projection, Join) yang masing-masing mengimplementasikan trait Executor (yang setara dengan Iterator). Setiap executor membungkus executor anaknya dan menerapkan logikanya sendiri dalam metode next(), menarik baris satu per satu melalui pohon rencana.

Optimizer Heuristik adalah jenis query optimizer yang menggunakan serangkaian aturan praktis (rules of thumb) yang telah ditentukan sebelumnya untuk mengubah pohon kueri menjadi rencana eksekusi yang lebih baik. Optimizer ini tidak mencoba menghitung biaya absolut dari setiap kemungkinan rencana.

Perbedaannya dengan Optimizer Modern: Sebagian besar database produksi modern (seperti PostgreSQL, Oracle) menggunakan Cost-Based Optimizer (CBO) atau Optimizer Berbasis Biaya.

Pilihan toydb untuk menggunakan optimizer heuristik sederhana dan model iterator Volcano klasik adalah keputusan pedagogis kunci lainnya. Ini memperkenalkan pengguna pada prinsip-prinsip fundamental perencanaan dan eksekusi kueri tanpa kerumitan yang luar biasa dari mesin modern yang berbasis biaya, tervektorisasi, atau JIT-compiling. Ini memberikan model mental “prinsip pertama” yang solid tentang query engine.

1. Graefe, G. (1994). Volcano—An Extensible and Parallel Query Evaluation System. IEEE Transactions on Knowledge and Data Engineering.