Biaya operasi I/O antara pemindaian indeks dan pemindaian tabel berbeda secara fundamental dalam hal bagaimana data diakses, jumlah halaman yang dibaca, dan efisiensi berdasarkan selektivitas kueri dan organisasi data.
Pemindaian indeks melibatkan mengakses data dengan melintasi struktur indeks (seringkali b-tree). Biaya di sini terutama mencakup dua komponen: biaya mengakses halaman indeks dan biaya pengambilan halaman tabel yang sesuai. Halaman indeks umumnya memiliki pola akses acak karena node daun indeks mungkin tidak secara fisik berdekatan pada disk, yang mengarah ke operasi I/O acak. Setiap langkah logis ke bawah pohon indeks dari akar ke daun membutuhkan halaman baca, dan biaya ini diperkirakan menggunakan parameter biaya halaman acak sistem. Setelah menemukan entri indeks untuk baris yang relevan, sistem mengambil halaman data tabel yang sesuai. Jumlah halaman data tersebut diambil tergantung pada selektivitas kueri dan korelasi fisik antara data yang disimpan dan urutan indeks (dikenal sebagai korelasi). Korelasi yang tinggi berarti lokasi baris entri indeks sangat cocok dengan urutan data fisik, mengurangi I/O acak dan membuat pemindaian indeks lebih efisien. Di sisi lain, korelasi yang rendah mengarah pada banyak pengambilan acak, meningkatkan biaya I/O secara substansial.
Biaya CPU dalam pemindaian indeks termasuk memproses setiap baris individu yang diambil, tetapi masalah biaya utama adalah I/O. Ada juga aspek visibilitas: Jika database memiliki pelacakan peta visibilitas mana halaman data sepenuhnya terlihat untuk semua transaksi, sistem kadang-kadang dapat sepenuhnya melewatkan membaca halaman tertentu selama pemindaian hanya indeks, mengurangi biaya I/O secara drastis.
Sebaliknya, pemindaian tabel atau pemindaian tabel penuh beroperasi dengan membaca semua halaman data secara berurutan dari tabel. I/O di sini sebagian besar berurutan, yang cenderung lebih cepat daripada I/O acak pada disk pemintalan atau kurang dihukum pada SSD. Biaya pemindaian tabel penuh relatif konstan karena membaca seluruh tabel terlepas dari jumlah baris yang memenuhi kueri. Biaya ini tergantung pada jumlah total halaman dalam tabel daripada jumlah baris yang dipilih. Pemindaian tabel penuh tidak mendapat manfaat dari selektivitas; Mereka harus membaca setiap halaman bahkan jika kueri menyaring barisan. Namun, dengan teknologi penyimpanan modern dan optimisasi seperti bacaan multi-blok, bacaan paralel, dan pembongkaran lapisan penyimpanan, biaya pemindaian tabel penuh mungkin kompetitif atau bahkan kurang dari pemindaian indeks untuk kueri yang mengambil sebagian besar tabel.
Pengoptimal berbasis biaya (CBO) memutuskan antara menggunakan pemindaian indeks dan pemindaian tabel penuh berdasarkan perkiraan biaya. Untuk pertanyaan yang sangat selektif di mana hanya sebagian kecil dari baris yang perlu diambil pemindaian indeks cenderung memiliki biaya I/O yang lebih rendah karena lebih sedikit halaman meja diambil. Ketika ambang selektivitas meningkat (lebih banyak baris yang dibutuhkan), biaya I/O dari pemindaian indeks naik karena jumlah pengambilan halaman acak yang lebih tinggi dan traversal indeks, akhirnya melampaui biaya pemindaian meja penuh. Pada titik ini, CBO mendukung pemindaian tabel karena biaya I/O berurutan kurang dari beban I/O acak dari banyak pencarian indeks.
Faktor penting lain yang memengaruhi perbedaan biaya I/O adalah "faktor pengelompokan" atau pengelompokan fisik baris yang sesuai dengan kunci indeks. Faktor pengelompokan yang lebih rendah (clustering yang lebih baik) berarti baris yang diakses melalui indeks terletak di dekat satu sama lain secara fisik, mengurangi I/O acak dan meningkatkan efisiensi pemindaian indeks. Faktor pengelompokan yang lebih tinggi mengarah pada lebih banyak I/O acak selama pemindaian indeks dan mengurangi manfaatnya dibandingkan dengan pemindaian tabel.
Sistem basis data modern juga dapat menerapkan pemindaian paralel baik indeks dan pemindaian meja penuh di mana sumber daya I/O dan CPU dibagi di antara banyak pekerja, yang dapat mengurangi total waktu kueri. Namun, sifat mendasar I/O untuk pemindaian indeks (akses halaman acak) versus pemindaian tabel (kebanyakan akses halaman berurutan) tetap menjadi pembeda utama.
Untuk meringkas poin -poin penting tentang perbedaan biaya I/O:
- Indeks pemindaian dikenakan biaya I/O dari halaman indeks membaca (akses acak) plus mengambil halaman data yang sesuai (akses acak yang berpotensi). Biaya sensitif terhadap selektivitas, korelasi, dan faktor pengelompokan.
- Pemindaian tabel penuh melakukan I/O berurutan membaca semua halaman, dengan biaya I/O yang relatif stabil terlepas dari selektivitas.
- Pemindaian indeks dapat mengungguli ketika kueri menargetkan subset kecil data, tetapi menderita overhead I/O acak saat selektivitas naik.
- Pemindaian tabel penuh dapat lebih efisien ketika sebagian besar tabel membutuhkan akses karena I/O sekuensial yang efisien.
- Peta visibilitas dan pemindaian hanya indeks dapat mengurangi biaya I/O dalam beberapa kasus pemindaian indeks dengan menghindari pembacaan halaman data.
- Paralelisme dapat meningkatkan kedua jenis pemindaian tetapi tidak mengubah karakteristik I/O mendasar.
- Pengoptimal menyeimbangkan faktor -faktor biaya ini untuk memilih metode yang paling efisien berdasarkan kueri dan karakteristik data.