Menyimpan dan mengueri metadata Directed Acyclic Graph (DAG) Git di dalam database relasional seperti PostgreSQL sering kali menimbulkan lonjakan latensi ketika repositori bertumbuh hingga ratusan ribu atau jutaan commit. Dua hambatan utama performa dalam skenario ini adalah:

  1. Ancestry Traversal Latency: Query rekursif untuk menelusuri riwayat percabangan dan merge commit membutuhkan nested loop join intensif pada edge table.
  2. Deep Offset Scanning: Penggunaan OFFSET pada query commit log memaksa database melakukan scan dan discard ribuan baris data yang tidak relevan sebelum mengembalikan pagination batch.

Pendekatan ini membedah arsitektur skema commit graph, konfigurasi composite index B-tree pada relasi edge, pembatasan kedalaman Recursive CTE, serta implementasi tuple keyset pagination deterministik.

1. Desain Skema Database Metadata Git

Pemisahan entitas node (commit) dan edge (relasi parent-child) adalah representasi relasional standar untuk DAG Git. Satu commit dapat memiliki 0 parent (root commit), 1 parent (regular commit), atau 2+ parent (merge commit).

CREATE TABLE commits (
    id CHAR(40) PRIMARY KEY, -- SHA-1 commit hash (atau VARCHAR(64) untuk SHA-256)
    repository_id INT NOT NULL,
    commit_date TIMESTAMPTZ NOT NULL,
    author_name TEXT NOT NULL,
    message TEXT NOT NULL
);

CREATE TABLE commit_parents (
    repository_id INT NOT NULL,
    commit_id CHAR(40) NOT NULL REFERENCES commits(id) ON DELETE CASCADE,
    parent_id CHAR(40) NOT NULL REFERENCES commits(id) ON DELETE CASCADE,
    parent_order SMALLINT NOT NULL DEFAULT 0, -- 0 untuk mainline/first parent, 1+ untuk merge parents
    PRIMARY KEY (repository_id, commit_id, parent_id)
);

2. Optimasi Recursive CTE untuk Ancestry Traversal

Saat mencari riwayat commit dari HEAD tertentu (misalnya commit branch `main`), database harus melakukan traversal rekursif mundur ke commit parent. Tanpa indeks yang presisi, setiap iterasi rekursi memicu Sequential Scan atau Bitmap Heap Scan bertingkat.

Composite B-Tree Index pada Edge Table

Penelusuran anak ke orang tua (ancestry traversal) mengevaluasi klausa commit_parents.commit_id = cte.parent_id. Sebaliknya, penelusuran orang tua ke anak (descendant/merge-base search) mengevaluasi klausa commit_parents.parent_id = cte.commit_id.

Untuk memangkas table heap lookup, definisikan composite B-tree index covering berikut:

-- Indeks untuk penelusuran descendant (child traversal)
CREATE INDEX idx_commit_parents_parent_commit 
ON commit_parents (repository_id, parent_id, commit_id);

-- Indeks untuk penelusuran ancestor (history log traversal)
CREATE INDEX idx_commit_parents_commit_parent 
ON commit_parents (repository_id, commit_id, parent_id);
Catatan Teknis: Menyertakan repository_id di urutan pertama indeks memastikan isolasi multi-tenant data repositori berjalan optimal pada skala B-Tree multi-tier.

Recursive CTE dengan Bounded Depth dan Deteksi Siklus

DAG Git secara teori tidak memiliki siklus (acyclic), namun anomali data integritas atau repository graft/replace dapat menyebabkan perulangan tak terbatas pada CTE. Gunakan bounded depth (pembatasan kedalaman) dan tracking path:

WITH RECURSIVE commit_ancestry AS (
    -- Anchor member: Titik awal traversal (misal: commit HEAD)
    SELECT 
        cp.parent_id,
        cp.parent_order,
        1 AS depth,
        ARRAY[cp.commit_id] AS visited_path
    FROM commit_parents cp
    WHERE cp.repository_id = 1 
      AND cp.commit_id = 'c1a013a2d04a6081e6a17b3c20c0a37e5c92881a'

    UNION ALL

    -- Recursive member: Ambil parent dari baris sebelumnya
    SELECT 
        cp.parent_id,
        cp.parent_order,
        ca.depth + 1,
        ca.visited_path || cp.commit_id
    FROM commit_parents cp
    JOIN commit_ancestry ca 
      ON cp.repository_id = 1 
     AND cp.commit_id = ca.parent_id
    WHERE ca.depth < 50 -- Bounded depth: batasi traversal hingga 50 level
      AND NOT (cp.parent_id = ANY(ca.visited_path)) -- Siklus guard
)
SELECT DISTINCT c.id, c.commit_date, c.author_name, c.message, ca.depth
FROM commit_ancestry ca
JOIN commits c ON c.repository_id = 1 AND c.id = ca.parent_id
ORDER BY ca.depth ASC;
-- ponytail: tracking visited_path menggunakan ARRAY cukup hingga kedalaman 100. Ganti dengan PostgreSQL 14 CYCLE clause untuk volume besar.

