Indexing

Indexing adalah proses penyusunan data sehingga mudah dalam pencarian data yang diinginkan (seperti index pada kamus) . Pada indexing dilakukan dengan cara menempatkan struktur data yang beriisi keys beserta referensinya ke data sebenarnya pada table.

Umunya ketika membuat table dengan primary key secara default kolom yang menjadi primary key akan dibuatkan indexnya menggunakan B-Tree (Balance Tree)

Contoh : Anggaplah kita terdapat sebuah database (menggunakan postgres) yang memiliki table employees yang berisi 1000000 recrod dengan stuktur data sebagai berikut

explain analyze select * from emplyees where name = 'Zs';
/* OUTPUT
Gather  (cost=1000.00..11310.94 rows=6 width=10) (actual time=3.088..47.719 rows=25 loops=1)  
  Workers Planned: 2  
  Workers Launched: 2  
  ->  Parallel Seq Scan on employees  (cost=0.00..10310.34 rows=2 width=10) (actual time=1.931..18.586 rows=8 loops=3)  
        Filter: (name = 'Zs'::text)  
        Rows Removed by Filter: 333325  
Planning Time: 0.364 ms  
Execution Time: 47.785 ms
*/


explain analyze select * from employees where id = 100;
/* OUTPUT
Index Scan using employees_pkey on employees  (cost=0.42..8.44 rows=1 width=10) (actual time=0.093..0.095 rows=1 loops=1)  
  Index Cond: (id = 100)  
Planning Time: 0.237 ms  
Execution Time: 0.178 ms
*/

Kita bisa melihat dari dua query diatas menghasilkan waktu eksekusi yang sangat berbeda kenapa bisa seperti itu?. Untuk query pertama pencarian bedasarkan kolumn name tidak menggunakan indexing, sehingga pencarian dilakukan dengan melakukan pengecekan pada setiap baris pada kolom name pada table employees.

Sedangkan pada query kedua, pencarian menggunakan id (ini di indexing) proses pencarian dilakukan dengan menggunakan scanning index yang sudah dibuat sehingga tidak perlu melakukan pengecekan pada setiap baris pada table employees.

Bagaimana membuat index dan prosesnya pada Postgres?

Untuk membuat index perlu menjalankan query

CREATE INDEX nama_index on nama_table(nama_kolumn);

/* menambahakna index untuk kolom name
CREATE INDEX EPLOYEE_NAME on employees(name);
*/

Proses yang terjadi dibalik CREATE INDEX adalah Postgres akan pembacaan data secara menyeluruh terlebih dahulu kemudian Postgress akan membuat B-Tree berdasarkan kolom tersebut, sehingga waktu yand dibutuhkan untuk pembuatan index berdasarkan banyaknya data yang ada pada table tersebut. Kita bisa melihat hasil perbedaan performa query pertama setelah di indexing

explain analyze select * from employees where name = 'Zs';

/*
Bitmap Heap Scan on employees  (cost=4.47..27.93 rows=6 width=10) (actual time=0.326..0.363 rows=25 loops=1)  
  Recheck Cond: (name = 'Zs'::text)  
  Heap Blocks: exact=25  
  ->  Bitmap Index Scan on employee_name  (cost=0.00..4.47 rows=6 width=0) (actual time=0.318..0.318 rows=25 loops=1)  
        Index Cond: (name = 'Zs'::text)  
Planning Time: 4.501 ms  
Execution Time: 0.391 ms
*/

Pembuatan index dengan penggunaan CREATE INDEX terlihat sangat menjanjikan namun kenapa query berikut ini tidak melakukan index scanning?

explain analyze select * from employees where name like '%Zs'

/* OUTPUT
Gather  (cost=1000.00..11319.34 rows=90 width=10) (actual time=0.425..44.853 rows=266 loops=1)  
  Workers Planned: 2  
  Workers Launched: 2  
  ->  Parallel Seq Scan on employees  (cost=0.00..10310.34 rows=38 width=10) (actual time=0.203..22.971 rows=89 loops=3)  
        Filter: (name ~~ '%Zs'::text)  
        Rows Removed by Filter: 333245  
Planning Time: 0.384 ms  
Execution Time: 44.896 ms
*/

Hal ini bisa terjadi karena secara default index yang dibuat pada Postgress mengguakan B-Tree yang mana struktur data ini di design untuk melakukan perbandingan secara terurut seperti =, >, <, >=, <= dan LIKE tanpa pengunaan wildcard di depan yang menyebabkan Postgress tidak tahu bagaimana cara menghandle query tersebut pada B-tree, sehingga Postgress harus melakukan scanning secara sekuensial pada setiap baris pada table employees.

Agar query menggunakan wildcard dapat berjalan dengan lebih baik hal yang perlu dilakukan adalah merubah indexingnya menggunakan trigam (Trigraph). Trigram adalah sekelompok tiga karakter berurutan yang diambil dari sebuah kata, hal ini memungkinkan untuk mengukur kemiripan dua buah kata (https://www.postgresql.org/docs/current/pgtrgm.html)

CREATE EXTENSION pg_trgm;  
create INDEX trgm_employee_name on employees USING gin (name gin_trgm_ops);

explain analyze select * from employees where name like '%Za';
/* OUTPUT
Bitmap Heap Scan on employees  (cost=17.56..342.82 rows=90 width=10) (actual time=0.478..2.449 rows=230 loops=1)  
  Recheck Cond: (name ~~ '%Za'::text)  
  Rows Removed by Index Recheck: 463  
  Heap Blocks: exact=641  
  ->  Bitmap Index Scan on trgm_employee_name  (cost=0.00..17.53 rows=90 width=0) (actual time=0.288..0.288 rows=693 loops=1)  
        Index Cond: (name ~~ '%Za'::text)  
Planning Time: 3.182 ms  
Execution Time: 2.543 ms
*/