Evaluasi Ekspresi

Back to IF3140 Sistem Basis Data

Topic

Evaluasi Ekspresi: Materialization vs Pipelining

Questions/Cues

• Apa itu Evaluasi Ekspresi?

• Apa itu strategi Materialization?

• Apa analogi Materialization?

• Apa kelebihan & kekurangan Materialization?

• Apa itu Double Buffering?

• Apa itu strategi Pipelining?

• Apa analogi Pipelining?

• Apa kelebihan & kekurangan Pipelining?

• Apa dua model eksekusi Pipelining?

• Apa itu Demand-Driven Pipelining?

• Apa itu Producer-Driven Pipelining?

• Bagaimana implementasi Demand-Driven Pipelining?

• Apa itu “Blocking Algorithm”?

• Bagaimana Pipelining menangani algoritma Blocking?

Reference Points

• Slides 46-53

Gambaran Umum Evaluasi Ekspresi

Setelah query di-parse dan dioptimasi, query execution engine mendapatkan sebuah expression tree (pohon ekspresi relasional aljabar). Tugas engine adalah mengeksekusi pohon ini untuk mendapatkan hasil akhir. Ada dua strategi utama untuk mengeksekusi pohon ini:

1. Materialization

2. Pipelining

1. Materialization

Materialization adalah pendekatan evaluasi di mana setiap operasi dalam pohon dieksekusi satu per satu, dimulai dari level terendah (daun).

• Proses: Hasil dari setiap operasi ditulis (dimaterialisasi) ke disk sebagai relasi sementara (temporary relation).

• Operasi di level berikutnya (induknya) kemudian akan membaca relasi sementara ini dari disk sebagai inputnya.

• Ini terus berlanjut hingga operasi di root (akar) pohon selesai dan menghasilkan jawaban akhir.

Kelebihan dan Kekurangan Materialization

• Kelebihan:

  • Selalu Berlaku (Always Applicable): Metode ini sederhana dan selalu bisa digunakan untuk operasi apa pun.

• Kekurangan:

  • Biaya Tinggi: Sangat mahal karena melibatkan banyak operasi I/O (Input/Output) ke disk. Biaya totalnya adalah jumlah biaya semua operasi ditambah biaya untuk menulis dan membaca kembali semua relasi sementara dari disk.

Optimasi: Double Buffering

Untuk mengurangi waktu tunggu saat menulis ke disk, double buffering bisa digunakan.

• Sistem menggunakan dua buffer output untuk satu operasi.

• Saat buffer pertama penuh dan sedang dalam proses ditulis ke disk, operasi dapat langsung mulai mengisi buffer kedua.

• Ini memungkinkan overlap (tumpang tindih) antara waktu komputasi (mengisi buffer) dan waktu disk I/O (menulis buffer), sehingga mengurangi total waktu eksekusi.

2. Pipelining

Pipelining adalah pendekatan evaluasi di mana beberapa operasi dieksekusi secara bersamaan (simultan) dalam sebuah “aliran data”.

• Proses: Hasil (tuple) dari satu operasi tidak disimpan ke disk. Sebaliknya, tuple tersebut langsung diteruskan (di-passing) ke operasi induknya (parent) sebagai input.

• Operasi induk langsung memproses tuple yang baru diterimanya dan meneruskan hasilnya lagi ke induknya, dan begitu seterusnya.

Kelebihan dan Kekurangan Pipelining

• Kelebihan:

  • Jauh Lebih Murah: Jauh lebih efisien daripada materialization karena menghilangkan biaya I/O disk untuk menyimpan dan membaca relasi sementara.

• Kekurangan:

  • Tidak Selalu Bisa: Pipelining tidak bisa diterapkan pada semua algoritma. Algoritma yang bersifat “blocking” (membutuhkan semua input sebelum bisa menghasilkan output pertama) tidak dapat di-pipeline. Contohnya: sort atau hash-join (pada fase build).

Model Eksekusi Pipelining

Ada dua cara untuk mengelola aliran data dalam pipeline:

1. Demand-Driven (Lazy Evaluation / Pull Model):

   • Operasi di level atas (root) “meminta” (requests) satu tuple dari anaknya.

   • Anak tersebut kemudian meminta tuple dari anak-anaknya, dan begitu seterusnya ke bawah.

   • Setiap operasi harus menyimpan “state” (status/posisi terakhirnya) agar tahu tuple mana yang harus dikirim selanjutnya saat diminta lagi.

2. Producer-Driven (Eager Pipelining / Push Model):

   • Operasi di level bawah (daun) “secara antusias” (eagerly) menghasilkan tuple dan “mendorong” (pushes) ke atas ke induknya.

   • Sebuah buffer (antrian) diletakkan di antara setiap operator (anak dan induk).

   • Anak memproduksi tuple dan menaruhnya di buffer. Induk mengambil tuple dari buffer untuk diproses.

   • Jika buffer penuh, operator anak akan berhenti (wait) sampai ada ruang kosong.

Implementasi: Model Iterator (untuk Demand-Driven)

Implementasi paling umum untuk demand-driven pipelining adalah menggunakan model iterator. Setiap operator (operasi) di pohon query diimplementasikan sebagai sebuah iterator yang memiliki tiga metode utama:

1. open(): Melakukan inisialisasi. (Contoh: untuk file scan, open() akan menyiapkan pointer ke awal file. Untuk merge join, open() akan menyortir relasi input terlebih dahulu).