3. Masalah OFFSET dan Solusi Deterministik Keyset Pagination

Pendekatan standar untuk log viewer biasanya mengandalkan OFFSET:

-- ANTI-PATTERN: Menghabiskan I/O untuk membuang 50.000 baris pertama
SELECT id, commit_date, message 
FROM commits 
WHERE repository_id = 1 
ORDER BY commit_date DESC 
LIMIT 20 OFFSET 50000;

Database tetap harus memproses 50.020 baris dari disk/buffer sebelum membuang 50.000 baris dan menyerahkan 20 baris ke klien. Kompleksitasnya adalah O(OFFSET + LIMIT).

Implementasi Row-Value Keyset Pagination

Dengan keyset pagination, database langsung melompat ke tuple indeks terakhir yang dilihat klien, menghasilkan kompleksitas konstan O(LIMIT). Timestamp commit_date saja tidak deterministik karena commit hasil automated script/rebase dapat memiliki timestamp identik (collision).

Gunakan compound comparison tuple (commit_date, id):

-- 1. Siapkan Composite Index penunjang keyset
CREATE INDEX idx_commits_repo_date_id 
ON commits (repository_id, commit_date DESC, id DESC);

-- 2. Query Keyset Pagination Deterministik
SELECT id, commit_date, author_name, message
FROM commits
WHERE repository_id = 1
  AND (commit_date, id) < ('2026-03-31 08:45:10+00', 'c1a013a2d04a6081e6a17b3c20c0a37e5c92881a')
ORDER BY commit_date DESC, id DESC
LIMIT 20;

Query di atas menggunakan operator baris (row constructor comparison). PostgreSQL akan melakukan Index Scan langsung ke posisi leaf node B-tree yang sesuai dan mengambil tepat 20 entri.

4. Analisis Execution Plan (EXPLAIN ANALYZE)

Berikut adalah perbandingan pembacaan eksekusi engine PostgreSQL pada dataset pengujian berisi 1.200.000 commit.

Sebelum Optimasi (OFFSET 50.000, Tanpa Composite Index)

Limit  (cost=12130.45..12135.31 rows=20 width=98) (actual time=68.412..68.435 rows=20 loops=1)
  ->  Gather Merge  (cost=1000.00..291580.12 rows=1200000 width=98) (actual time=14.218..64.872 rows=50020 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Sort  (cost=289580.00..291080.00 rows=600000 width=98) (actual time=12.110..18.441 rows=17000 loops=3)
              Sort Key: commit_date DESC
              Sort Method: external merge  Disk: 42100kB
              ->  Parallel Seq Scan on commits  (cost=0.00..35100.00 rows=600000 width=98) (actual time=0.045..5.120 rows=400000 loops=3)
Planning Time: 0.280 ms
Execution Time: 74.891 ms

Setelah Optimasi (Tuple Keyset Scan dengan Index)

Limit  (cost=0.43..2.88 rows=20 width=98) (actual time=0.038..0.061 rows=20 loops=1)
  ->  Index Scan using idx_commits_repo_date_id on commits  (cost=0.43..140230.15 rows=1142857 width=98) (actual time=0.036..0.057 rows=20 loops=1)
        Index Cond: ((repository_id = 1) AND (ROW(commit_date, id) < ROW('2026-03-31 08:45:10+00'::timestamp with time zone, 'c1a013a2...'::bpchar)))
Planning Time: 0.145 ms
Execution Time: 0.082 ms

Hasil: Waktu eksekusi turun dari 74.891 ms menjadi 0.082 ms. Penggunaan memori disk sort sepenuhnya tereliminasi karena data dibaca langsung terurut dari B-tree index.

5. Trade-off dan Pertimbangan Arsitektur

  • Index Write Amplification: Setiap commit push baru yang memiliki banyak parent akan menulis data ke beberapa indeks sekunder. Pastikan ukuran fillfactor tabel dikonfigurasi bila update in-place sering terjadi.
  • B-Tree Operator Class Support: Sintaks perbandingan tuple (a, b) < (x, y) didukung optimal pada indeks B-tree majemuk PostgreSQL, namun perhatikan arah sorting (ASC/DESC). Indeks dan query wajib memiliki kombinasi arah urutan yang sama agar database terhindar dari operasi explicit in-memory sorting.