Benefit Melakukan Indexing Pada Kolom

8 min readAug 25, 2021

Saat kita akan mengoptimalkan query pada suatu tabel yang ada pada database, sebagian besar orang orang cenderung hanya membuat indeks pada hal yang ditanyakannya saja. Biasanya pertanyaan yang sering dilontarkan seperti dibawah ini :

Saya tidak begitu mengerti apa maksud dari indexing pada suatu kolom ?
Saya mengerti dan paham , bahwa dengan melakukan indexing dapat meningkatkan efisiensi query yang kita tulis. Yang menjadi pertanyaansaya adalah apakah ada kegunaan lain dari pengindeksan atau hal hal yang perlu diperhatikan ?

Secara pribadi 2 pertanyaan ini pernah terlintas di pikiran saya, dan akhirnyapun saya bisa menemukan jawabannya.

Sebelumnya saya akan menjelaskan apa saja yang akan dibahas dalam tulisan kali ini :

Akan membahas struktur indeks yang paling banyak digunakan pada Database yaitu B-tree.
Akan membahas jenis Scanning ( Scan Types), Scan types ini merupakan cara mesin database dalam membaca data dari sebuah disk.
Melakukan percobaan untuk memahami bagaimana suatu pengindeksan berdampak pada operasi CRUD untuk berbagai tipe fields ( kolom) dan query
Mempelajari trade-off yang dibuat saat menggunakan indeks

B-tree

B-tree merupakan struktur data pohon yang paling umum digunakan dalam basis data dan file system. B-tree menjaga data tetap terurut dan seimbang. B-tree diciptakan pada tahun 1970-an. B-tree ini merupakan struktur data paling populer yang digunakan sebagai mekanisme pengindeksan default di sebagian besar database.

Meskipun ada banyak jenis struktur data pengindeksan, namun disini kita akan fokus pada B-tree saja karena karena B-tree ini adalah yang paling populer dan banyak digunakan. Untuk memahami B-tree, mari kita pertimbangkan kumpulan data sederhana, pengguna dengan fields (kolom)berikut:

Pada hakikatnya sebuah database menyimpan data dalam bentuk kepingan kepingan kecil dalam sebuah disk. Kepingan-kepingan kecil ini dinamakan dengan blocks atau pages, biasanya memiliki ukuran 4 kb. Hal ini merupakan sebuah implementasi pada perangkat keras ( Hardware) berdasarkan optimisasi. Misalnya saat kita membuat sebuah indeks pada kolom user_id , B-tree secara terpisah akan membentuak sebuah perkiraan berikut. B-tree dibentuk dimulai dari root pages dan berkaitan dengan halaman lainnya. Halaman yang menunjuk ke data disebut leaf pages. Diilustrasikan seperti dibawah ini.

Seperti yang terlihat pada gambar di atas bahwa diagram B-tree mimiliki banyak page , dan masing-masing page mengarah pada leaf page dimana kita bisa mendapatkan pointer ke lokasi data (implementasi tergantung pada database yang digunakan). Jumlah pointer yang mengarah pada child page dari parent page ini dinamakan dengan branching factor . Dalam contoh diatas terdapat 5 branching factor .

Keuntungan dari B-tree ini adalah dalam pengaksesan datanya memiliki runtime Big-O O(log(n))yang sangat efisien. (ref Big-O ).

Lalu mengapa tidak membuat sebuah indeks untuk setiap kolom dalam database ? Seperti halnya kebanyakan hal dalam Software Engineering, tentunya terdapat sebuah tradeoff. Dalam hal pengindeksan, ini merupakan sebuah pekerjaan ekstra yang harus dilakukan suatu mesin database saat kita hendak melakukan insert/update/delete records tujuannya yaitu agar menjaga si B-Tree ini tetap seimbang. Kita akan membahasa pros dan cons dari indexing pada bagian terakhir.

Scan Types

Semua operasi pada database merupakan salah satu dari operasi Create Read Update Delete (CRUD). Operasi ini memerlukan mesin database untuk bisa membaca/menulis (read/write) data dari sebuah disk, mengakses satu atau banyak block/pages data dari sebuah disk membutuhkan suatu proses pemindaian (scanning) data untuk mendapatkan blok yang tepat.Pemindaian ini salah satu operasi yang ingin dioptimalkan melali indeks. Berikut ini 4 jenis pemindaian (scan types) yang utama :