2. next(): Menghasilkan satu tuple output berikutnya. Ini adalah inti dari pipeline. Saat next() dipanggil, operator akan memanggil next() pada anak-anaknya seperlunya untuk mendapatkan input yang dibutuhkan. (Contoh: untuk file scan, next() akan membaca tuple berikutnya dan memajukan pointer file).

3. close(): Membersihkan state setelah semua tuple habis.

Pipelining dan “Blocking Algorithms”

Beberapa algoritma secara alami bersifat blocking—mereka tidak bisa menghasilkan output pertama sampai mereka melihat semua data input. Contohnya, sort (tidak bisa tahu tuple minimum sebelum melihat semua tuple) atau hash-join (harus membangun seluruh hash table dari relasi build terlebih dahulu).

Untuk algoritma ini, pipeline “terputus”. Sistem terpaksa menggunakan materialization di titik tersebut (misalnya, hasil sort ditulis ke disk, lalu dibaca lagi oleh operator di atasnya).

Namun, beberapa algoritma varian (seperti hybrid hash-join) dirancang agar “setidaknya” bisa menghasilkan beberapa output secara on-the-fly (misalnya, hasil join dari partisi 0 yang ada di memori) sambil tetap memproses sisa datanya.

Summary

Evaluasi ekspresi query dapat dilakukan dengan dua cara utama: Materialization dan Pipelining. Materialization adalah pendekatan langkah-demi-langkah di mana setiap hasil operasi disimpan sementara ke disk, sebuah metode yang selalu bisa diterapkan namun memakan biaya I/O yang tinggi. Sebaliknya, Pipelining mengalirkan tuple antar operasi secara bersamaan tanpa menyimpannya ke disk, sehingga jauh lebih efisien. Pipelining dapat diimplementasikan dengan model demand-driven (pull/lazy) menggunakan iterator (open, next, close) atau producer-driven (push/eager) menggunakan buffer. Namun, Pipelining tidak bisa diterapkan pada blocking algorithm seperti sort atau hash-join yang harus memproses seluruh inputnya terlebih dahulu.

Additional Information

Analisis Mendalam: Iterator vs. Buffering (Pull vs. Push)

• Model Iterator (Demand-Driven/Pull): Model ini, yang dipopulerkan oleh sistem “Volcano”, sangat elegan. Kontrol alirannya sederhana: pemanggil (parent) memegang kendali penuh kapan ia ingin memproses data. Ini menyederhanakan logika query plan dan error handling. Namun, pemanggilan fungsi next() yang berulang-ulang (satu per tuple, dari atas sampai bawah pohon) dapat menimbulkan overhead CPU (disebut function call overhead).

• Model Buffering (Producer-Driven/Push): Model ini sering digunakan dalam sistem stream processing modern (seperti Apache Flink) dan juga sistem database yang berorientasi pada throughput (disebut juga vectorized processing atau batch processing). Operator “mendorong” sekumpulan (batch/vector) tuple sekaligus ke buffer, bukan satu per satu. Ini secara drastis mengurangi function call overhead dan memanfaatkan CPU cache dengan lebih baik, sehingga throughput data menjadi jauh lebih tinggi.

Analisis Mendalam: Blocking (Pipeline Breakers)

Operator yang “memutus” pipeline (disebut pipeline breakers) adalah titik kritis dalam optimasi query.

• Non-Blocking (Pipelined Penuh): $\sigma$ (Selection), $\Pi$ (Projection). Keduanya bisa memproses tuple satu per satu saat mereka tiba.

• Full Blocking (Harus Materialisasi): Sort, GROUP BY/Aggregation (yang berbasis sort), Hash Join (pada fase build), Merge Join (pada fase sort). Mereka harus mengkonsumsi seluruh input sebelum bisa menghasilkan satu output pun.

• Partial Blocking (Hybrid): Hash Join (pada fase probe) dan Hybrid Hash Join. Mereka bisa mulai menghasilkan output setelah fase build selesai (untuk Hash Join standar) atau bahkan selama fase probe untuk partisi pertama (untuk Hybrid Hash Join).

Query optimizer modern akan berusaha keras untuk meminimalkan jumlah pipeline breakers dalam sebuah execution plan, atau setidaknya menempatkannya di titik di mana data yang harus diproses sudah sekecil mungkin (misalnya, setelah operasi selection yang sangat selektif).

Eksplorasi Mandiri

• Cari tahu tentang Vectorized Execution (atau Batch-Oriented Processing) yang digunakan oleh sistem seperti MonetDB atau ClickHouse. Bagaimana model ini berhubungan dengan Pipelining? (Petunjuk: Ini adalah varian dari model producer-driven yang memproses data dalam batch atau vector, bukan tuple per tuple).

• Baca paper “Volcano - An Extensible and Parallel Query Evaluation System” oleh Goetz Graefe. Ini adalah paper fundamental yang memperkenalkan model iterator open-next-close ke dunia database.

Sumber & Referensi Lanjutan:

• Buku: Silberschatz, Korth, Sudarshan: “Database System Concepts”, 7th Edition, Chapter 15.

• Paper: Graefe, G. (1994). Volcano - An Extensible and Parallel Query Evaluation System. IEEE Transactions on Knowledge and Data Engineering.