Pengantar Query Processing & Ukuran Biaya (Cost)

Back to IF3140 Sistem Basis Data

Topic

Questions/Cues

• Apa tiga langkah dasar query processing?

• Apa itu evaluation plan?

• Apa komponen biaya utama dalam query?

• Bagaimana biaya query diukur secara sederhana?

Tiga Langkah Dasar Query Processing

Proses eksekusi sebuah query di dalam DBMS secara umum dibagi menjadi tiga langkah utama:

1. Parsing and Translation: Query SQL dari pengguna diterjemahkan ke dalam bentuk internal, biasanya ekspresi aljabar relasional. Parser juga akan memeriksa sintaks dan memverifikasi nama-nama relasi.

2. Optimization: Optimizer mencari rencana evaluasi (evaluation plan) dengan estimasi biaya terendah dari berbagai alternatif ekspresi yang ekuivalen. Proses ini menggunakan informasi statistik dari katalog database.

3. Evaluation: Query-execution engine mengambil rencana evaluasi yang sudah dioptimalkan, menjalankannya, dan mengembalikan hasil query kepada pengguna.

Evaluation Plan

Sebuah Evaluation Plan adalah sebuah ekspresi aljabar relasional yang diberi anotasi detail. Anotasi ini mendefinisikan strategi evaluasi secara spesifik, seperti algoritma apa yang harus digunakan untuk setiap operasi (misal, menggunakan index scan atau linear scan).

Pengukuran Biaya Query

Biaya sebuah query umumnya diukur sebagai total waktu yang dibutuhkan untuk menjawab query tersebut. Dari berbagai faktor seperti akses disk, CPU, dan jaringan, akses disk adalah komponen biaya yang paling dominan. Oleh karena itu, estimasi biaya biasanya berfokus pada aktivitas disk.

Secara sederhana, biaya diukur berdasarkan:

• Jumlah transfer blok (b): Berapa banyak blok yang harus dibaca/ditulis dari/ke disk.
• Waktu transfer blok ($t_t$)
• Jumlah seek (S): Berapa kali lengan disk harus bergerak.
• Waktu seek ($t_s$)

Dengan rumus, $\text{cost}=b\times t_t+t_s\times S$ Dengan catatan, biaya CPU dan biaya untuk menulis hasil akhir ke disk seringkali diabaikan dalam formula estimasi untuk menyederhanakan perhitungan.

Summary

Query Processing terdiri dari tiga langkah: Parsing/Translation (mengubah SQL ke aljabar relasional), Optimization (memilih evaluation plan termurah), dan Evaluation (menjalankan rencana tersebut). Biaya sebuah evaluation plan diukur terutama berdasarkan biaya akses disk, yang disederhanakan menjadi jumlah transfer blok dan seek yang dibutuhkan untuk mengeksekusi rencana tersebut.

Additional Information (Optional)

Mengapa Biaya CPU Diabaikan?

Dalam sistem database tradisional, waktu yang dibutuhkan untuk operasi mekanis pada disk (seek time ~milidetik) jauh lebih besar daripada waktu untuk operasi CPU (clock cycle ~nanodetik). Perbedaannya bisa mencapai ribuan hingga jutaan kali lipat. Oleh karena itu, mengoptimalkan jumlah I/O disk memberikan dampak performa yang jauh lebih besar daripada mengoptimalkan beberapa siklus CPU. Namun, dengan munculnya in-memory database di mana semua data berada di RAM, biaya CPU menjadi jauh lebih relevan dalam estimasi biaya.

Worst-Case Estimation

Saat menghitung biaya, optimizer seringkali menggunakan estimasi kasus terburuk (worst-case). Misalnya, ia akan mengasumsikan bahwa tidak ada blok yang dibutuhkan sudah tersedia di buffer memori dan semuanya harus dibaca dari disk. Ini dilakukan karena status buffer saat query dijalankan sangat dinamis dan sulit diprediksi. Menggunakan worst-case memberikan jaminan batas atas performa yang lebih dapat diandalkan.