MR Ferry

Mungkin ketika kuliah kita udah sering mendengar kata index pada database. Harusnya pada saat materi database dasar ada materi tentang index. Index pada database berguna untuk mempercepat pencarian data agar database tidak perlu melakukan full scan data. Awalnya memang ga bakal terasa efeknya. Apalagi ketika jumlah data yang disimpan masih sedikit. Dampaknya baru terasa ketika data yang disimpan sudah mulai besar dan terdapat pencarian menggunakan kolom yang tidak di-index sehingga database melakukan pencarian data dengan membaca keseluruhan data yang banyak dan tentu saja mengakibatkan proses pencariannya jadi sangat lambat. Disinilah index dibutuhkan.

Ada beberapa jenis index pada database, seperti B-tree, B+tree, Hash, Gist, GIN, dan lainnya. B-Tree dan B+Tree cocok untuk untuk pencarian menggunakan range value dan prefix chars (<, >, <=,>=, BETWEEN, LIKE 'prefix%'), Hash cocok untuk pencarian dengan equals, Gist cocok untuk tipe data yang kompleks, dan GIN cocok untuk pencarian dengan full-text. Tapi default type pada beberapa database seperti MySql dan PostgreSql adalah B-tree karena dianggap paling ideal untuk banyak kasus lain selain pencarian seperti ORDER BY,GROUP BY, MIN, dan MAX. B-tree ini artinya Balanced Tree, sesuai namanya ini menerapkan data struktur Tree. Kalau struktur data Tree rootnya tetap, sehingga worst case-nya dapat menghasilkan urutan data yang ga seimbang dengan kecepatan O(n). Sedangkan B-tree keseimbangannya dijaga dengan range tertentu agar proses pencarian lebih optimal dengan kecepatan O(log(n)). Penjelasan mengenai O(log(n)) bisa dibaca pada halaman Big O Notation. Oh ya, B-tree (Balanced Tree) dan B+tree (B Plus Tree) adalah 2 hal yang berbeda, walau memiliki nama yang mirip dan sama-sama menerapkan Tree data struktur. Tapi pada tulisan ini fokus gw hanyalah penggunaan index B-tree pada database saja. Kalau ingin mempelajari lebih dalam tentang B-tree bisa baca lebih lanjut di Wikipedia.

By default, Primary Key dan Unique Key di-index otomatis oleh database (khusus MySql juga mengindex Foreign Key) menggunakan B-tree. Selain key-key itu, kita perlu menetapkan Index Key secara terpisah pada kolom lain yang ingin diindex. Pada kolom yang diindex, pencarian akan lebih cepat karena datanya tersimpan terurut menggunakan struktur data Tree dengan kecepatan O(log(n)), jadi tidak perlu mencari keseluruhan data. Seperti melakukan pencarian kata pada kamus, semua kata disimpan secara terurut. Jadi ketika kita ingin mencari kata yang berawalan dengan huruf “F”, maka kita tinggal buka halaman yang berawalan “F” tanpa perlu mencarinya satu-persatu dari halaman awal sampai halaman akhir. Contohnya seperti tabel Person berikut ini:

CREATE INDEX person_name_index
ON person (name);

Misalkan table di atas memiliki kolom Id sebagai Primary Key, kolom Name sebagai Index Key, dan kolom Gender, Birth date, dan Occupation yang tidak terindex. Behind the scene, database juga menyimpan data Index Name secara terpisah menggunakan struktur data Tree yang dicari dari root value. Ilustrasinya bisa dilihat di link BTree visualization. Namun untuk mempermudah penulisan, di sini kita gambarkan saja menggunakan tabel dengan posisi terurut seperti berikut:

Ketika kita melakukan pencarian menggunakan Name = “Dodi”, database tidak perlu melakukan pencarian semua nama untuk mendapatkan data dengan nama “Dodi”. Database bisa mendapatkan data “Dodi” dengan cepat karena datanya sudah terurut meggunakan struktur data Tree. Perlu diperhatikan juga, where clause menggunakan LIKE %keyword atau LIKE %keyword% pada kolom yang di-index tidak akan dioptimasi, hanya menggunakan operator =, !=, <, >, <=,>=, BETWEEN, IN (), NOT IN (), dan menggunakan prefix seperti LIKE keyword% yang dioptimasi. Ibarat kamus, tentu sulit mencari kata berdasarkan karakter terakhir atau karakter di tengah.

Composite Index

Selain single index, kita juga bisa menggunakan index menggunakan lebih dari satu kolom. Ini bagus untuk kasus yang sering melakukan pencarian terhadap lebih dari kolom dalam satu query sehingga lebih cepat daripada bikin beberapa single index. Misalkan pada contoh berikut.

