Indeks SQL Dijelaskan, Pt. 2

Dalam pelajaran pertama Penjelasan Indeks SQL , kita belajar menggunakan pengurutan untuk mempercepat pengambilan data. Sementara eksekusi kueri kami lebih cepat setelah baris diurutkan, pengurutan melibatkan membaca setiap baris setidaknya sekali dan memindahkannya. Itu membuat metode ini lebih lambat dan kurang efisien daripada sekadar membaca seluruh tabel secara berurutan.

Kesimpulan logis tampaknya adalah bahwa kita harus mempertahankan salinan yang diurutkan—yang secara resmi kita sebut sebagai indeks SQL , diawali dengan IX_ —dari tabel yang diberikan. Algoritma pengambilan dari artikel pertama kemudian akan berlaku, dan kita tidak perlu mengurutkan tabel sebelum memulai.

Indeks sebagai Salinan Terurut dari Tabel

Mari kita lihat implementasi literal dari ide itu, sekali lagi menggunakan Google Spreadsheet. Spreadsheet Reservasi kami menjadi kumpulan lima lembar yang berisi data yang sama. Setiap lembar diurutkan menurut kumpulan kolom yang berbeda.

Latihan di sini dimaksudkan agar tidak terlalu menuntut daripada di artikel tutorial indeks SQL sebelumnya—latihan ini dapat dilakukan lebih banyak dengan perasaan daripada dengan penghitung waktu dan jumlah baris. Beberapa latihan akan tampak sangat mirip, tetapi kali ini, kita akan mengeksplorasi:

1. Cara lebih efisien mengambil data saat menggunakan indeks terpisah daripada tabel utama yang diurutkan
2. Bagaimana menjaga ketertiban di setiap indeks dan tabel saat memodifikasi data

Tutorial sebelumnya berfokus pada pembacaan, tetapi dalam banyak dinamika data dunia nyata yang umum—termasuk reservasi hotel kami—kami harus memperhitungkan efek pengindeksan pada kinerja penulisan, baik untuk memasukkan data baru maupun memperbarui data yang ada.

Latihan Pendahuluan: Membatalkan Reservasi

Untuk merasakan kinerja indeks SQL menggunakan strategi tabel terurut, tugas Anda adalah menghapus reservasi untuk Klien 12, mulai 22 Agustus 2020, di Hotel 4. Perlu diingat bahwa Anda harus menghapus satu baris dari semua salinan tabel dan pertahankan penyortiran yang benar.

Selesai? Harus jelas bahwa gagasan menyimpan beberapa salinan tabel yang diurutkan tidak sebaik kelihatannya. Jika Anda masih ragu, Anda juga dapat mencoba memasukkan kembali reservasi yang baru saja Anda hapus atau mengubah tanggal reservasi yang ada.

Sementara salinan tabel yang diurutkan memungkinkan pengambilan yang lebih cepat, seperti yang baru saja kita pelajari, modifikasi data adalah mimpi buruk. Kapan pun kita perlu menambah, menghapus, atau memperbarui baris yang ada, kita harus mengambil semua salinan tabel, menemukan baris dan/atau tempat di mana ia harus ditambahkan atau dipindahkan, dan akhirnya memindahkan blok data.

Indeks SQL Menggunakan Alamat Baris

Spreadsheet ini berisi indeks yang menggunakan pendekatan berbeda. Baris indeks masih diurutkan menurut kriteria tertentu, tetapi kami tidak menyimpan semua informasi lain di baris indeks. Sebagai gantinya, kami hanya menyimpan "alamat baris", alamat baris di lembar Reservasi—yang mewakili tabel itu sendiri—di kolom H.

Semua implementasi RDBMS menggunakan kemampuan tingkat sistem operasi untuk menemukan blok pada disk dengan cepat menggunakan alamat fisik. Alamat baris biasanya terdiri dari alamat blok ditambah posisi baris di dalam blok.

Mari lakukan beberapa latihan untuk mempelajari cara kerja desain indeks ini.

Latihan 1: Semua Reservasi Klien

Seperti pada artikel pertama, Anda akan mensimulasikan eksekusi kueri SQL berikut:

 SELECT * FROM Reservations WHERE ClientID = 12;

Sekali lagi, ada dua pendekatan yang masuk akal. Yang pertama cukup membaca semua baris dari tabel Reservasi dan hanya mengambil baris yang cocok dengan kriteria:

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

Pendekatan kedua melibatkan membaca data dari lembar IX_ClientID, dan untuk item apa pun yang cocok dengan kriteria, menemukan baris dalam tabel Reservasi berdasarkan nilai rowAddress:

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

