Query Optimazation adalah proses pemilihan evaluasi Query yang paling efisien merencanakan dari antara banyak strategi yang biasanya mungkin untuk memproses permintaan yang diberikan, terutama jika permintaannya rumit. Query Optimizers untuk evaluasi Query paralel lebih rumit daripada Query Optimizers untuk evaluasi Query berurutan.

1. Overview

Pertimbangkan ekspresi relational-algebra untuk Query “Temukan nama semua pelanggan yang memiliki akun di cabang mana saja yang berlokasi di Brooklyn.”

gambar ini membangun relasi perantara besar, cabang ⋈ rekening ⋈ deposan.

Gambar diatas adalah bentuk equivalent expression. Ini adalah contoh dari expresi relational-algebra, dari contoh diatas kita juga dapat memperkecil ukuran jika tuple diatas tidak memiliki branch city = brooklyn

yang setara dengan ekspresi relation-algebra originalnya, tetapi yang menghasilkan lebih kecil hubungan menengah. Gambar tree diatas menggambarkan ekspresi awal dan transformasi.

2. Estimating Statistic of Expression Results

Biaya operasi tergantung pada ukuran dan statistik input lainnya. Diberikan ekspresi seperti a ⋈ (b ⋈ c) untuk memperkirakan biaya bergabung dengan (b ⋈ c), kita perlu memiliki perkiraan statistik seperti ukuran b ⋈ c.

Di bagian ini pertama-tama mendaftar beberapa statistik tentang hubungan basis data yang disimpan katalog sistem database, dan kemudian menunjukkan cara menggunakan statistik untuk memperkirakan statistik pada hasil berbagai operasi relasional.

3. Transformation of Relational Expression

Dua ekspresi aljabar relasional dikatakan setara jika, pada setiap basis data hukum Misalnya, dua ekspresi menghasilkan set tupel yang sama. (Ingat itu legal database instance adalah salah satu yang memenuhi semua kendala integritas yang ditentukan dalam database skema.) Perhatikan bahwa urutan tupel tidak relevan; dua ungkapan itu mungkin menghasilkan tupel dalam pesanan yang berbeda, tetapi akan dianggap setara selama sebagai himpunan tupel adalah sama.

3.1 Equivalent Rules

                Aturan kesetaraan mengatakan bahwa ekspresi dua bentuk adalah setara. Kita bisa ganti ekspresi bentuk pertama dengan ekspresi bentuk kedua, atau sebaliknya sebaliknya – yaitu kita dapat mengganti ekspresi dari bentuk kedua dengan ekspresi dari bentuk pertama – karena dua ekspresi akan menghasilkan hasil yang sama pada sembarang database yang valid. Pengoptimal menggunakan aturan kesetaraan untuk mengubah ekspresi menjadi ekspresi lain yang setara secara logis.

Ini adalah beberapa syarat dari equivalent:

  1. Operasi pemilihan konjungtif dapat didekonstruksi menjadi suatu urutan individu pilihan. Transformasi ini disebut sebagai cascade σ.


2. Operasi pemilihan bersifat komutatif.

3. Hanya operasi final dalam urutan operasi proyeksi yang diperlukan, yang lain bisa dihilangkan. Transformasi ini juga dapat disebut sebagai cascade Π.

4. Pilihan dapat dikombinasikan dengan produk Cartesian dan theta joins.

5. Operasi theta joins bersifat komutatif.

4. Enumeration of Equivalent Expressions

Pengoptimal kueri menggunakan aturan kesetaraan untuk secara sistematis menghasilkan ekspresi yang setara dengan ekspresi kueri yang diberikan. Secara konseptual, prosesnya sebagai berikut. Diberikan ekspresi, jika ada subekspresi yang cocok dengan satu sisi aturan kesetaraan, pengoptimal menghasilkan ekspresi baru di mana subekspresi ditransformasikan agar sesuai dengan sisi lain dari aturan. Proses ini berlanjut hingga tidak ada lagi ekspresi baru dapat dihasilkan.

5. Choice of Evaluation Plans

Generasi ekspresi hanyalah bagian dari proses optimisasi-kueri, karena setiap operasi dalam ekspresi dapat diimplementasikan dengan algoritma yang berbeda. Oleh karena itu diperlukan rencana evaluasi untuk menentukan secara tepat algoritma apa yang harus digunakansetiap operasi, dan bagaimana pelaksanaan operasi harus dikoordinasikan.