Sequential Scan: Mesin database memindai semua data secara berurutan
Parllel Seq Scan: Basis data memindai semua data secara paralel dengan n jumlah worker (dapat diperoleh dengan menjelaskan). Ini tidak selalu digunakan karena overhead saat memulai, mengelola, dan membaca data dari banyak pekerja itu terlalu banyak, tetapi digunakan untuk meningkatkan kinerja kueri yang memerlukan pemindaian data dalam jumlah besar tetapi hanya sedikit yang memenuhi kriteria pemilihan.
Index Scan: Jika kueri yang kita tulis memiliki filter pada kolom yang diindeks, maka mesin database akan menggunakan indeks B-tree untuk mendapatkan lokasi data dan hanya akan membaca pada halaman itu (cara ini merupakan yang tercepat). Tergantuan pada databasenya, jika mesin database menentukan kueri yang kita tulisa akan mengembalikan diatas 5-10% dari seluruh data .Index Scan akan melewati Seq scan, hal ini terjadi karena mesin database memutuskan overhead untuk mendapatkan lokasi halaman dari B-tree indeks, kemudian membaca halaman untuk beberapa nilai kolom dari diindeks yang tidak sepadan jika dibandingkan dengan pemindaian sekuensial sederhana dari seluruh data.
Bitmap Index Scan: Ini adalah kombinasi Index Scan dan Seq Scan, pemindaian ini digunakan bila jumlah baris yang akan dipilih terlalu besar untuk Index Scan dan terlalu rendah untuk Seq Scan.

Experiments

Di bagian ini kita akan membahas beberapa skenario yang akan digunakan untuk melihat bagaimana kinerja kueri dan untuk kasus ketika ada jenis pemindaian tertentu yang lebih direkomendasikan oleh mesin database. Idenya adalah untuk memahami mengapa kueri tertentu mungkin lebih cepat. Di bagian selanjutnya kita akan melihat pro dan kontra dari pengindeksan.

Set Up

Untuk melakukan percobaan ini dibutuhkan :

1. docker (lebih diutamakan ) untuk menjalankan postgres

pgcli menghubungkan pada postgres instance
Data dapat di Download disini

Download data ke local machine , selanjutnya lakukan setup docker yang didalamnya sudah terdapat postgres dengan folder data yang sebelumnya sudah didownload.

docker run --name pg_local -p 5432:5432 -e POSTGRES_USER=start_data_engineer \
-e POSTGRES_PASSWORD=password -e POSTGRES_DB=tutorial \
-v <your-data-folder-location>:/data -d postgres:12.2

memulai pgcli

pgcli -h  localhost -p 5432  -U start_data_engineer_tutorial

Ketikan password ketika pgcli meminta untuk menginputkan password , dan kemudian kita membuat sebuah user tables seperti dibawah ini

CREATE SCHEMA bank ;
SET search_path TO bank.public ;
CREATE TABLE bank.user(
user_id int, 
user_name varchar(50),
score int,
user_account_type char(1)
);COPY bank.user FROM 'data/user.csv' DELIMETER ',' CSV HEADER;

Explaining

Kita dapat menggunakan perintah explain untuk menjelaskan bagaimana suatu mesin database akan mengeksekusi query yang kita tulis. Yang mana dalam cara membacanya yaitu secara bottom up (ref: EXPLAIN ). Perintah explain ini memberikan kita cost metrics ( biaya metriks) yang ingin diminimalisasikan oleh mesin database.

Experiments 1

Experiments pertama yaitu melakukan query dengan perintah SELECT dengan adanya perintah filter (statement WHERE )pada fields score, dan tanpa pengindeksan pada fields score.

EXPLAIN SELECT  * FROM bank.user WHERE score = 900001;

