GiST Index

B-tree mengurutkan nilai skalar, dan itu menyelesaikan sebagian besar kebutuhan. Tetapi bagaimana dengan rentang waktu yang saling tumpang tindih, titik koordinat dengan jarak terdekat, atau teks yang hampir mirip? Pertanyaan “berapa nilai antara a dan b” tidak lagi relevan di sana — yang dibutuhkan adalah “apa yang beririsan” dan “apa yang paling dekat”. GiST (Generalized Search Tree) adalah kerangka index PostgreSQL untuk kelas data seperti ini. Chapter ini memakai dua kasus nyata — reservasi ruang rapat dan jaringan gerai — untuk menunjukkan kapan GiST menjadi satu-satunya pilihan yang benar.

GiST Sebagai Kerangka, Bukan Satu Algoritma #

Berbeda dengan B-tree yang punya struktur tetap, GiST adalah kerangka (template) yang diisi strategi pencarian berbeda untuk setiap jenis data. Strategi tersebut dibungkus dalam operator class: range_ops untuk tipe range, point_ops untuk titik geometri, trgm_ops untuk teks mirip (lewat extension pg_trgm), dan sebagainya. Ketika kita menulis USING gist (kolom), operator class yang menentukan operator mana yang bisa dipercepat.

Kebutuhan data	Operator class	Operator kunci
Rentang (range) overlap	`range_ops`	`&&`, `@>`, `<@`
Titik geometri, jarak	`point_ops`	`<->` (kNN), `<<->>`
Teks similar	`trgm_ops` (pg_trgm)	`%`, `<->`
Alamat IP prefix	`inet_ops`	`<<`, `>>=`, `&&`

Dua hal dari tabel ini layan digarisbawahi. Pertama, operator tumpang tindih && dan tetangga terdekat <-> tidak dimiliki B-tree sama sekali — tidak ada cara mempercepat query tersebut tanpa GiST (atau SP-GiST untuk kasus tertentu). Kedua, exclusion constraint yang kita pakai di chapter Exclusion Constraints bekerja di atas struktur yang sama, sehingga memahami GiST juga berarti memahami cara kerja EXCLUDE USING gist.

Menyiapkan Data Studi Kasus #

Dua tabel siap dipakai: reservasi menyimpan rentang waktu peminjaman ruang rapat, dan gerai menyimpan titik koordinat 1024 gerai di grid kota 32 x 32 km. Keduanya diisi secara deterministik lewat generate_series:

sql
buat-tabel.sql
-- Reservasi ruang rapat: satu baris = satu rentang waktu (tstzrange).
CREATE TABLE reservasi (
    id      integer PRIMARY KEY,
    ruang   text NOT NULL,
    pemohon text NOT NULL,
    rentang tstzrange NOT NULL
);

INSERT INTO reservasi
SELECT g,
       (ARRAY['Rapat A', 'Rapat B', 'Rapat C'])[1 + g % 3],
       'Pemohon ' || g,
       tstzrange(
           TIMESTAMPTZ '2026-03-02 08:00:00+07' + (g * 7 || ' hours')::interval,
           TIMESTAMPTZ '2026-03-02 08:00:00+07' + (g * 7 || ' hours')::interval
               + ((1 + g % 4) || ' hours')::interval
       )
FROM generate_series(1, 1000) AS g;

-- 1024 gerai pada grid koordinat kota 32 x 32 km.
CREATE TABLE gerai (
    id     integer PRIMARY KEY,
    nama   text NOT NULL,
    lokasi point NOT NULL
);

INSERT INTO gerai
SELECT g, 'Gerai ' || g, point(g % 32, g / 32)
FROM generate_series(1, 1024) AS g;

ANALYZE reservasi;
ANALYZE gerai;

SELECT id, ruang, rentang
FROM reservasi
WHERE id BETWEEN 9 AND 13
ORDER BY id;

SELECT id, nama, lokasi
FROM gerai
WHERE id IN (1, 261, 1024)
ORDER BY id;

Output yang Dihasilkan:

text
CREATE TABLE
INSERT 0 1000
CREATE TABLE
INSERT 0 1024
ANALYZE
ANALYZE
 id |  ruang  |                       rentang                       
----+---------+-----------------------------------------------------
  9 | Rapat A | ["2026-03-04 23:00:00+07","2026-03-05 01:00:00+07")
 10 | Rapat B | ["2026-03-05 06:00:00+07","2026-03-05 09:00:00+07")
 11 | Rapat C | ["2026-03-05 13:00:00+07","2026-03-05 17:00:00+07")
 12 | Rapat A | ["2026-03-05 20:00:00+07","2026-03-05 21:00:00+07")
 13 | Rapat B | ["2026-03-06 03:00:00+07","2026-03-06 05:00:00+07")
