# 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

| Kolom | data type | Primary key |
| --- | --- | --- |
| id | int | Yes |
| name | text | No |

```sql
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

```sql
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

```sql
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?

```sql
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](https://www.postgresql.org/docs/current/pgtrgm.html))

```sql
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
*/
```