Optimasi Query Parser SQL: Implementasi LR(1) Ringkas via APLR

Query engine database internal sering mengalami bottleneck latensi pada fase parsing string query besar sebelum masuk ke optimasi query planner. Implementasi parser berbasis full LR(1) murni menghasilkan ribuan state table redundan, sementara LALR(1) rentan terhadap konflik shift/reduce pada grammar SQL kompleks yang kaya percabangan ekspresi.

Artikel ini membahas teknik APLR(1) (Approximate / Adaptive Practical LR(1)) untuk memadatkan state table tanpa memperkenalkan duplikasi atau konflik sintaksis, disertai implementasi lexer dan parser nol alokasi dinamis (zero-heap allocation) untuk subset query SQL.

Tantangan State Table: LALR(1), IELR(1), dan APLR(1)

Penyusunan grammar SQL lengkap (meliputi klausa window function, nested subquery, dan join bertingkat) menghasilkan ribuan LR item set. Karakteristik kompresi tabel antar algoritma parsing:

• LALR(1): Menggabungkan state dengan LR(0) core yang identik. Pendekatan ini meminimalkan footprint memori secara drastis, namun kerap menimbulkan konflik lookahead palsu (reduce/reduce) pada konstruksi SQL ambigu tanpa deklarasi precedence khusus.
• IELR(1) (Minimal LR(1)): Memisahkan state hanya jika terjadi konflik parsing yang nyata. IELR(1) mempertahankan presisi penuh LR(1) dengan ukuran tabel jauh lebih kecil dari canonical LR(1), namun proses kalkulasi tabel transisi saat kompilasi membutuhkan overhead komputasi yang tinggi.
• APLR(1): Menggunakan kompresi state selektif berbasis reachability path dan transisi lookahead deterministik. State lookahead yang tidak bertabrakan langsung digabungkan melalui bit-vector mask, mengeliminasi duplikasi state hingga setara dengan ukuran tabel LALR(1) tanpa memicu konflik parsing pada token berulang.

Perbandingan Footprint State Table Dialek SQL Kompleks

Dalam representasi grammar SQL ~250 rule gramatikal, estimasi perbandingan footprint state transisi:

• Canonical LR(1): ~12.000 hingga 18.000 state, ukuran file binary state table: ~2.5 MB.
• IELR(1): ~2.800 hingga 3.500 state, ukuran file binary state table: ~350 KB.
• APLR(1): ~1.900 hingga 2.400 state, ukuran file binary state table: ~210 KB (kompresi baris berdensitas tinggi via bitmask).

Arsitektur Zero-Allocation Lexer & Parser

Parsing query throughput tinggi mengharuskan perulangan token bebas dari heap allocation (malloc/free atau new per token). Parser membaca referensi substring langsung dari query string awal melalui pointer dan offset (string span atau slice).

1. Struct Definisi Token dan State

typedef enum {
    TOK_EOF = 0,
    TOK_SELECT,
    TOK_FROM,
    TOK_WHERE,
    TOK_JOIN,
    TOK_ON,
    TOK_IDENT,
    TOK_EQ,
    TOK_COMMA
} TokenType;

typedef struct {
    TokenType type;
    const char *ptr;
    size_t len;
} Token;

typedef struct {
    const char *src;
    size_t pos;
    size_t len;
} Lexer;

2. Implementasi In-Place Lexer

static inline int is_ident_char(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') || 
           (c >= '0' && c <= '9') || c == '_';
}

Token lexer_next(Lexer *l) {
    while (l->pos < l->len && (l->src[l->pos] == ' ' || l->src[l->pos] == '\t' || 
           l->src[l->pos] == '\n' || l->src[l->pos] == '\r')) {
        l->pos++;
    }

    if (l->pos >= l->len) {
        return (Token){TOK_EOF, NULL, 0};
    }

    char c = l->src[l->pos];
    if (c == ',') { l->pos++; return (Token){TOK_COMMA, &l->src[l->pos - 1], 1}; }
    if (c == '=') { l->pos++; return (Token){TOK_EQ, &l->src[l->pos - 1], 1}; }

    if (is_ident_char(c)) {
        size_t start = l->pos;
        while (l->pos < l->len && is_ident_char(l->src[l->pos])) {
            l->pos++;
        }
        size_t tok_len = l->pos - start;
        const char *word = &l->src[start];

        // Zero-copy keyword matching
        if (tok_len == 6 && strncasecmp(word, "SELECT", 6) == 0) return (Token){TOK_SELECT, word, 6};
        if (tok_len == 4 && strncasecmp(word, "FROM", 4) == 0)   return (Token){TOK_FROM, word, 4};
        if (tok_len == 5 && strncasecmp(word, "WHERE", 5) == 0)  return (Token){TOK_WHERE, word, 5};
        if (tok_len == 4 && strncasecmp(word, "JOIN", 4) == 0)   return (Token){TOK_JOIN, word, 4};
        if (tok_len == 2 && strncasecmp(word, "ON", 2) == 0)     return (Token){TOK_ON, word, 2};

        return (Token){TOK_IDENT, word, tok_len};
    }

    l->pos++;
    return (Token){TOK_EOF, NULL, 0};
}

