Optimasi Query
Mencari urutan optimal dari operasi query.
Strategi yang terpilih diharapkan dapat meminimalisasi biaya yang harus dikeluarkan dalam pengeksekusian query.
Biaya eksekusi merupakan kombinasi bobot dari I/O, CPU, dan biaya komunikasi.
- Search Space
Merupakan sekumpulan alternatif perencanaan eksekusi yang merepresentasikan query. Seluruh alternatif adalah ekuivalen, yaitu memberikan hasil yang sama dengan urutan pengoperasian, pengimplementasian, dan performance yang berbeda.
Representasi dari query tersebut dibentuk dalam suatu operator trees yang dapat dibuat dengan aturan transformasi
- Cost Model
Cost Model memprediksi biaya yang harus dikeluarkan dari suatu query yang akan dieksekusi. Terdiri dari cost function, statistic database, dan formula.
- Search Strategy
Search strategy mengeksplorasi search space dan memilih strategi terbaik dari alternatif yang ada menggunakan cost model.
Search Strategy yang dapat digunakan adalah dynamic programming yang bersifat determenistik, di mana menghasilkan solusi terbaik, dan randomized strategies (seperti Iterative Improvement dan Simulated Annealing) yang berkonsentrasi pada pencarian solusi optimal dengan menghindari biaya tinggi dalam optimasi.
Optimasi Query Terpusat
- Algoritma INGRESAlgoritma INGRES
menggunakan algoritma optimasi dinamis yang memecah query kalkulus ke dalam bagian yang lebih kecil secara rekursif. Mengombinasikan dua tahapan yaitu dekomposisi dan optimasi kalkulus-aljabar.
- Algoritma Sistem RSistem R
merupakan optimasi query statis yang didasarkan pada exhaustive search dari ruang solusi yang ada. Input untuk optimizer dengan sistem R adalah pohon relasi aljabar yang dihasilkan dari dekomposisi dari sebuah query SQL. Kemudian output dari sistem merupakan rencana eksekusi yang mengimplementasikan pohon relasi aljabar yang optimal.
Optimizer menetapkan biaya (dalam hal waktu) dari masing-masing pohon kandidat dan mempertahankan pohon dengan biaya yang terkecil.
- Join Ordering
Join ordering merupakan aspek yang penting dalam suatu optimasi query, terlebih pada query terdistribusi. Join ordering menjadi lebih penting ketika query merupakan query terdistribusi karena akan mempengaruhi communication time.
Join ordering dapat dilakukan secara langsung, maupun dengan mengombinasikan dengan semijoins di mana akan meminimalisasi communication cost
Optimasi Query Terdistribusi
- Algoritma INGRES terdistribusi
Fungsi objektif dari algoritma ini adalah untuk meminimalisasi kombinasi baik communication time maupun response time. Algoritma ini juga mendapat keuntungan pada fragmentasi, tetapi hanya fragmentasi horizontal.
Input untuk algoritma pemrosesan query ini dinyatakan dalam calculus relational-tupel dan skema informasi (tipe network, lokasi dan ukuran masing-masing site).
- Algoritma R*
Algoritma R* merupakan substansial ekstensi dari teknik yang dikembangkan untuk optimizer sistem R. Algoritma ini menggunakan pendekatan kompilasi di mana suatu exhaustive search dari seluruh alternative strategi dilakukan untuk memilih salah satu dengan biaya terendah.
Algoritma Sistem R* tidak mendukung pengimplementasian baik dalam fragmentasi maupun replikasi. Input untuk algoritma ini adalah query yang sudah dilokalisasi yang direpresentasikan dalam pohon relasi aljabar(query tree), lokasi relasi, dan statistiknya.
- Algoritma SDD-1
Algoritma SDD-1 berasal dari metode yang disebut sebagai algoritma ‘hill-climbing’, yang memiliki keistimewaan sebagai algoritma pemrosesan query terdistribusi yang pertama. Dalam algoritma ini, perbaikan dari solusi layak awal dihitung secara rekursif sampai tidak ada lagi perbaikan biaya yang dapat dilakukan. Input untuk algoritma ini termasuk query graph, lokasi relasi, dan statistik dari relasi.
Tidak ada komentar:
Posting Komentar