Pada experiments pertama termasuk kedalam proses Scan Type: Parallel seq scan karena pada proses scanning perlu dilakukan pada seluruh dataset (alasannya karena tidak memiliki indeks) dan hasilnya akan sangat sedikit jika terdapat baris dari tabel.Waktu eksekusi yaitu 0.055 detik.

Experiments 2

Experiments kedua yaitu melakukan query dengan perintah SELECT dengan adanya perintah filter range lebih dari (>)pada fields score, dan tanpa pengindeksan pada fields score.

EXPLAIN SELECT  * FROM bank.user WHERE score > 900000;

Pada experiments kedua termasuk kedalam proses Scan Type: seq scan karena pada proses scanning perlu dilakukan pada seluruh dataset (alasannya karena tidak memiliki indeks). Waktu eksekusi yaitu 0.354 detik.

Experiments 3

Experiments ketiga yaitu melakukan query dengan perintah UPDATE pada fields score tanpa pengindeksan pada fields score.

EXPLAIN UPDATE   bank.user SET score = 1000000  WHERE score > 1000;

Pada experiments ketiga termasuk kedalam proses Scan Type: seq scan karena pada proses scanning perlu dilakukan pada seluruh dataset (alasannya karena tidak memiliki indeks) kemudian melakukan filtering untuk score > 1000 setelah itu melakukan update score berdasarkan filtering. Waktu eksekusi yaitu 2.447 detik.

Experiments 4

Experiments keempat yaitu melakukan query dengan perintah SELECT dengan melakukan filtering pada fields user_account_type tanpa pengindeksan pada fields user_account_type.

EXPLAIN SELECT  * FROM bank.user WHERE user_account_type = 'S';

Pada experiments keempat termasuk kedalam proses Scan Type: seq scan karena pada proses scanning perlu dilakukan pada seluruh dataset (alasannya karena tidak memiliki indeks) kemudian melakukan filtering untuk data yang memiliki user_account_type=’S’ dan kemudian memperbarui records yang memenuhi filter.ing tersebut. Waktu eksekusi yaitu 0.830 detik.

Experiments 5

Experiments kelima yaitu melakukan query dengan perintah SELECT dengan melakukan filtering pada fields score dengan pengindeksan pada fields score.

CREATE INDEX  score_idx ON bank.user (score);
-- Time 0.709s
EXPLAIN SELECT  * FROM bank.user WHERE score = 900001;

Pada experiments kelima termasuk kedalam proses Scan Type: index scan karena pada proses scanning yang berarti menggunakan indeks b-tree untuk mendapatkan referensi ke page lokasi data yang diperlukan.Waktu eksekusi yaitu 0.019 detik.

Experiments 6

Experiments keenam yaitu melakukan query dengan perintah SELECT dengan adanya perintah filter range lebih dari (>)pada fields score, dan dengan pengindeksan pada fields score.

EXPLAIN SELECT  * FROM bank.user WHERE score > 600000;

Pada experiments keenam termasuk kedalam proses Scan Type: bitmap index scan yang berarti jumlah record yang memenuhi kondisi diperkirakan terlalu besar untuk dilakukan Indeks scan dan terlalu kecil untuk menjamin Seq scan secara penuh.Waktu eksekusi yaitu 0.411 detik.

Experiments 6.2

EXPLAIN SELECT  * FROM bank.user WHERE score > 900000;

Pada experiments 6.2 termasuk kedalam proses Scan Type: seq scan digunakan meskipun kita memiliki indeks pada kolom score. Ini karena mesin database memperkirakan bahwa biaya untuk memeriksa indeks, kemudian mengambil halaman data dan mengulanginya untuk setiap skor > 600000 lebih dari sekadar Seq scan sederhana. Waktu eksekusi yaitu 0.585 detik.

Experiments 7

Experiments ketujuh yaitu melakukan query dengan perintah UPDATE dengan pengindeksan pada fields score.

EXPLAIN UPDATE bank.user SET  score = 1000000 WHERE score > 1000;

Pada experiments ketujuh termasuk kedalam proses Scan Type: bitmap index scan yang berarti jumlah record yang memenuhi kondisi diperkirakan terlalu besar untuk dilakukan Indeks scan dan terlalu kecil untuk menjamin Seq scan secara penuh.Waktu eksekusi yaitu 4.239 detik.