Implementasi State Machine APLR(1)

Parsing table dikompresi ke array statis menggunakan aksi shift (> 0), reduce (< 0), accept (0), dan error (INT16_MIN). Stack parser dialokasikan pada stack memori CPU lokal, bukan heap.

#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define ACT_ERR INT16_MIN
#define ACT_ACC 0

// Transisi shift/reduce subset: SELECT id FROM tbl JOIN tbl ON id = id WHERE id = id
// Baris: State ID, Kolom: TokenType
static const int16_t ACTION_TABLE[9][9] = {
    // EOF,   SELECT, FROM,   WHERE,  JOIN,   ON,     IDENT,  EQ,     COMMA
    { ACT_ERR, 1,     ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR }, // S0: Start -> expect SELECT
    { ACT_ERR, ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,2,      ACT_ERR,ACT_ERR }, // S1: expect col
    { ACT_ERR, ACT_ERR,3,      ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR }, // S2: expect FROM
    { ACT_ERR, ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,4,      ACT_ERR,ACT_ERR }, // S3: expect tbl
    { ACT_ACC, ACT_ERR,ACT_ERR,6,      5,      ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR }, // S4: expect JOIN / WHERE / EOF
    { ACT_ERR, ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,7,      ACT_ERR,ACT_ERR }, // S5: expect join_tbl
    { ACT_ERR, ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,8,      ACT_ERR,ACT_ERR }, // S6: expect where_ident
    { ACT_ERR, ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,4,      ACT_ERR,ACT_ERR,ACT_ERR }, // S7: expect ON
    { ACT_ACC, ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR,ACT_ERR }  // S8: parsed WHERE clause
};

int parse_sql(const char *query) {
    Lexer lexer = { .src = query, .pos = 0, .len = strlen(query) };
    int16_t state_stack[128];
    size_t sp = 0;
    
    state_stack[sp] = 0; // Inisialisasi state awal
    Token tok = lexer_next(&lexer);

    while (1) {
        int16_t state = state_stack[sp];
        int16_t act = ACTION_TABLE[state][tok.type];

        if (act == ACT_ACC) {
            return 0; // Sukses parsing
        }
        if (act > 0) { // SHIFT
            if (sp >= 127) return -1; // Stack overflow
            state_stack[++sp] = act;
            tok = lexer_next(&lexer);
        } else if (act < 0 && act != ACT_ERR) { // REDUCE
            // ponytail: flat-table reduce logic; expand with non-terminal goto matrix for subqueries.
            sp -= (size_t)(-act); 
        } else {
            return -1; // Parsing error sintaksis
        }
    }
}

Benchmarking: Alokasi Memori dan Latensi

Pengujian latensi dilakukan parsing 500 token string query secara berulang (1.000.000 iterasi) sebelum data diteruskan ke Query Planner.

Optimasi Transisi Cache

Eliminasi pointer dereference pada buffer token memungkinkan seluruh struktur parser tetap berada pada cache L1 CPU selama penelusuran. Karena ACTION_TABLE APLR(1) memadatkan kolom token menggunakan pemetaan numerik berturut-turut, branch predictor hardware dapat mengeksekusi loop transisi state tanpa pipeline stalls.

Trade-offs dan Batasan APLR(1)

• Grammar Maintenance: Peta transisi APLR(1) membutuhkan kompilator grammar terdedikasi jika dialect terus berkembang secara dinamis. Modifikasi grammar manual tanpa generator table otomatis meningkatkan risiko collision.
• Error Recovery Terbatas: Kompresi state agresif mengaburkan konteks error pinpointing. Pesan error umumnya hanya dapat mengembalikan perkiraan token terakhir yang gagal di-shift/reduce.