Measure Of Costs
Selection
- Menghitung Cost Query Selection
Cara menghitung cost dari suatu query menggunakan jumlah blok transfer dari disk, dan jumlah seek adalah:
Cost untuk blok b transfer ditambah seeks s:
- tT= waktu untuk transfer satu blok
- tS s = waktu untuk satu kali seek
b * tT + S * tS
| Algorithm | Cost | Reason | |
| A1 | Linier Search | tS + bR * tR | Satu Initial seek ditambah b, transfer blok, di mana b, menunjukkan jumlah blok dalam file |
| A1 | Linear search, equality on key | Kasus Umum tS + (bR/2) tR | Karena kondisi paling banyak Mengisi satu record, pemindaian dapat dihentikan segera dengan record yang diperlukan . Dalam kasus terburuk, bR block transfer masih diperlukan |
| A2 | Primary b+ – tree index, equality on key | (hI + 1) * (tR +tS) | dimana hI menunjukkan ketinggian indeks. Indeks lookup melintasi ketinggian tree ditambah satu I / O untuk mengambil record; masing-masing operasi I / o ini membutuhkan seek dan block transfer |
| A3 | Primary b+ – tree index, equality on nonkey | hI * (tR + tS ) + b *tR | Satu Seeks untuk setiap tingkat tree, satu seeks blok pertama. di sini b adalah jumlah blocks yang berisi record dengan key pencarian tertentu, semua yang dibaca. blok ini adalah blok daun yang diasumsikan disimpan secara berurutan (karena merupakan indeks utama) dan tidak memerlukan tambahan seeks. |
| A4 | secondary b+ – tree index, equality on key | (hI + 1 ) * (tR + tS) | Kasus ini mirip dengan indeks utama |
| A5 | secondary b+ – tree index, equality on nonkey | (hI + n) * (tR + tS) | (Di mana n adalah jumlah record diambil). Sini. Biaya indeks traversal adalah sama seperti A3, tetapi setiap record mungkin berada di blok yang berbeda, membutuhkan seek per record. Cost berpotensi sangat tinggi jika n besar. |
| A5 | Primary b+ – tree index, Comparison | hI * (tR + tS) + b * tR | Identik dengan kasus A3, equality on nonkey |
| A6 | Primary b+ – tree index, Comparison | (hI + n) * (tR + tS) | Identik dengan kasus A4, equality on nonkey |
Implementasi Pada Selection yang Kompleks
Algorithm A8 (conjunctive selection using one index)
Pada algoritma ini pilih kombinasi dari qI dan algorithma A1 sampai A7 yang hasil costnya paling sedikit untuk sqi (r). lalu test kondisi lain pada record setelah mengambil dari memory buffer.
Algorithm A9 (conjunctive selection using multiple-key index)
Pada algoritma ini kita menggunakan komposisi index (multiple-key) yang sesuai.
Algorithm A10 (conjunctive selection by intersection of identifiers)
Pada algoritma ini memerlukan indices dengan record pointers. dengan menggunakan index yang sesuai untuk setiap kondisi dan di ambil titik tengahnya dari semua sets record pointers yang didapat. lalu, ambil records dari file. Apabila ada sebagian kondisi yang tidak sesuai dengan indices, maka lakukan test di dalam memory.
Algorithm A11 (disjunctive selection by union of identifiers)
Algoritma ini dapat diaplikasikan apabila semua kondisi tersedia dalam indices, atau gunakan linear scan. Gunakan index yang sesuai untuk setiap kondisi dan ambil gabungan dari semua sets record pointers yang didapat. Kemudian ambil records dari file.
Sorting
- Membangun indeks pada hubungan, dan menggunakan indeks untuk membaca hubungan untuk disortir.
- Sorting dalam sistem database sangat penting untuk dua alasan :
- Dapat menentukan output yang harus diurutkan
- Pengolahan beberapa operasi relasional query dapat dilaksanakan lebih efisien berdasarkan hubungan diurutkan
Join
Operasi join:
- Hash join
- Merge joinAlgoritma yang berbeda untuk melaksanakan operasi join
- Nested-loop join
- Block nested-loop join
- Index nested-loop join
- Query Optimizer dapat memilih algoritma berdasarkan perkiraan biaya
Referensi
Silberschatz. Abraham, Henry F. Korth, and S. Sudarshan. 2011. Database System Concepts – Sixth Edition. McGraw-Hill.