Experiments 8

Experiments kedelapan yaitu melakukan query dengan perintah SELECT dengan melakukan filtering pada fields user_account_type dengan pengindeksan pada fields user_account_type.

CREATE INDEX  acct_type_idx  ON bank.user (user_account_type);
-- Time: 0.846s
EXPLAIN SELECT  * FROM bank.user WHERE user_account_type = 'S';

Pada experiments kedelapan termasuk kedalam proses Scan Type: bitmap index scan yang berarti jumlah record yang memenuhi kondisi diperkirakan terlalu besar untuk dilakukan Indeks scan dan terlalu kecil untuk menjamin Seq scan secara penuh.Waktu eksekusi yaitu 0.660 detik.

CREATE SCHEMA bank;
SET search_path TO bank,public;
CREATE TABLE bank.user (
    user_id int,
    user_name varchar(50),
    score int,
    user_account_type char(1)
);
COPY bank.user FROM '/data/user.csv' DELIMITER ',' CSV HEADER;
-- Time: 1.122s

-- E1
explain select * from bank.user where score = 900001;
-- Time: 0.070s

-- E2
explain select * from bank.user where score > 900000;
-- Time: 0.422s

-- E3
explain update bank.user set score = 1000000 where score > 1000;
-- Time: 2.580s (2 seconds)

-- E4
explain select * from bank.user where user_account_type = 'S';
-- Time: 0.747s

-- Adding Index
CREATE INDEX score_idx ON bank.user (score);
CREATE INDEX acct_type_idx ON bank.user (user_account_type);

-- E5
explain select * from bank.user where score = 900001;
-- Time: 0.017s

-- E6
explain select * from bank.user where score > 900000;
-- Time: 1.351s (a second)
explain select * from bank.user where score > 600000;
-- Time: 1.675s (a second)

-- E7
explain update bank.user set score = 1000000 where score > 1000;
-- Time: 8.627s (8 seconds)

-- E8
explain select * from bank.user where user_account_type = 'S';
-- Time: 0.883s (a moment)

Cardinality

Cardinality didefinisikan sebagai keunikan pada setiap field data, contohya jika kita memiliki fields gender dengan nilai M atau F sebagai nilai yang dapat diterima.Maka dapat dikatakan bahwa field tersebut memiliki kardinalitas yang rendah. Cardinality dibagi ke dalam 2 jenis yaitu

high cardinality fields dengan banyak nilai unik (misalnya score )
low cardinality fileds dengan beberapa nilai unik (misalnya user_account_type )

Kesimpulan

semoga berdasarkan percobaan diatas memberikan pemahaman yang baik tentang kapan dan bagaimana menggunakan indeks, bagaimana menggunakan, menjelaskan untuk memeriksa kinerja kueri , dan apa arti berbagai jenis scanning.

Kelebihan menggunakan indeks:

Query dengan filtering pada kolom yang diindeks jauh lebih cepat daripada yang tidak. Bisa dilihat pada Experiments 1 dan Experiments 5

Kekurangan menggunakan indeks:

Adanya Penurunan performa untuk operasi insert/update/delete, karena B-tree juga harus dikelola. Bisa dilihat dari perbandingan Experiments 7 dan Experiments 3, waktu update dengan indeks 8.627 detik dibandinng tanpa indeks yaitu 2.447 detik.
Tergantung dari jenis SQL yang digunakan, operasi Create , Update, Delete dapat dikunci saat kolom sedang diindeks.
Indeks tidak akan selalu digunakan, tergantung pada estimasi ukuran dari hasil kueri (menggunakan statement EXPLAIN untuk memeriksa query plan).
Peningkatan performa indeks untuk kolom yang memiliki kardinalitas rendah akan lebih rendah dibandingkan dengan kolom dengan kardinalitas tinggi. Dalam contoh ini , pengurangan latensi dengan menambahkan indeks pada kolom yang memiliki kardinalitas rendah yaitu user_account_type adalah 20%, sedangkan pengurangan latensi dengan menambahkan indeks pada kolom score yang memiliki kardinalitas tinggi adalah 65%.