Anatomi Masalah: Nontermination pada Recursive Query

Dalam sistem backend yang memproses relational data kompleks seperti RBAC (Role-Based Access Control) bertingkat atau dependency graph, declarative query engine seperti Datalog atau recursive SQL (Common Table Expressions) sering diandalkan. Masalah muncul saat recursive rule memicu nontermination (infinite loop execution).

Gejala umum pada level infrastruktur mencakup:

  • CPU Core Spike 100%: Satu atau lebih worker thread terkunci dalam loop komputasi fixpoint atau derivasi SLD-resolution tanpa henti.
  • Memory Leak Bertahap: Intermediate state table atau recursion call stack terus membengkak hingga memicu OOM (Out Of Memory) killer.
  • Worker Pool Exhaustion: Request timeouts bertingkat pada layer API akibat pool thread backend kehabisan resource melayani worker yang macet.

Top-Down vs Bottom-Up: Mengapa Evaluation Order Menentukan Terminasi

Secara teoretis, bahasa deklaratif seperti Datalog berbasiskan least fixed-point semantics. Namun, implementasi engine menentukan apakah eksekusi query benar-benar terminasi.

1. Top-Down Evaluation (Prolog style / SLD Resolution)

Engine mengevaluasi dari goal ke fakta dasar. Jika predikat rekursif diletakkan di sebelah kiri (left-recursive) pada data dengan cyclic graph, engine melakukan unrolling subtree identik terus-menerus tanpa mendeteksi state yang pernah dikunjungi, menghasilkan infinite call tree.

2. Bottom-Up Evaluation (Datalog Semi-Naïve / Fixpoint)

Engine mengevaluasi dari fakta (extensional database) ke atas secara iteratif hingga tidak ada fakta baru yang dihasilkan (fixed-point). Pendekatan ini terminasi pada relational data standar (finite universe), tetapi rentan loop tak hingga ketika query mengombinasikan konstruksi fungsi (functors/terms), unbounded arithmetic, atau negasi yang tidak terstratifikasi (unstratified negation).

Bedah Masalah: Infinite Path pada Cyclic Graph

Bayangkan struktur edge cyclic sederhana: A -> B, B -> A. Rule transitif path didefinisikan sebagai berikut:

% Extensional Database (Fakta)
edge(a, b).
edge(b, a).

% Rule Rekursif Bermasalah (Left-Recursive / Non-Guarded)
path(X, Y) :- path(X, Z), edge(Z, Y).
path(X, Y) :- edge(X, Y).

Pada engine yang menggunakan strategi evaluasi top-down tanpa memoization/tabling, sub-goal path(X, Z) langsung memicu panggilan rekursif ke dirinya sendiri sebelum memeriksa edge dasar atau cycle history. Derivasi pohon membengkak tanpa henti.

Pada engine recursive SQL (seperti PostgreSQL WITH RECURSIVE), operasi default menggunakan semantik UNION ALL tanpa siklus de-duplikasi otomatis:

-- SQL Query rentan loop tak berujung
WITH RECURSIVE traverse(src, dst) AS (
    SELECT src, dst FROM edges
    UNION ALL
    SELECT t.src, e.dst 
    FROM traverse t
    JOIN edges e ON t.dst = e.src
)
SELECT * FROM traverse WHERE src = 'a';

UNION ALL tidak membuang row duplikat antar-iterasi. Pada siklus a -> b -> a, query menghasilkan kombinasi row tanpa henti hingga sistem crash.

Langkah Debugging Step-by-Step

1. Trace Execution Plan dan State Profiling

Isolasi query pada environment test. Periksa physical plan execution:

  • Pada SQL recursive: Gunakan EXPLAIN (ANALYZE, BUFFERS). Perhatikan lonjakan baris pada node WorkTable Scan.
  • Pada Datalog engine: Aktifkan debug trace untuk melihat derivasi atom (misal flag trace. pada Soufflé atau Prolog-based systems).

2. Profile Intermediate Relation Size

Pantau ukuran working memory delta per iterasi recursive loop. Jika delta per iterasi tidak pernah konvergen ke nol (0 tuples added) melainkan terus bertambah atau stabil di angka tertentu secara periodik, engine terperangkap dalam cyclic state derivation.

Solusi dan Refactoring Query

Opsi 1: Explicit Cycle Detection Guard (Array / Visited Set)

Cegah re-evaluasi node yang sudah dikunjungi dengan membawa riwayat traversal:

WITH RECURSIVE traverse(src, dst, visited) AS (
    SELECT 
        src, 
        dst, 
        ARRAY[src, dst]::text[] AS visited
    FROM edges
    WHERE src = 'a'
    
    UNION ALL
    
    SELECT 
        t.src, 
        e.dst, 
        t.visited || e.dst
    FROM traverse t
    JOIN edges e ON t.dst = e.src
    WHERE NOT (e.dst = ANY(t.visited)) -- Guard condition
)
SELECT DISTINCT src, dst FROM traverse;

Opsi 2: Menggunakan UNION Set Semantics (Bottom-Up Deduplication)

Jika menggunakan engine dengan memoization bawaan atau SQL engine standar, ubah UNION ALL menjadi UNION. Pendekatan ini memaksa engine melakukan hash deduplication terhadap intermediate relation:

WITH RECURSIVE traverse(src, dst) AS (
    SELECT src, dst FROM edges WHERE src = 'a'
    UNION
    SELECT t.src, e.dst 
    FROM traverse t
    JOIN edges e ON t.dst = e.src
)
SELECT * FROM traverse;
Trade-off: UNION memerlukan hashing atau sorting pada setiap langkah iterasi, meningkatkan overhead CPU per putaran. Namun, ini menjamin pencapaian fixed-point pada graph bertipe finite.

Opsi 3: Stratified Negation

Jika query melibatkan pengecekan ketiadaan relasi (misalnya node yang tidak boleh melewati edge tertentu), pastikan negasi berstatus stratified. Negasi tidak boleh bergantung secara sirkular pada derivasi dirinya sendiri:

% Datalog valid dengan stratified dependency:
% Layer 1: Hitung semua reachable node
reachable(X, Y) :- edge(X, Y).
reachable(X, Y) :- reachable(X, Z), edge(Z, Y).

% Layer 2: Negasi hanya dilakukan setelah Layer 1 selesai dievaluasi penuh
unreachable(X, Y) :- all_nodes(X), all_nodes(Y), not reachable(X, Y).

Kesimpulan

Nontermination query pada Datalog engine dan recursive SQL berakar dari ketidaksesuaian antara evaluation order (top-down vs bottom-up) dengan struktur data cyclic graph. Masalah ini diselesaikan dengan mengganti evaluation style, membatasi state traversal menggunakan visited guard, atau beralih ke semantik deduplikasi hingga konvergensi least fixed-point tercapai.