Misalnya yang diindex pada tabel di atas adalah (Name, Birth date). Maka datanya akan diurutkan terlebih dahulu dari kolom Name, diikuti kolom Birth date. Seperti ilustrasi berikut:

CREATE INDEX person_name_birth_date_index
ON person (name, birth_date);

Jadi Saat melakukan pencarian dengan Name = “Yudi” dan Birth date = “1995-03-03”, database akan mencari data berdasarkan kombinasi Name & Birth date, yaitu “Yudi” diikuti “1995-03-03” sehingga akan didapatkan data dengan id = 3. Ketika kita sudah menggunakan composite index (Name, Birth date), kita tidak perlu lagi menambahkan single index (Name) karena index kolom Name sudah tercover oleh composite index. Misalkan kita ingin melakukan query dengan kolom Name saja, pencarian itu tetap akan terindex lewat composite index di atas karena ditulis paling awal. Sedangkan apabila kita melakukan pencarian pada kolom Birth date saja tanpa menggunakan kolom Name, maka itu tidak akan tercover composite index di atas, karena Birth date ditulis setelah kolom Name. Pencarian menggunakan Birth date hanya akan tercover jika pencarian menggunakan query Birth date & Name. Jika pencarian menggunakan query kolom Birth date saja juga sering dilakukan, maka perlu ditambahkan juga single index (Birth date).

Drawback

Selain mempercepat pencarian, Index Key juga bisa berdampak pada performa database jika sebuah tabel memiliki terlalu banyak Index. Ketika melakukan perubahan data, database juga akan mengurutkan kembali data yang baru dimasukkan pada index. Sehingga jika terlalu banyak index, maka proses insertion, deletion dan update data akan melambat karena selain melakukan perubahan data kolom, database juga akan mengurutkan kembali data pada index. Jadi pastikan kolom yang diindex adalah kolom yang benar-benar sering dilakukan filter data. Oleh karena itu, menggunakan index pada kolom yang sering mengalami perubahan harus dihindari, karena semakin sering kolom index berubah, urutan datanya juga akan sering berubah sehingga ga efisien. Selain itu, penggunaan index juga butuh storage ekstra di harddisk untuk menyimpan data index.

PostgreSql vs MySql

PostgreSql dan MySql melakukan pendekatan yang berbeda saat menyimpan index. Pada PostgreSql, setiap index juga menyimpan referensi pada data dari kolom-kolom lainnya. Jadi misalkan kita ingin melakukan query dengan kolom Name di atas, PostgreSql langsung menampilkan data dari kolom-kolom lainnya yang berhubungan dengan index yang kita cari sehingga sedikit lebih cepat. Tapi saat melakukan perubahan, PostgreSql juga akan menginformasikannya pada index-index pada tabel tersebut bahwa ada referensi kolom yang berubah sehingga sedikit lebih lambat. Sedangkan pada MySql, setiap index hanya mereferensikan data dari kolom Primary Key saja. Jadi misalkan saat melakukan pencarian dengan kolom Name di atas, MySql mengambil Primary Key dari data tersebut, lalu dari Primary Key itu akan dicari lagi data kolom-kolom lainnya sehingga sedikit lebih lambat. Pada saat melakukan perubahan data, MySql tidak perlu melakukan perubahan referensi pada semua index pada tabel tersebut karena index pada MySql hanya mereferensikan data lewat Primary Key saja sehingga dalam hal ini MySql sedikit lebih cepat.

Verdict

Index sangat berguna untuk mempercepat pencarian data. Index hanya efisien pada tabel yang datanya banyak, sedangkan jika datanya masih sedikit sebaiknya tidak usah diindex. B-tree adalah jenis index yang umum digunakan pada database karena dianggap paling cocok untuk sebagian besar kasus dengan kecepatan O(log(n)). Selain Single Index, kita juga bisa menerapkan Composite Index untuk kasus dengan lebih dari satu kolom yang sering dicari secara bersamaan. Composite Index hanya efisien jika semua kolom pada Composite Index atau sebagian kolom yang ditulis di awal digunakan sebagai filter pencarian, jadi kolom yang ditulis belakangan tidak akan terindex jika digunakan sendirian. Primary Key dan Unique Key by default akan diindex, jadi tidak perlu dibuatkan index secara eksplisit. Index juga akan mengurangi performa jika terlalu banyak karena setiap ada proses perubahan data pada index juga akan diurutkan ulang. Sehingga kolom yang diindex sebaiknya hanya yang perlu-perlu saja.