Di sini, ekspresi Get first row from diimplementasikan oleh loop yang mirip dengan yang terlihat di artikel sebelumnya:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

Anda dapat menemukan baris dengan rowAddress tertentu dengan menggeser ke bawah hingga Anda menemukan baris, atau menggunakan filter pada kolom rowAddress.

Jika hanya ada sedikit reservasi yang dikembalikan, pendekatan menggunakan indeks akan lebih baik. Namun, dengan ratusan—atau terkadang bahkan hanya puluhan—baris yang dikembalikan, hanya menggunakan tabel Reservasi secara langsung bisa lebih cepat.

Volume pembacaan bergantung pada nilai ClientID. Untuk nilai terbesar harus membaca seluruh indeks, sedangkan untuk nilai terendah berada di awal indeks. Nilai rata-rata adalah setengah dari jumlah baris.

Kami akan kembali ke bagian itu nanti dan menyajikan solusi yang efisien. Untuk saat ini, mari fokus pada bagian setelah Anda menemukan baris pertama yang cocok dengan kriteria kita.

Latihan 2: Jumlah Reservasi yang Dimulai pada Tanggal tertentu

Tugasnya menghitung jumlah check-in pada 16 Agustus 2020, menggunakan desain indeks baru.

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

Pendekatan menggunakan indeks yang tepat untuk penghitungan lebih unggul daripada pemindaian tabel, tidak peduli jumlah baris yang terlibat. Alasannya adalah karena kita tidak harus mengakses tabel Reservasi sama sekali—kita memiliki semua informasi yang kita butuhkan dalam indeks itu sendiri:

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

Algoritma pada dasarnya sama dengan algoritma yang menggunakan tabel yang diurutkan. Namun, baris indeks jauh lebih pendek daripada baris tabel, sehingga RDBMS kita harus membaca lebih sedikit blok data dari disk.

Latihan 3: Investigasi Kriminal (Daftar Tamu Diberikan Hotel dan Rentang Tanggal)

Yuk siapkan daftar tamu yang tiba di Hotel 3 pada 13 dan 14 Agustus 2020.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

Kita dapat membaca semua baris dari tabel Reservasi atau menggunakan salah satu indeks yang tersedia. Setelah melakukan latihan yang sama dengan tabel yang diurutkan menurut kriteria tertentu, kami menemukan bahwa indeks IX_HotelID_DateFrom adalah yang paling efisien.

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

Bisakah Kita Merancang Indeks yang Lebih Efisien?

Kami mengakses tabel karena nilai ClientID , satu-satunya informasi yang kami perlukan untuk daftar tamu yang kami laporkan. Jika kita memasukkan nilai itu dalam indeks SQL, kita tidak perlu mengakses tabel sama sekali. Coba siapkan daftar yang hanya membaca dari indeks seperti itu, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Ketika indeks berisi semua informasi yang diperlukan untuk eksekusi kueri, kami mengatakan bahwa indeks mencakup kueri.

Latihan 4: Daftar Nama Tamu Alih-alih ID

Daftar ID tamu tidak akan berguna bagi petugas polisi yang menyelidiki kejahatan. Kami perlu memberikan nama:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Untuk memberikan daftar, selain data dari tabel Reservations , kami juga membutuhkan tabel Clients yang berisi informasi tamu, yang dapat ditemukan di lembar Google ini.

Latihan ini mirip dengan yang sebelumnya, dan begitu juga pendekatannya.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

Ekspresi Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID dapat diimplementasikan dengan pemindaian tabel atau menggunakan indeks kami. Jika kita menggunakan pemindaian tabel, untuk setiap ClientID Klien dari loop While , kita harus membaca rata-rata setengah baris dari tabel Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

Implementasi indeks yang telah kita pertimbangkan sejauh ini—sebut saja sebagai implementasi indeks “datar”—tidak akan terlalu membantu. Kami harus membaca jumlah baris yang sama (meskipun baris lebih kecil) dari indeks, lalu melompat ke baris di Clients menggunakan RowAddress :

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Catatan: Di sini, PK mengacu pada "kunci utama", sebuah istilah yang akan kita jelajahi nanti dalam seri ini.

Apakah ada cara untuk mencapai ini tanpa harus membaca begitu banyak baris? Ya—inilah gunanya indeks B-tree.

Indeks Pohon Seimbang (pohon-B)

