Topik 14
Query Optimizer dan DDBMS
Dekomposisi kueri, lokalisasi data, join terdistribusi, dan optimasi global.
Kemampuan akhir yang diharapkan. Memahami optimasi pada data terdistribusi dan mengenali DDBMS beserta fungsionalitasnya.
Empat lapisan pemrosesan kueri
| Lapisan | Masukan | Keluaran | Peduli distribusi? |
|---|---|---|---|
| 1. Dekomposisi kueri | Kueri kalkulus relasional (SQL) | Kueri aljabar atas relasi global | Tidak — sama untuk sistem terpusat |
| 2. Lokalisasi data | Kueri aljabar atas relasi global | Kueri aljabar atas fragmen fisik | Ya — memakai skema fragmen |
| 3. Optimasi global | Kueri atas fragmen | Rencana eksekusi beserta urutan dan situsnya | Ya — memakai statistik dan biaya jaringan |
| 4. Optimasi lokal | Bagian kueri untuk satu situs | Rencana akses fisik di situs itu | Tidak — tugas DBMS lokal |
Empat langkah dekomposisi kueri
| Langkah | Tujuan | Teknik |
|---|---|---|
| 1. Normalisasi | Mengubah kualifikasi WHERE ke bentuk normal | Bentuk normal konjungtif (CNF) atau disjungtif (DNF) |
| 2. Analisis | Menolak kueri yang salah tipe atau salah semantik | Pemeriksaan tipe terhadap skema global + graf kueri |
| 3. Eliminasi redundansi | Membuang predikat berlebih | Hukum idempoten: p∧p≡p, p∧(p∨q)≡p, p∧¬p≡false |
| 4. Penulisan ulang | Mengubah kueri menjadi pohon operator | Daun = relasi, akar = proyeksi hasil |
Kueri disebut salah tipe bila atribut atau relasinya tidak ada dalam skema global, atau operasi diterapkan pada tipe yang salah. Disebut salah semantik bila graf kuerinya tidak terhubung — hasilnya perkalian kartesian yang hampir pasti bukan yang dimaksud pengguna.
Lokalisasi data dan reduksi
Lapisan lokalisasi menerjemahkan kueri aljabar atas relasi global menjadi kueri atas fragmen fisik, memakai program lokalisasi: UNION untuk fragmen horizontal, JOIN untuk fragmen vertikal. Kueri hasilnya lalu direduksi.
- Reduksi horizontal primer — σp(Fi) = ∅ bila p bertentangan dengan predikat fragmen
- Reduksi vertikal — fragmen yang tidak menyumbang atribut hasil dibuang dari join
- Reduksi join — pasangan fragmen dengan predikat bertentangan pada atribut join dibuang
- Reduksi turunan — fragmen anak hanya dipasangkan dengan fragmen induknya
Strategi join terdistribusi
Semijoin memakai identitas R ⋈ S = (R ⋉ S) ⋈ S. Bloom join menggantikan daftar nilai join dengan penapis Bloom yang jauh lebih ringkas, dengan imbalan positif palsu yang baru tersaring saat join akhir — hasil akhirnya tetap identik.
| Strategi | Yang dikirim | Pesan | Menang bila |
|---|---|---|---|
| Kirim R utuh | Seluruh relasi R | 1 | R kecil atau hampir semua barisnya berpasangan |
| Kirim S utuh | Seluruh relasi S | 1 | S jauh lebih kecil daripada R |
| Semijoin | π kolom join dari S, lalu R yang tersaring | 2 | R besar dan selektivitasnya rendah |
| Bloom join | Penapis Bloom, lalu R yang tersaring | 2 | Sama seperti semijoin, dengan pesan pertama jauh lebih kecil |
Optimasi global
- Urutan join — ruang pencariannya tumbuh faktorial, sehingga dipakai heuristik atau pemrograman dinamis
- Pemilihan salinan — replika mana yang paling murah diakses dari situs asal kueri
- Penempatan operasi — di situs mana tiap operator dijalankan
- Dorong selection dan projection sedekat mungkin ke daun, sebelum data melintasi jaringan
Di Oracle, bukti bahwa reduksi benar-benar terjadi ada pada kolom PSTART/PSTOP (partition pruning) dan operasi REMOTE pada rencana eksekusi. Kolom OTHER berisi SQL yang sesungguhnya dikirim ke situs jauh.
Coba di terminal
Kueri di bawah memperagakan konsep topik ini pada data sungguhan. Tekan ▶ Jalankan untuk membukanya di Terminal SQL, lalu ubah sesuka hati — sesi terminal adalah salinan pribadi di peramban Anda.
Rencana eksekusi sebuah join
Lapisan optimasi: urutan SCAN, JOIN, FILTER, AGGREGATE, SORT. rumahsakit
EXPLAIN PLAN FOR
SELECT d.spesialis, COUNT(*) AS n
FROM dokter d JOIN pasien_dokter pd ON d.id_dokter = pd.id_dokter
WHERE pd.biaya > 250000
GROUP BY d.spesialis
ORDER BY n DESC;Reduksi lokalisasi
Predikat kota = Bandung hanya cocok dengan satu fragmen; dua fragmen lain bisa dilewati. terdistribusi
SELECT nama_pasien FROM pasien WHERE kota = 'Bandung';
SELECT nama_pasien FROM pasien@bandung;Semijoin: kirim kunci, bukan tabel
Hanya id pasien yang dikirim ke situs lain untuk menyaring baris yang berpasangan. terdistribusi
SELECT pd.id, pd.resep
FROM pasien_dokter@bandung pd
WHERE pd.id_pasien IN (SELECT id_pasien FROM pasien@bandung);Jalankan sendiri
Dekomposisi Kueri
Normalisasi CNF/DNF, analisis graf kueri, eliminasi redundansi, dan pohon operator.
Lokalisasi Data
Program lokalisasi dan reduksi fragmen, diverifikasi terhadap hasil kueri global.
Join Terdistribusi
Kirim utuh, semijoin, dan bloom join dijalankan sungguhan lalu dibandingkan biayanya.
Terminal SQL Live
Terminal SQL gaya SQL*Plus: kueri, DML, DDL, transaksi, kamus data, dan 3 situs lewat database link — pratinjau hasil muncul saat mengetik.
Bank Soal Praktikum
38 soal Praktikum 2–5, termasuk ke-12 soal Praktikum 3 dan soal INSERT/UPDATE/DELETE ber-CASCADE, dinilai otomatis dari hasil dan keadaan tabel.
Sumber: Modul Pertemuan 7 — Dekomposisi Kueri dan Lokalisasi Data; Modul 1 (RPS pekan 14)