(5 rows)

  id  |    nama    | lokasi 
------+------------+--------
    1 | Gerai 1    | (1,0)
  261 | Gerai 261  | (5,8)
 1024 | Gerai 1024 | (0,32)
(3 rows)

Perhatikan dua detail pada cara pembuatan datanya. Kolom rentang bertipe tstzrange — tipe range dengan timestamp dan zona waktu — yang isinya dibangun dari tstzrange(awal, akhir), dengan awal dan akhir dihitung dari kelipatan 7 jam sejak 2 Maret 2026. Sedangkan gerai.lokasi bertipe point bawaan PostgreSQL, dan point(g % 32, g / 32) menyusunnya dalam grid teratur: gerai 1 di (1, 0), gerai 2 di (2, 0), hingga gerai 1024 di (0, 32).

Membuat Index GiST #

Pembuatan index GiST memakai sintaks USING gist, satu untuk tiap kolom dengan jenis data berbeda:

sql
index-gist.sql
-- GiST untuk rentang waktu dan titik koordinat sekaligus.
CREATE INDEX idx_reservasi_rentang
    ON reservasi USING gist (rentang);

CREATE INDEX idx_gerai_lokasi
    ON gerai USING gist (lokasi);

-- Rapat mendadak Selasa 5 Maret 12:00-15:00: ada bentrok?
SELECT id, ruang, pemohon, rentang
FROM reservasi
WHERE rentang && tstzrange(TIMESTAMPTZ '2026-03-05 12:00:00+07',
                           TIMESTAMPTZ '2026-03-05 15:00:00+07')
ORDER BY id;

-- Seberapa sibuk kamar rapat sepanjang Kamis 5 Maret?
SELECT count(*) AS reservasi_sehari
FROM reservasi
WHERE rentang && tstzrange(TIMESTAMPTZ '2026-03-05 00:00:00+07',
                           TIMESTAMPTZ '2026-03-06 00:00:00+07');

Output yang Dihasilkan:

text
CREATE INDEX
CREATE INDEX
 id |  ruang  |  pemohon   |                       rentang                       
----+---------+------------+-----------------------------------------------------
 11 | Rapat C | Pemohon 11 | ["2026-03-05 13:00:00+07","2026-03-05 17:00:00+07")
(1 row)

 reservasi_sehari 
------------------
                4
(1 row)

Perintah CREATE INDEX tanpa menyebut metode memilih B-tree secara default, sehingga USING gist wajib eksplisit. Setelah perintah di atas, pg_indexes akan menampilkan dua index baru dengan metode gist — silakan verifikasi dengan query SELECT indexname FROM pg_indexes WHERE tablename IN ('reservasi','gerai') ORDER BY indexname;.

Query Tumpang Tindih Rentang #

Pertanyaan operasional ruang rapat selalu berbunyi “apakah ada yang sudah memesan di sekitar jam ini?” — alias deteksi tumpang tindih dengan operator &&:

sql
query-overlap.sql
-- Reservasi apa saja yang bertabrakan dengan slot Senin 5 Maret 12:00-15:00?
SELECT id, ruang, pemohon, rentang
FROM reservasi
WHERE rentang && tstzrange(TIMESTAMPTZ '2026-03-05 12:00:00+07',
                           TIMESTAMPTZ '2026-03-05 15:00:00+07')
ORDER BY id;

Output yang Dihasilkan:

text
 id |  ruang  |  pemohon   |                       rentang                       
----+---------+------------+-----------------------------------------------------
 11 | Rapat C | Pemohon 11 | ["2026-03-05 13:00:00+07","2026-03-05 17:00:00+07")
(1 row)

Query ini yang menjadi tulang punggung pencegahan double-booking: cukup uji rentang_baru && rentang_lama sebelum menyisipkan reservasi baru, atau lebih ketat lagi, biarkan exclusion constraint yang menolaknya (materi chapter Exclusion Constraints). Tanpa GiST, PostgreSQL harus memeriksa seribu baris satu per satu; dengan index, pemeriksaan menyusut menjadi segelintir kandidat di cabang tree yang relevan.

Tetangga Terdekat dengan <-> #

Fitur khas GiST yang paling bersinar adalah pencarian tetangga terdekat (k-nearest neighbor). Operator <-> menghitung jarak, dan GiST mampu menyajikan baris dalam urutan jarak — sehingga ORDER BY lokasi <-> titik LIMIT 3 tidak perlu mengurutkan seluruh tabel:

sql
query-knn.sql
-- Kurir di titik (5.2, 7.7): tiga gerai terdekat, jarak dihitung operator <->.
SELECT id, nama, lokasi,
       round((lokasi <-> point '(5.2, 7.7)')::numeric, 3) AS jarak_km
FROM gerai
ORDER BY lokasi <-> point '(5.2, 7.7)'
LIMIT 3;

Output yang Dihasilkan:

text
 id  |   nama    | lokasi | jarak_km 
-----+-----------+--------+----------
 261 | Gerai 261 | (5,8)  |    0.361
 229 | Gerai 229 | (5,7)  |    0.728
 262 | Gerai 262 | (6,8)  |    0.854
(3 rows)

Hasilnya tiga gerai terdekat dari titik kurir, lengkap dengan jaraknya dihitung langsung dari operator yang sama. Mari kita bedah query-nya:

ORDER BY lokasi <-> point '(5.2, 7.7)': klausa urutan memakai operator jarak GiST. Planner tahu index dapat menyajikan baris sudah terurut sesuai jarak, sehingga tidak ada pengurutan penuh atas 1024 baris.
LIMIT 3: hanya tiga baris pertama yang diambil — index berhenti begitu tiga tetangga terdekat terkumpul, sisa tree tidak disentuh.
round((...)::numeric, 3): jarak dikembalikan sebagai double precision lalu dibulatkan tiga desimal agar tampilan stabil; nilai jarak penuh tetap dipakai untuk pengurutan.

Melihat Rencana Eksekusi #

Bukti bahwa index benar-benar dipakai dilihat lewat EXPLAIN. Pada tabel latihan kita yang hanya seribu baris, planner justru memilih Seq Scan karena membaca seluruh tabel lebih murah daripada menelusuri index — perilaku yang benar dan akan berbalik pada tabel jutaan baris. Untuk melihat rencana berbasis indexnya, file berikut memakai SET enable_seqscan = off (teknik diagnosa, bukan setelan produksi) dan memakai atribut manual="true" karena biaya yang ditampilkan bergantung lingkungan:

sql
rencana-gist.sql
-- Statistik diperbarui dulu supaya perkiraan planner akurat.
ANALYZE reservasi;
ANALYZE gerai;

-- Tabel kecil: planner memilih Seq Scan. Matikan sementara untuk
-- MELIHAH rencana berbasis index yang akan dipakai saat tabel besar.
SET enable_seqscan = off;

EXPLAIN
SELECT id, ruang
FROM reservasi
WHERE rentang && tstzrange(TIMESTAMPTZ '2026-03-05 12:00:00+07',
                           TIMESTAMPTZ '2026-03-05 15:00:00+07');

EXPLAIN
SELECT id, nama
FROM gerai
ORDER BY lokasi <-> point '(5.2, 7.7)'
LIMIT 3;

Output yang Dihasilkan:

text
ANALYZE
ANALYZE
SET
                                         QUERY PLAN                                           
---------------------------------------------------------------------------------------------
 Index Scan using idx_reservasi_rentang on reservasi  (cost=0.14..8.16 rows=1 width=12)
   Index Cond: (rentang && '["2026-03-05 12:00:00+07","2026-03-05 15:00:00+07")'::tstzrange)
(2 rows)

                                       QUERY PLAN                                         
-----------------------------------------------------------------------------------------
 Limit  (cost=0.14..0.40 rows=3 width=21)
   ->  Index Scan using idx_gerai_lokasi on gerai  (cost=0.14..88.62 rows=1024 width=21)
         Order By: (lokasi <-> '(5.2,7.7)'::point)
(3 rows)

Dua rencana di atas menceritakan dua jalur berbeda. Query rentang memakai Index Scan dengan Index Cond: (rentang && ...) — operator tumpang tindih langsung dipuaskan oleh index. Query kNN memakai Index Scan dengan Order By: (lokasi <-> ...): index dibaca dalam urutan jarak, dan node Limit memotong setelah tiga baris terkumpul. Angka biaya di mesin Anda akan sedikit berbeda, tetapi kedua pola ini akan tetap terlihat.

Kapan Memilih GiST #

Keputusan memilih GiST hampir selalu mengikuti operator, bukan tipe datanya. Jika query memakai && pada range, <-> pada titik, << pada alamat jaringan, atau exclusion constraint — GiST adalah kandidat utama. Sebaliknya, untuk kesetaraan dan rentang pada angka/teks biasa, B-tree lebih kecil dan lebih cepat. Ketika data bertipe geometri dan kebutuhan melampaui titik-titik sederhana (poligon, garis, proyeksi koordinat), saat itulah PostGIS mengambil alih peran GiST operator class bawaan — pembahasan mendalamnya menunggu di chapter khusus PostGIS pada Section Extension dan Ekosistem.

