GiST yang kita bahas sebelumnya bekerja seperti lemari arsip bertingkat: setiap node menyimpan pembungkus yang boleh tumpang tindih dengan pembungkus lain, sehingga satu pencarian harus menelusuri semua cabang yang mungkin beririsan. Ada keluarga struktur data yang bekerja sebaliknya — quadtree, k-d tree, dan radix tree — membagi ruang menjadi bagian-bagian yang saling lepas, sehingga setiap nilai jatuh ke tepat satu partisi dan pencarian cukup menuruni satu jalur. PostgreSQL menyediakan kerangka untuk struktur-partisi ini lewat SP-GiST (Space-Partitioned GiST). Kasus pakainya khas: routing alamat IP di log akses, pencarian prefix nomor telepon, dan penempatan titik pada peta. Di chapter ini kita membangun ketiganya di atas data situs web Toko Maju Jaya, lalu membandingkan kapan SP-GiST mengalahkan GiST biasa.

Dari Pembungkus ke Partisi Ruang #

Perbedaan kedua keluarga ini paling mudah dipahami lewat satu pertanyaan: ketika sebuah node penuh dan harus dipecah, apa yang terjadi? GiST memecah node menjadi dua pembungkus yang boleh tumpang tindih — sebuah titik di perbatasan dua kotak pembungkus harus dicari di kedua cabang. SP-GiST memecah node menjadi partisi yang tidak tumpang tindih sama sekali — setiap nilai hanya punya satu rumah, dan pencarian menuruni satu jalur dari akar ke daun.

Struktur-partisi yang didukung PostgreSQL mencakup quadtree yang membagi bidang menjadi empat kuadran berulang, k-d tree yang membagi ruang berselang-sumbu, dan radix tree yang mempartisi teks atau bit berdasarkan prefix. Konsekuensinya: pencarian prefix seperti “semua alamat di dalam 103.10.128.0/24” atau “semua nomor diawali 0812” hanya menyentuh cabang-cabang yang benar-benar relevan, bukan seluruh pohon.

Demo: Log Akses dengan Alamat IP #

Tabel log_akses merekam 50.000 permintaan ke situs web Toko Maju Jaya. Kolom alamat bertipe inet diisi dari empat jaringan: dua jaringan internal, satu subnet kantor cabang, dan satu rentang pengunjung luar:

sql buat-tabel.sql 
-- Log akses situs web Toko Maju Jaya: 50.000 permintaan
-- yang datang dari empat jaringan berbeda.
CREATE TABLE log_akses (
    id      integer PRIMARY KEY,
    alamat  inet NOT NULL,
    negara  text NOT NULL
);

INSERT INTO log_akses (id, alamat, negara)
SELECT g,
       (CASE (g % 4)
          WHEN 0 THEN '192.168.' || (g % 3 + 1) || '.'
          WHEN 1 THEN '10.0.' || (g % 3) || '.'
          WHEN 2 THEN '103.10.128.'
          ELSE '203.0.113.'
        END || (g % 250)::text)::inet,
       CASE WHEN g % 4 = 3 THEN 'singapura' ELSE 'indonesia' END
FROM generate_series(1, 50000) AS g;

ANALYZE log_akses;

SELECT id, alamat, negara
FROM log_akses
ORDER BY id
LIMIT 3;

Output yang Dihasilkan:

text 
CREATE TABLE
INSERT 0 50000
ANALYZE
 id |    alamat    |  negara   
----+--------------+-----------
  1 | 10.0.1.1     | indonesia
  2 | 103.10.128.2 | indonesia
  3 | 203.0.113.3  | singapura
(3 rows)

Ekspresi CASE membangun alamat dari modulus g: seperempat baris jatuh ke masing-masing jaringan, sehingga query routing nanti punya jawaban yang terukur. Tipe inet menyimpan alamat beserta subnet mask-nya — operasi jaringan seperti “berada di dalam subnet” menjadi operator bawaan database, bukan manipulasi string.

Query Routing dengan SP-GiST #

Operator << pada inet berarti contained within: alamat di sisi kiri berada di dalam subnet di sisi kanan. Persis inilah bahasa tabel routing, dan index SP-GiST menjawabnya lewat penurunan prefix bit:

sql index-spgist.sql 
-- Index SP-GiST pada kolom inet: setiap node mempartisi
-- ruang alamat berdasarkan prefix bit, seperti tabel routing.
CREATE INDEX idx_spgist_alamat ON log_akses USING spgist (alamat);

-- << berarti "alamat ini berada DI DALAM subnet ini"
SELECT count(*) AS dari_subnet_kantor
FROM log_akses
WHERE alamat << '103.10.128.0/24';