Mari kita bagi baris dari Clients_PK_Flat menjadi empat baris blok dan buat daftar yang berisi nilai ClientID terakhir dari blok dan alamat awal blok (kolom IndexRowAddress ). Struktur data indeks database yang dihasilkan—Anda dapat menemukannya di lembar Clients_PK_2Levels. Cobalah bagaimana struktur baru membantu Anda menemukan klien yang memiliki ClientID Klien 28. Algoritmenya akan terlihat seperti ini:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Anda mungkin tahu bahwa kami dapat menambahkan level lain. Level 1 terdiri dari empat baris, seperti yang Anda lihat di tab IX_Clients_PK. Untuk menemukan nama tamu dengan ClientID 28, Anda harus membaca tiga blok (node) data—satu per level—dari struktur kunci utama dan terakhir melompat ke baris Klien dengan alamat 42.

Struktur indeks SQL ini disebut pohon seimbang. Pohon itu seimbang ketika jalur dari simpul akar ke setiap simpul tingkat daun memiliki panjang yang sama, yang disebut kedalaman pohon-B. Dalam kasus kami, kedalamannya adalah tiga.

Mulai sekarang, kami akan menganggap setiap indeks memiliki struktur B-tree, meskipun spreadsheet kami hanya berisi entri tingkat daun. Fakta yang paling penting untuk diketahui tentang B-tree adalah:

• Struktur indeks B-tree adalah indeks yang paling umum digunakan oleh semua RDBMS utama di pasar.
• Semua level dari pohon seimbang diurutkan berdasarkan nilai kolom kunci.
• Data dibaca dari disk dalam blok.
• Satu node B-tree berisi satu atau lebih blok.
• Faktor terpenting yang memengaruhi kinerja kueri adalah jumlah blok yang dibaca dari disk.
• Jumlah item di setiap level B-tree baru, dimulai dari root, berakhir di level daun, meningkat secara eksponensial.

Latihan 5: Investigasi Kriminal, Bagian II

Sekarang, inspektur polisi sedang mencari daftar nama tamu yang sesuai, tanggal kedatangan, dan nama hotel dari semua hotel di kota A.

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Pendekatan 1

Jika kita menggunakan indeks IX_DateFrom_HotelID_ClientID , maka untuk setiap baris dari rentang tanggal, kita harus mengakses tabel Hotel dan memeriksa apakah hotel tersebut dari kota A. Jika ya, kita juga harus mengakses tabel Klien untuk membaca nama klien.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Pendekatan 2

Menggunakan IX_HotelID_DateFrom_ClientID memberi kami rencana eksekusi yang lebih efisien.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Dari tabel Hotels , kami menemukan semua hotel dari kota A. Mengetahui ID hotel ini, kami dapat membaca item berikutnya dari indeks IX_HotelID_DateFrom_ClientID . Dengan cara ini, setelah menemukan baris pertama di tingkat daun B-tree untuk setiap hotel dan tanggal, kami tidak membaca reservasi dari hotel di luar kota A.

Di sini, kita dapat melihat bahwa ketika kita memiliki indeks database yang sesuai dengan tujuan kita, penggabungan tambahan sebenarnya dapat membuat kueri lebih cepat.

Struktur B-tree dan bagaimana itu diperbarui setiap kali sebuah baris dimasukkan, diperbarui, atau dihapus akan dibahas secara lebih rinci ketika saya menjelaskan motivasi untuk mempartisi dan dampaknya. Intinya adalah kita dapat mempertimbangkan operasi ini dengan cepat setiap kali kita menggunakan index.

Kueri Indeks dalam SQL: Detail Membuat Semua Perbedaan

Ketika datang ke indeks dan database, bekerja di tingkat bahasa SQL menyembunyikan detail implementasi sampai batas tertentu. Latihan-latihan ini dimaksudkan untuk membantu Anda merasakan bagaimana rencana eksekusi bekerja saat menggunakan indeks SQL yang berbeda. Setelah membaca artikel ini, saya harap Anda dapat menebak rencana eksekusi terbaik yang diberikan indeks yang tersedia dan indeks desain yang akan membuat kueri secepat dan seefisien mungkin.

Di bagian selanjutnya dari seri ini, kami akan menggunakan dan memperluas keterampilan yang baru diperoleh untuk menyelidiki dan memahami praktik terbaik dan anti-pola paling umum dalam penggunaan indeks dalam SQL. Saya memiliki daftar praktik yang baik dan terbaik yang ingin saya bahas di bagian selanjutnya, tetapi untuk membuat artikel berikutnya lebih relevan dengan kebutuhan dan pengalaman Anda, jangan ragu untuk memposting pertanyaan Anda sendiri yang ingin Anda lihat jawabannya .

Di bagian akhir Penjelasan Indeks SQL , kita juga akan belajar tentang tabel dan partisi indeks, motivasi yang benar dan salah untuk menggunakannya, dan dampaknya pada kinerja kueri dan pemeliharaan basis data.