Optimasi Kueri dalam Sistem Terdistribusi
Bab ini membahas tentang optimasi query pada sistem database terdistribusi.
Arsitektur Pemrosesan Kueri Terdistribusi
Dalam sistem database terdistribusi, pemrosesan kueri terdiri dari pengoptimalan di tingkat global dan lokal. Kueri memasuki sistem database di klien atau situs pengendali. Di sini, pengguna divalidasi, kueri diperiksa, diterjemahkan, dan dioptimalkan di tingkat global.
Arsitektur dapat direpresentasikan sebagai -
Memetakan Kueri Global menjadi Kueri Lokal
Proses pemetaan kueri global ke kueri lokal dapat diwujudkan sebagai berikut -
Tabel yang diperlukan dalam kueri global memiliki fragmen yang didistribusikan ke beberapa situs. Basis data lokal memiliki informasi hanya tentang data lokal. Situs pengontrol menggunakan kamus data global untuk mengumpulkan informasi tentang distribusi dan merekonstruksi tampilan global dari fragmen.
Jika tidak ada replikasi, pengoptimal global menjalankan kueri lokal di situs tempat fragmen disimpan. Jika ada replikasi, pengoptimal global memilih situs berdasarkan biaya komunikasi, beban kerja, dan kecepatan server.
Pengoptimal global menghasilkan rencana eksekusi terdistribusi sehingga jumlah transfer data paling sedikit terjadi di seluruh situs. Rencana tersebut menyatakan lokasi fragmen, urutan langkah kueri yang perlu dijalankan dan proses yang terlibat dalam mentransfer hasil antara.
Kueri lokal dioptimalkan oleh server database lokal. Terakhir, hasil kueri lokal digabungkan melalui operasi gabungan dalam kasus fragmen horizontal dan operasi gabungan untuk fragmen vertikal.
Sebagai contoh, mari kita pertimbangkan bahwa skema Proyek berikut ini terpecah-pecah secara horizontal menurut Kota, kota-kota tersebut adalah New Delhi, Kolkata, dan Hyderabad.
PROYEK
| PId | Kota | Departemen | Status |
Misalkan ada kueri untuk mengambil detail dari semua proyek yang statusnya "Sedang Berlangsung".
Kueri global akan menjadi & inus;
$$ \ sigma_ {status} = {\ small "berkelanjutan"} ^ {(PROJECT)} $$
Permintaan di server New Delhi akan -
$$ \ sigma_ {status} = {\ small "berkelanjutan"} ^ {({NewD} _- {PROJECT})} $$
Permintaan di server Kolkata akan -
$$ \ sigma_ {status} = {\ small "berkelanjutan"} ^ {({Kol} _- {PROJECT})} $$
Permintaan di server Hyderabad akan -
$$ \ sigma_ {status} = {\ small "berkelanjutan"} ^ {({Hid} _- {PROJECT})} $$
Untuk mendapatkan hasil keseluruhan, kita perlu menggabungkan hasil dari tiga query sebagai berikut -
$ \ sigma_ {status} = {\ small "berkelanjutan"} ^ {({NewD} _- {PROJECT})} \ cup \ sigma_ {status} = {\ small "berkelanjutan"} ^ {({kol} _- {PROJECT})} \ cup \ sigma_ {status} = {\ small "berkelanjutan"} ^ {({Hyd} _- {PROJECT})} $
Pengoptimalan Kueri Terdistribusi
Pengoptimalan kueri terdistribusi memerlukan evaluasi sejumlah besar pohon kueri yang masing-masing menghasilkan hasil kueri yang diperlukan. Ini terutama karena adanya sejumlah besar data yang direplikasi dan terfragmentasi. Oleh karena itu, targetnya adalah menemukan solusi optimal, bukan solusi terbaik.
Masalah utama untuk pengoptimalan kueri terdistribusi adalah -
- Pemanfaatan sumber daya secara optimal dalam sistem terdistribusi.
- Query trading.
- Pengurangan ruang solusi kueri.
Pemanfaatan Sumber Daya Secara Optimal dalam Sistem Terdistribusi
Sistem terdistribusi memiliki sejumlah server database di berbagai situs untuk melakukan operasi yang berkaitan dengan kueri. Berikut adalah pendekatan untuk pemanfaatan sumber daya yang optimal -
Operation Shipping- Dalam operasi pengiriman, operasi dijalankan di situs tempat data disimpan dan bukan di situs klien. Hasilnya kemudian ditransfer ke situs klien. Ini sesuai untuk operasi yang operandnya tersedia di lokasi yang sama. Contoh: Operasi Select dan Project.
Data Shipping- Dalam pengiriman data, fragmen data ditransfer ke server database, tempat operasi dijalankan. Ini digunakan dalam operasi di mana operan didistribusikan di situs yang berbeda. Ini juga sesuai dalam sistem di mana biaya komunikasinya rendah, dan prosesor lokal jauh lebih lambat daripada server klien.
Hybrid Shipping- Ini adalah kombinasi data dan operasi pengiriman. Di sini, fragmen data ditransfer ke prosesor berkecepatan tinggi, tempat operasi dijalankan. Hasilnya kemudian dikirim ke situs klien.
Query Trading
Dalam algoritma perdagangan kueri untuk sistem basis data terdistribusi, situs pengendali / klien untuk kueri terdistribusi disebut pembeli dan situs tempat kueri lokal dieksekusi disebut penjual. Pembeli merumuskan sejumlah alternatif untuk memilih penjual dan merekonstruksi hasil global. Target pembeli adalah mencapai biaya yang optimal.
Algoritme dimulai dengan pembeli menetapkan sub-kueri ke situs penjual. Rencana optimal dibuat dari rencana permintaan optimal lokal yang diusulkan oleh penjual dikombinasikan dengan biaya komunikasi untuk merekonstruksi hasil akhir. Setelah rencana optimal global dirumuskan, kueri dijalankan.
Pengurangan Ruang Solusi dari Query
Solusi optimal umumnya melibatkan pengurangan ruang solusi sehingga biaya kueri dan transfer data berkurang. Ini dapat dicapai melalui sekumpulan aturan heuristik, seperti halnya heuristik dalam sistem terpusat.
Berikut adalah beberapa aturannya -
Lakukan operasi pemilihan dan proyeksi sedini mungkin. Ini mengurangi aliran data melalui jaringan komunikasi.
Sederhanakan operasi pada fragmen horizontal dengan menghilangkan kondisi pemilihan yang tidak relevan dengan lokasi tertentu.
Dalam kasus operasi gabungan dan gabungan yang terdiri dari fragmen yang terletak di beberapa lokasi, transfer data terfragmentasi ke situs di mana sebagian besar datanya ada dan lakukan operasi di sana.
Gunakan operasi semi-join untuk memenuhi syarat tupel yang akan digabungkan. Ini mengurangi jumlah transfer data yang pada akhirnya mengurangi biaya komunikasi.
Gabungkan daun dan sub-pohon umum dalam pohon kueri terdistribusi.