sqljs_bench.js

const initSqlJs = require('sql.js');
const fs = require('fs');
const path = require('path');
const { performance } = require('perf_hooks');

const TC_DATASETS = [
    'data_7035', 'data_21693', 'data_23874', 'data_26013',
    'data_39994', 'data_48232', 'data_49152',
    'data_88234', 'data_119666', 'data_121544', 'data_196575', 'data_223001',
];

const SG_DATASETS = [
    'data_7035', 'data_21693', 'data_23874', 'data_409593',
];

let WARMUP_RUNS = 0;
let TIMED_RUNS  = 1;

function loadEdges(name) {
    const buf = fs.readFileSync(path.join(__dirname, 'public', 'data', `${name}.bin`));
    return new Uint32Array(buf.buffer, buf.byteOffset, buf.byteLength / 4);
}

function populateEdgeTable(db, edges) {
    db.run("CREATE TABLE edge (src INTEGER NOT NULL, dst INTEGER NOT NULL)");
    db.run("BEGIN");
    const stmt = db.prepare("INSERT INTO edge VALUES (?, ?)");
    for (let i = 0; i < edges.length; i += 2) {
        stmt.bind([edges[i], edges[i + 1]]);
        stmt.step();
        stmt.reset();
    }
    stmt.free();
    db.run("COMMIT");
    db.run("CREATE INDEX idx_edge_src ON edge(src)");
    db.run("CREATE INDEX idx_edge_dst ON edge(dst)");
    db.run("ANALYZE");
}

// TC: tc(X,Y) :- edge(X,Y).
//     tc(X,Y) :- tc(X,Z), edge(Z,Y).
const TC_QUERY = `
    WITH RECURSIVE tc(src, dst) AS (
        SELECT src, dst FROM edge
        UNION
        SELECT tc.src, edge.dst
        FROM tc JOIN edge ON tc.dst = edge.src
    )
    SELECT COUNT(*) FROM tc
`;

// SG Variant B:
//   sg(X,Y) :- parent(X,P),  parent(Y,P),  X != Y.       (seed)
//   sg(X,Y) :- parent(X,Px), parent(Y,Py), sg(Px,Py).    (recursive, no filter)
// edge(src,dst) means src=parent, dst=child.
// parent(X, P) ≡ edge(P, X): src=P, dst=X.
const SG_QUERY = `
    WITH RECURSIVE sg(x, y) AS (
        SELECT e1.dst, e2.dst
        FROM edge e1 JOIN edge e2 ON e1.src = e2.src
        WHERE e1.dst <> e2.dst
        UNION
        SELECT e1.dst, e2.dst
        FROM sg
        JOIN edge e1 ON e1.src = sg.x
        JOIN edge e2 ON e2.src = sg.y
    )
    SELECT COUNT(*) FROM sg
`;

function bench(db, query, label, dataset) {
    console.log(`\n--- ${label}: ${dataset} ---`);

    for (let i = 0; i < WARMUP_RUNS; i++) {
        const t0 = performance.now();
        const res = db.exec(query);
        const ms = performance.now() - t0;
        const cnt = res[0]?.values[0]?.[0] ?? 0;
        console.log(`  Warmup ${i + 1}/${WARMUP_RUNS}: ${ms.toFixed(1)} ms  |closure| = ${cnt}`);
    }

    const times = [];
    let closureSize = 0;
    for (let i = 0; i < TIMED_RUNS; i++) {
        const t0 = performance.now();
        const res = db.exec(query);
        const ms = performance.now() - t0;
        closureSize = res[0]?.values[0]?.[0] ?? 0;
        times.push(ms);
        console.log(`  Run ${i + 1}/${TIMED_RUNS}: ${ms.toFixed(3)} ms  |closure| = ${closureSize}`);
    }

    const avg = times.reduce((a, b) => a + b, 0) / times.length;
    const sigma = Math.sqrt(times.reduce((a, b) => a + (b - avg) ** 2, 0) / times.length);
    console.log(`  => avg = ${avg.toFixed(3)} ms, σ = ${sigma.toFixed(3)} ms, |closure| = ${closureSize}`);
    return { dataset, closureSize, avg, sigma };
}

function printSummary(tag, results) {
    console.log(`\n========== ${tag} Summary ==========`);
    console.log('Dataset          |     |closure| |    avg (ms) |   σ (ms)');
    console.log('-'.repeat(62));
    let total = 0;
    for (const r of results) {
        console.log(
            `${r.dataset.padEnd(16)} | ${String(r.closureSize).padStart(11)} | ${r.avg.toFixed(3).padStart(11)} | ${r.sigma.toFixed(3).padStart(8)}`
        );
        total += r.avg;
    }
    console.log(`${'Σ all'.padEnd(16)} |             | ${total.toFixed(3).padStart(11)} |`);
}

(async () => {
    const mode = process.argv[2] || 'both';          // tc | sg | both
    const only = process.argv[3];                     // optional single dataset
    if (process.argv[4]) WARMUP_RUNS = parseInt(process.argv[4], 10);
    if (process.argv[5]) TIMED_RUNS  = parseInt(process.argv[5], 10);

    const SQL = await initSqlJs();

    if (mode === 'tc' || mode === 'both') {
        console.log('\n============================================================');
        console.log('  TC (Transitive Closure) — sql.js / SQLite WASM');
        console.log('============================================================');
        const list = only ? [only] : TC_DATASETS;
        const results = [];
        for (const ds of list) {
            const db = new SQL.Database();
            const edges = loadEdges(ds);
            console.log(`\nLoading ${ds}: ${edges.length / 2} edges …`);
            const t0 = performance.now();
            populateEdgeTable(db, edges);
            console.log(`  Table + indexes: ${(performance.now() - t0).toFixed(1)} ms`);
            results.push(bench(db, TC_QUERY, 'TC', ds));
            db.close();
        }
        printSummary('TC', results);
    }

    if (mode === 'sg' || mode === 'both') {
        console.log('\n============================================================');
        console.log('  SG (Same Generation, Variant B) — sql.js / SQLite WASM');
        console.log('============================================================');
        const list = only ? [only] : SG_DATASETS;
        const results = [];
        for (const ds of list) {
            const db = new SQL.Database();
            const edges = loadEdges(ds);
            console.log(`\nLoading ${ds}: ${edges.length / 2} edges …`);
            const t0 = performance.now();
            populateEdgeTable(db, edges);
            console.log(`  Table + indexes: ${(performance.now() - t0).toFixed(1)} ms`);
            results.push(bench(db, SG_QUERY, 'SG', ds));
            db.close();
        }
        printSummary('SG', results);
    }
})();