-- Jaringan internal 10.0.0.0/8 juga satu cabang routing
SELECT count(*) AS dari_jaringan_internal
FROM log_akses
WHERE alamat << '10.0.0.0/8';

SELECT id, alamat, negara
FROM log_akses
WHERE alamat << '103.10.128.0/24'
ORDER BY id
LIMIT 3;

Output yang Dihasilkan:

text 
CREATE INDEX
 dari_subnet_kantor 
--------------------
              12500
(1 row)

 dari_jaringan_internal 
------------------------
                  12500
(1 row)

 id |    alamat     |  negara   
----+---------------+-----------
  2 | 103.10.128.2  | indonesia
  6 | 103.10.128.6  | indonesia
 10 | 103.10.128.10 | indonesia
(3 rows)

Dua query counting memberi angka pembanding: 12.500 permintaan berasal dari subnet kantor 103.10.128.0/24 dan 12.500 lagi dari seluruh jaringan internal 10.0.0.0/8. Query terakhir memperlihatkan contoh barisnya — 103.10.128.2, 103.10.128.6, 103.10.128.10 — semua berprefiks 103.10.128. Mari kita lihat rencana eksekusi nyata untuk query routing ini. Output berikut disalin manual dari eksekusi nyata; angka waktu dan estimasi baris bervariasi antar mesin dan antar ANALYZE, tetapi bentuk rencananya sama:

sql explain-analyze.sql 
-- Rencana eksekusi nyata: routing subnet pada kolom inet.
EXPLAIN ANALYZE SELECT count(*) FROM log_akses
WHERE alamat << '103.10.128.0/24';

-- Rencana eksekusi nyata: pencarian prefix pada kolom text.
EXPLAIN ANALYZE SELECT count(*) FROM pelanggan_telepon
WHERE nomor LIKE '0812-%';

Output yang Dihasilkan:

text 
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=837.58..837.59 rows=1 width=8) (actual time=2.931..2.932 rows=1 loops=1)
   ->  Bitmap Heap Scan on log_akses  (cost=332.45..806.56 rows=12409 width=0) (actual time=0.740..2.404 rows=12500 loops=1)
         Recheck Cond: (alamat << '103.10.128.0/24'::inet)
         Heap Blocks: exact=319
         ->  Bitmap Index Scan on idx_spgist_alamat  (cost=0.00..329.34 rows=12409 width=0) (actual time=0.703..0.704 rows=12500 loops=1)
               Index Cond: (alamat << '103.10.128.0/24'::inet)
 Planning Time: 0.270 ms
 Execution Time: 2.984 ms
(8 rows)

                                                               QUERY PLAN                                                                
-----------------------------------------------------------------------------------------------------------------------------------------
 Aggregate  (cost=923.52..923.53 rows=1 width=8) (actual time=3.228..3.229 rows=1 loops=1)
   ->  Bitmap Heap Scan on pelanggan_telepon  (cost=366.13..891.95 rows=12626 width=0) (actual time=0.956..2.688 rows=12500 loops=1)
         Filter: (nomor ~~ '0812-%'::text)
         Heap Blocks: exact=368
         ->  Bitmap Index Scan on idx_spgist_nomor  (cost=0.00..362.97 rows=12626 width=0) (actual time=0.916..0.917 rows=12500 loops=1)
               Index Cond: (nomor ^@ '0812-'::text)
 Planning Time: 0.161 ms
 Execution Time: 3.250 ms
(8 rows)

Rencana tersebut menunjukkan Bitmap Index Scan on idx_spgist_alamat dengan Index Cond: (alamat << '103.10.128.0/24') — operator routing diterjemahkan menjadi penurunan prefix di radix tree bit alamat, lalu blok-blok kandidat dikumpulkan lewat bitmap. Tidak ada pemindaian seluruh tabel: hanya halaman yang memuat alamat subnet kantor yang disentuh.

Pencarian Prefix dengan Radix Tree #

Kasus kedua SP-GiST yang sama klasiknya: teks berprefix. Tabel pelanggan_telepon menyimpan 50.000 pelanggan dengan nomor yang dibangun dari empat prefix operator (0812, 0813, 0814, 0815). Pertanyaan bisnis seperti “seluruh pelanggan nomor operator 0812” adalah query prefix murni:

sql prefix-teks.sql 
-- Daftar pelanggan beserta nomor teleponnya:
-- pencarian prefix "semua nomor 0812" adalah kasus radix tree.
CREATE TABLE pelanggan_telepon (
    id     integer PRIMARY KEY,
    nama   text NOT NULL,
    nomor  text NOT NULL
);