Ukuran index adalah kompromi berikutnya yang perlu kita kelola dengan sadar; dan untuk tabel raksasa yang datanya mengalir terurut, PostgreSQL punya index yang jauh lebih ringkas lagi — BRIN, topik chapter berikutnya.

Referensi #

Berkas Sumber

Berkas pendukung halaman ini dapat diunduh dan dijalankan langsung sesuai penjelasan di atas.

sql
-- Reservasi ruang rapat: satu baris = satu rentang waktu (tstzrange).
CREATE TABLE reservasi (
    id      integer PRIMARY KEY,
    ruang   text NOT NULL,
    pemohon text NOT NULL,
    rentang tstzrange NOT NULL
);

INSERT INTO reservasi
SELECT g,
       (ARRAY['Rapat A', 'Rapat B', 'Rapat C'])[1 + g % 3],
       'Pemohon ' || g,
       tstzrange(
           TIMESTAMPTZ '2026-03-02 08:00:00+07' + (g * 7 || ' hours')::interval,
           TIMESTAMPTZ '2026-03-02 08:00:00+07' + (g * 7 || ' hours')::interval
               + ((1 + g % 4) || ' hours')::interval
       )
FROM generate_series(1, 1000) AS g;

-- 1024 gerai pada grid koordinat kota 32 x 32 km.
CREATE TABLE gerai (
    id     integer PRIMARY KEY,
    nama   text NOT NULL,
    lokasi point NOT NULL
);

INSERT INTO gerai
SELECT g, 'Gerai ' || g, point(g % 32, g / 32)
FROM generate_series(1, 1024) AS g;

ANALYZE reservasi;
ANALYZE gerai;

SELECT id, ruang, rentang
FROM reservasi
WHERE id BETWEEN 9 AND 13
ORDER BY id;

SELECT id, nama, lokasi
FROM gerai
WHERE id IN (1, 261, 1024)
ORDER BY id;

sql
-- GiST untuk rentang waktu dan titik koordinat sekaligus.
CREATE INDEX idx_reservasi_rentang
    ON reservasi USING gist (rentang);

CREATE INDEX idx_gerai_lokasi
    ON gerai USING gist (lokasi);

-- Rapat mendadak Selasa 5 Maret 12:00-15:00: ada bentrok?
SELECT id, ruang, pemohon, rentang
FROM reservasi
WHERE rentang && tstzrange(TIMESTAMPTZ '2026-03-05 12:00:00+07',
                           TIMESTAMPTZ '2026-03-05 15:00:00+07')
ORDER BY id;

-- Seberapa sibuk kamar rapat sepanjang Kamis 5 Maret?
SELECT count(*) AS reservasi_sehari
FROM reservasi
WHERE rentang && tstzrange(TIMESTAMPTZ '2026-03-05 00:00:00+07',
                           TIMESTAMPTZ '2026-03-06 00:00:00+07');

sql
-- Kurir di titik (5.2, 7.7): tiga gerai terdekat, jarak dihitung operator <->.
SELECT id, nama, lokasi,
       round((lokasi <-> point '(5.2, 7.7)')::numeric, 3) AS jarak_km
FROM gerai
ORDER BY lokasi <-> point '(5.2, 7.7)'
LIMIT 3;

sql
-- Reservasi apa saja yang bertabrakan dengan slot Senin 5 Maret 12:00-15:00?
SELECT id, ruang, pemohon, rentang
FROM reservasi
WHERE rentang && tstzrange(TIMESTAMPTZ '2026-03-05 12:00:00+07',
                           TIMESTAMPTZ '2026-03-05 15:00:00+07')
ORDER BY id;

sql
-- Statistik diperbarui dulu supaya perkiraan planner akurat.
ANALYZE reservasi;
ANALYZE gerai;

-- Tabel kecil: planner memilih Seq Scan. Matikan sementara untuk
-- MELIHAH rencana berbasis index yang akan dipakai saat tabel besar.
SET enable_seqscan = off;

EXPLAIN
SELECT id, ruang
FROM reservasi
WHERE rentang && tstzrange(TIMESTAMPTZ '2026-03-05 12:00:00+07',
                           TIMESTAMPTZ '2026-03-05 15:00:00+07');

EXPLAIN
SELECT id, nama
FROM gerai
ORDER BY lokasi <-> point '(5.2, 7.7)'
LIMIT 3;