Optimasi Kueri dalam Sistem Terpusat
Setelah jalur akses alternatif untuk komputasi ekspresi aljabar relasional diturunkan, jalur akses optimal ditentukan. Pada bab ini, kita akan melihat optimasi query dalam sistem terpusat sedangkan pada bab berikutnya kita akan mempelajari optimasi query dalam sistem terdistribusi.
Dalam sistem terpusat, pemrosesan kueri dilakukan dengan tujuan berikut -
Meminimalkan waktu respons kueri (waktu yang dibutuhkan untuk menghasilkan hasil untuk kueri pengguna).
Maksimalkan throughput sistem (jumlah permintaan yang diproses dalam jangka waktu tertentu).
Kurangi jumlah memori dan penyimpanan yang diperlukan untuk pemrosesan.
Tingkatkan paralelisme.
Query Parsing dan Terjemahan
Awalnya, kueri SQL dipindai. Kemudian diurai untuk mencari kesalahan sintaksis dan ketepatan tipe data. Jika kueri melewati langkah ini, kueri akan diuraikan menjadi blok kueri yang lebih kecil. Setiap blok kemudian diterjemahkan ke ekspresi aljabar relasional yang setara.
Langkah-langkah untuk Pengoptimalan Kueri
Pengoptimalan kueri melibatkan tiga langkah, yaitu pembuatan pohon kueri, pembuatan rencana, dan pembuatan kode rencana kueri.
Step 1 − Query Tree Generation
Pohon kueri adalah struktur data pohon yang mewakili ekspresi aljabar relasional. Tabel kueri direpresentasikan sebagai node daun. Operasi aljabar relasional direpresentasikan sebagai node internal. Akar mewakili kueri secara keseluruhan.
Selama eksekusi, node internal dieksekusi setiap kali tabel operannya tersedia. Node tersebut kemudian diganti dengan tabel hasil. Proses ini berlanjut untuk semua node internal sampai node root dijalankan dan diganti dengan tabel hasil.
Sebagai contoh, mari kita pertimbangkan skema berikut -
KARYAWAN
| EmpID | EName | Gaji | DeptNo | Tanggal Bergabung |
DEPARTEMEN
| DNo | DName | Lokasi |
Contoh 1
Mari kita pertimbangkan kueri sebagai berikut.
$$ \ pi_ {EmpID} (\ sigma_ {EName = \ small "ArunKumar"} {(EMPLOYEE)}) $$
Pohon kueri terkait akan menjadi -
Contoh 2
Mari kita pertimbangkan kueri lain yang melibatkan gabungan.
$ \ pi_ {EName, Gaji} (\ sigma_ {DName = \ small "Marketing"} {(DEPARTMENT)}) \ bowtie_ {DNo = DeptNo} {(EMPLOYEE)} $
Berikut adalah pohon kueri untuk kueri di atas.
Step 2 − Query Plan Generation
Setelah pohon kueri dibuat, rencana kueri dibuat. Rencana kueri adalah pohon kueri yang diperluas yang menyertakan jalur akses untuk semua operasi di pohon kueri. Jalur akses menentukan bagaimana operasi relasional di pohon harus dilakukan. Misalnya, operasi pemilihan dapat memiliki jalur akses yang memberikan detail tentang penggunaan indeks pohon B + untuk pemilihan.
Selain itu, rencana kueri juga menyatakan bagaimana tabel perantara harus diteruskan dari satu operator ke operator berikutnya, bagaimana tabel sementara harus digunakan dan bagaimana operasi harus pipelined / digabungkan.
Step 3− Code Generation
Pembuatan kode adalah langkah terakhir dalam pengoptimalan kueri. Ini adalah bentuk kueri yang dapat dieksekusi, yang bentuknya bergantung pada jenis sistem operasi yang mendasarinya. Setelah kode kueri dibuat, Manajer Eksekusi menjalankannya dan menghasilkan hasilnya.
Pendekatan untuk Pengoptimalan Kueri
Di antara pendekatan untuk pengoptimalan kueri, pencarian lengkap dan algoritme berbasis heuristik banyak digunakan.
Optimasi Pencarian Lengkap
Dalam teknik ini, untuk kueri, semua kemungkinan rencana kueri awalnya dibuat dan kemudian rencana terbaik dipilih. Meskipun teknik ini memberikan solusi terbaik, teknik ini memiliki kompleksitas ruang dan waktu eksponensial karena ruang solusi yang besar. Misalnya teknik pemrograman dinamis.
Optimasi Berbasis Heuristik
Pengoptimalan berbasis heuristik menggunakan pendekatan pengoptimalan berbasis aturan untuk pengoptimalan kueri. Algoritme ini memiliki kompleksitas ruang dan waktu polinomial, yang lebih rendah daripada kompleksitas eksponensial dari algoritme berbasis pencarian yang lengkap. Namun, algoritme ini tidak selalu menghasilkan rencana kueri terbaik.
Beberapa aturan heuristik yang umum adalah -
Lakukan operasi pilih dan proyek sebelum bergabung dengan operasi. Ini dilakukan dengan memindahkan operasi pilih dan proyek ke bawah pohon kueri. Ini mengurangi jumlah tupel yang tersedia untuk digabungkan.
Lakukan operasi pemilihan / proyek yang paling ketat pada awalnya sebelum operasi lainnya.
Hindari operasi produk silang karena menghasilkan tabel perantara berukuran sangat besar.