INSERT INTO pelanggan_telepon (id, nama, nomor)
SELECT g,
       'Pelanggan ' || lpad(g::text, 5, '0'),
       '081' || ((g % 4) + 1)::text || '-' || lpad(((g * 13) % 100000)::text, 5, '0')
FROM generate_series(1, 50000) AS g;

CREATE INDEX idx_spgist_nomor ON pelanggan_telepon USING spgist (nomor);
ANALYZE pelanggan_telepon;

SELECT count(*) AS pelanggan_prefix_0812
FROM pelanggan_telepon
WHERE nomor LIKE '0812-%';

SELECT nama, nomor
FROM pelanggan_telepon
WHERE nomor LIKE '0812-%'
ORDER BY nomor
LIMIT 3;

Output yang Dihasilkan:

text 
CREATE TABLE
INSERT 0 50000
CREATE INDEX
ANALYZE
 pelanggan_prefix_0812 
-----------------------
                 12500
(1 row)

      nama       |   nomor    
-----------------+------------
 Pelanggan 23077 | 0812-00001
 Pelanggan 15385 | 0812-00005
 Pelanggan 07693 | 0812-00009
(3 rows)

Ada 12.500 pelanggan berprefix 0812, dan tiga baris pertama memperlihatkan bentuk nomornya. Rencana eksekusi untuk query LIKE '0812-%' (bagian kedua output manual di atas) memperlihatkan detail menarik: planner menuliskan Filter: (nomor ~~ '0812-%') tetapi Index Cond: (nomor ^@ '0812-'). Operator ^@ adalah starts with — planner menulis ulang pola LIKE berprefix menjadi operator keanggotaan prefix agar radix tree pada index SP-GiST bisa dipakai. Pola LIKE yang tidak berprefix (misalnya %0812) kehilangan awalan pasti dan tidak bisa dilayani index ini.

Operator Class yang Tersedia #

Access method SP-GiST tidak mengikat diri pada satu struktur — kelas operatorlah yang menentukan partisi apa yang dipakai untuk tipe data tertentu. Katalog sistem mencatat semuanya, dan query berikut membacanya langsung dari server:

sql katalog-opclass.sql 
-- Semua access method index yang tersedia di server ini.
SELECT amname AS metode_index
FROM pg_am
WHERE amname IN ('btree', 'hash', 'gist', 'spgist', 'gin', 'brin')
ORDER BY amname;

-- Kelas operator bawaan SP-GiST per tipe data.
SELECT opc.opcname AS kelas_operator,
       opc.opcintype::regtype AS tipe_data
FROM pg_opclass opc
JOIN pg_am am ON am.oid = opc.opcmethod
WHERE am.amname = 'spgist'
  AND opc.opcdefault
ORDER BY opc.opcintype::regtype::text, opc.opcname;

Output yang Dihasilkan:

text 
 metode_index 
--------------
 brin
 btree
 gin
 gist
 hash
 spgist
(6 rows)

 kelas_operator | tipe_data 
----------------+-----------
 range_ops      | anyrange
 box_ops        | box
 inet_ops       | inet
 quad_point_ops | point
 poly_ops       | polygon
 text_ops       | text
(6 rows)

Query pertama memastikan enam access method tersedia di server ini; query kedua menampilkan kelas operator bawaan SP-GiST: inet_ops untuk alamat jaringan, text_ops untuk teks berprefix, quad_point_ops untuk titik geometri berpartisi quadtree, plus box_ops, poly_ops, dan range_ops untuk bentuk-bentuk lain. Daftar ini bisa berbeda bila ekstensi tambahan dipasang — misalnya PostGIS menyumbang kelas operator geografisnya sendiri.

SP-GiST vs GiST #

AspekGiSTSP-GiST
Cara memecah nodepembungkus yang boleh tumpang tindihpartisi ruang yang saling lepas
Jalur pencarianbeberapa cabang sekaligus bila pembungkus beririsantepat satu cabang per level
Struktur khasR-tree, pembungkus kotak geometriquadtree, k-d tree, radix tree
Operator khas@>, <->, &&<<, prefix, ^@
Cocok untukgeometri, range, kNN, exclusion constraintrouting IP, prefix teks, partisi titik

Keduanya bukan pesaing langsung melainkan spesialisasi berbeda. Bila data Anda secara alami membentuk prefix — bit alamat IP, digit nomor telepon, karakter awal kata — partisi SP-GiST menjamin setiap pencarian menuruni satu jalur. Bila data Anda berupa bentuk yang saling menutup dan pembungkus terbaiknya tetap tumpang tindih — poligon wilayah, kotak rentang tanggal — GiST lebih tepat meski harus menelusuri cabang beririsan.

Dengan SP-GiST, koleksi jenis index PostgreSQL lengkap: struktur seimbang, hash, inverted index GIN, pembungkus GiST, ringkasan blok BRIN, hingga partisi ruang. Satu bahan data modern masih menunggu perlakuannya sendiri — dokumen JSONB di kolom produk yang strukturnya berubah-ubah — dan itulah pembahasan chapter berikutnya.

Berkas Sumber

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

buat-tabel.sql

Unduh berkas
sql 
-- Log akses situs web Toko Maju Jaya: 50.000 permintaan
-- yang datang dari empat jaringan berbeda.
CREATE TABLE log_akses (
    id      integer PRIMARY KEY,
    alamat  inet NOT NULL,
    negara  text NOT NULL
);

INSERT INTO log_akses (id, alamat, negara)
SELECT g,
       (CASE (g % 4)
          WHEN 0 THEN '192.168.' || (g % 3 + 1) || '.'
          WHEN 1 THEN '10.0.' || (g % 3) || '.'
          WHEN 2 THEN '103.10.128.'
          ELSE '203.0.113.'
        END || (g % 250)::text)::inet,
       CASE WHEN g % 4 = 3 THEN 'singapura' ELSE 'indonesia' END
FROM generate_series(1, 50000) AS g;

ANALYZE log_akses;

SELECT id, alamat, negara
FROM log_akses
ORDER BY id
LIMIT 3;

explain-analyze.sql

Unduh berkas
sql 
-- Rencana eksekusi nyata: routing subnet pada kolom inet.
EXPLAIN ANALYZE SELECT count(*) FROM log_akses
WHERE alamat << '103.10.128.0/24';

-- Rencana eksekusi nyata: pencarian prefix pada kolom text.
EXPLAIN ANALYZE SELECT count(*) FROM pelanggan_telepon
WHERE nomor LIKE '0812-%';

index-spgist.sql

Unduh berkas
sql 
-- Index SP-GiST pada kolom inet: setiap node mempartisi
-- ruang alamat berdasarkan prefix bit, seperti tabel routing.
CREATE INDEX idx_spgist_alamat ON log_akses USING spgist (alamat);

-- << berarti "alamat ini berada DI DALAM subnet ini"
SELECT count(*) AS dari_subnet_kantor
FROM log_akses
WHERE alamat << '103.10.128.0/24';

-- Jaringan internal 10.0.0.0/8 juga satu cabang routing
SELECT count(*) AS dari_jaringan_internal
FROM log_akses
WHERE alamat << '10.0.0.0/8';

SELECT id, alamat, negara
FROM log_akses
WHERE alamat << '103.10.128.0/24'
ORDER BY id
LIMIT 3;

katalog-opclass.sql

Unduh berkas
sql 
-- Semua access method index yang tersedia di server ini.
SELECT amname AS metode_index
FROM pg_am
WHERE amname IN ('btree', 'hash', 'gist', 'spgist', 'gin', 'brin')
ORDER BY amname;

-- Kelas operator bawaan SP-GiST per tipe data.
SELECT opc.opcname AS kelas_operator,
       opc.opcintype::regtype AS tipe_data
FROM pg_opclass opc
JOIN pg_am am ON am.oid = opc.opcmethod
WHERE am.amname = 'spgist'
  AND opc.opcdefault
ORDER BY opc.opcintype::regtype::text, opc.opcname;

prefix-teks.sql

Unduh berkas
sql 
-- Daftar pelanggan beserta nomor teleponnya:
-- pencarian prefix "semua nomor 0812" adalah kasus radix tree.
CREATE TABLE pelanggan_telepon (
    id     integer PRIMARY KEY,
    nama   text NOT NULL,
    nomor  text NOT NULL
);

INSERT INTO pelanggan_telepon (id, nama, nomor)
SELECT g,
       'Pelanggan ' || lpad(g::text, 5, '0'),
       '081' || ((g % 4) + 1)::text || '-' || lpad(((g * 13) % 100000)::text, 5, '0')
FROM generate_series(1, 50000) AS g;

CREATE INDEX idx_spgist_nomor ON pelanggan_telepon USING spgist (nomor);
ANALYZE pelanggan_telepon;

SELECT count(*) AS pelanggan_prefix_0812
FROM pelanggan_telepon
WHERE nomor LIKE '0812-%';

SELECT nama, nomor
FROM pelanggan_telepon
WHERE nomor LIKE '0812-%'
ORDER BY nomor
LIMIT 3;