UQA — Unified Query Algebra

Core Theory

UQA is built on four interconnected theoretical papers that establish a mathematical foundation spanning database theory, information retrieval, probabilistic inference, and neural computation.

Read the full theoretical foundations →

Architecture

graph TD
    SQL["SQL Parser — pglast"] --> Compiler[SQL Compiler]
    QB["QueryBuilder — Fluent API"] --> Operators

    Compiler --> Optimizer[Query Optimizer]
    Optimizer --> Operators[Operator Tree]
    Operators --> Executor[Plan Executor]
    Executor --> PAR["Parallel Executor — ThreadPool"]
    Operators --> Cypher["Cypher Compiler — openCypher"]

    PAR --> DS["Document Store — SQLite"]
    PAR --> II["Inverted Index — SQLite + Analyzer"]
    PAR --> VI["Vector Index — IVF"]
    PAR --> GS["Graph Store — SQLite"]

    subgraph Scoring
        BM25[BM25]
        BBFS[Bayesian BM25]
        VS[Vector Scorer]
    end

    subgraph Fusion
        LO[Log-Odds]
        PB[Probabilistic Boolean]
    end

    Operators --> Scoring
    Operators --> Fusion
  

Cross-Paradigm Operators

Each paradigm maps into the posting list space through primitive operators. Because every operator produces a posting list, they compose freely.

Operator	Definition	Paradigm
$T(t)$	$PL(\lbrace d \in \mathcal{D} \mid t \in term(d, f) \rbrace)$	Text retrieval
$V_\theta(q)$	$PL(\lbrace d \in \mathcal{D} \mid sim(vec(d, f), q) \geq \theta \rbrace)$	Vector search
$KNN_k(q)$	$PL(D_k)$ where $|D_k| = k$, ranked by similarity	Vector search
$Filter_{f,v}(L)$	$L \cap PL(\lbrace d \in \mathcal{D} \mid d.f = v \rbrace)$	Relational
$Score_q(L)$	$(L, [s_1, \ldots, s_{|L|}])$	Scoring
$\Phi(L_G)$	$PL\bigl(\bigcup_i \phi_{G \rightarrow D}(G_i)\bigr)$	Graph

A hybrid text + vector search is simply an intersection:

Fusion Functions

Multi-signal fusion combines scores from different paradigms. Log-odds conjunction resolves the conjunction shrinkage problem where naive probability multiplication underestimates relevance:

Function	Description
fuse_log_odds(s1, s2, ...)	Log-odds conjunction — calibrated multi-signal fusion
fuse_prob_and(s1, s2, ...)	$P = \prod P_i$
fuse_prob_or(s1, s2, ...)	$P = 1 - \prod(1 - P_i)$
fuse_prob_not(signal)	$P = 1 - P_{signal}$
fuse_log_odds(s1, s2, 'relu')	Log-odds with ReLU/Swish gating
pagerank() / hits() / betweenness()	Graph centrality as FROM or WHERE signal
progressive_fusion(s1, s2, k, ...)	Cascading multi-stage WAND pruning
weighted_rpq('expr', start, 'prop')	RPQ with cumulative edge weight tracking

Query Optimizer

DPccp Join Ordering (Moerkotte & Neumann, 2006)

The join order optimizer uses the DPccp algorithm — dynamic programming over connected subgraph complement pairs. It finds the optimal bushy join tree in $O(3^n)$ time, compared to $O(n!)$ for exhaustive enumeration. For queries with more than 16 relations, it falls back to a greedy $O(n^3)$ heuristic.

Cost-Based Optimization

• Histogram-aware selectivity: equi-depth histograms + Most Common Values (MCV) from ANALYZE
• Recursive filter pushdown: through nested IntersectOperators to all leaf operators
• Vector threshold merge: same query vector with floating-point tolerance (np.allclose)
• Cost-based intersection reordering: sort by execution cost, not cardinality
• Intersection early termination: skip remaining operands when accumulator is empty
• Predicate-aware cardinality damping: same-column correlation vs cross-column independence
• Join-algorithm-aware DPccp: index join cost for small inputs, hash join cost for large inputs
• Fusion signal reordering: cheapest-first signal evaluation
• R*Tree spatial index scan: for POINT column range queries
• B-tree index scan substitution: replace full scans when profitable
• FDW predicate pushdown: comparison, IN, LIKE, ILIKE, BETWEEN pushed to DuckDB/Arrow Flight SQL
• FDW full query pushdown: same-server queries delegated entirely via AST deparsing
• FDW mixed foreign-local: small local tables shipped to DuckDB for in-process JOINs
• Cross-paradigm cardinality: text, vector, graph, fusion, temporal, and GNN operators
• Edge filter pushdown: graph edge property filters into pattern constraints
• Join-pattern fusion: merge intersected pattern matches with shared variables
• Cross-paradigm join cost models: text similarity, vector similarity, graph, hybrid joins
• Threshold-aware vector selectivity: 4-tier estimation buckets
• Temporal cardinality correction: timestamp/range selectivity for temporal graphs
• Path index acceleration: for Concat-of-Labels RPQ expressions and Cypher MATCH patterns
• CTE inlining: for single-reference non-recursive CTEs
• Predicate pushdown: into views and derived tables
• Implicit cross join reordering: via DPccp when equijoin predicates exist in WHERE

SQL Interface

PostgreSQL 17 compatible SQL with cross-paradigm extensions. 95 of 103 target PostgreSQL 17 features implemented.

Multi-Signal Fusion

SELECT title, _score FROM papers
WHERE fuse_log_odds(
    text_match(title, 'attention'),
    knn_match(embedding, ARRAY[0.1, 0.2, ...], 5),
    traverse_match(1, 'cited_by', 2)
) AND year >= 2020
ORDER BY _score DESC;

Window Functions

SELECT rep, sale_date, amount,
       SUM(amount) OVER (ORDER BY sale_date
           ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS running_total
FROM sales;

Recursive CTE

WITH RECURSIVE org_tree AS (
    SELECT id, name, 1 AS depth FROM org_chart WHERE manager_id IS NULL
    UNION ALL
    SELECT o.id, o.name, t.depth + 1
    FROM org_chart o INNER JOIN org_tree t ON o.manager_id = t.id
)
SELECT name, depth FROM org_tree ORDER BY depth;

Graph Query (openCypher / Apache AGE)

— Create a named graph (persisted in SQLite)
SELECT * FROM create_graph('social');

— Populate the graph with Cypher CREATE
SELECT * FROM cypher('social', $$
    CREATE (a:Person {name: 'Alice', age: 30})
    CREATE (b:Person {name: 'Bob', age: 28})
    CREATE (a)-[:KNOWS]->(b)
$$) AS (v agtype);

— Query the named graph
SELECT * FROM cypher('social', $$
    MATCH (p:Person)-[:KNOWS]->(friend:Person)
    WHERE p.age > 25
    RETURN p.name, friend.name, p.age
    ORDER BY p.name
$$) AS (name agtype, friend agtype, age agtype);

— Drop the graph and all its data
SELECT * FROM drop_graph('social');

Named graphs provide isolated graph namespaces with full SQLite persistence. Each graph stores vertices and edges in dedicated tables (_graph_vertices_*, _graph_edges_*), surviving engine restarts. Graph centrality functions (pagerank, hits, betweenness) and path indexes operate on named graphs via the 'graph:name' syntax.

Full-Text Search (@@ Operator)

— Query string mini-language: boolean, phrase, field targeting
SELECT title, _score FROM articles
WHERE title @@ 'database AND query' ORDER BY _score DESC;

— Hybrid text + vector fusion via @@
SELECT title, _score FROM articles
WHERE _all @@ 'body:search AND embedding:[0.1, 0.9, 0.0, 0.0]'
ORDER BY _score DESC;

Geospatial Query

CREATE TABLE restaurants (
    id SERIAL PRIMARY KEY,
    name TEXT NOT NULL,
    location POINT
);

CREATE INDEX idx_loc ON restaurants USING rtree (location);

SELECT name, ROUND(ST_Distance(location, POINT(-73.9857, 40.7484)), 0) AS dist_m
FROM restaurants
WHERE spatial_within(location, POINT(-73.9857, 40.7484), 5000)
ORDER BY dist_m;

Temporal Graph Traversal

— Edges valid at timestamp
SELECT * FROM temporal_traverse(1, 'knows', 2, 1700000000);

— GNN message passing: aggregate neighbor properties
SELECT * FROM papers
WHERE message_passing(2, 'mean', 'citations');

— Structural graph embeddings
SELECT * FROM papers
WHERE graph_embedding(16, 3);

Graph Centrality

SELECT title, _score FROM pagerank()
ORDER BY _score DESC;

SELECT title, _score FROM papers
WHERE fuse_log_odds(
    text_match(title, 'attention'),
    pagerank(),
    'relu'
) ORDER BY _score DESC;

Foreign Data Wrapper

CREATE SERVER warehouse FOREIGN DATA WRAPPER duckdb_fdw;

CREATE FOREIGN TABLE sales (
    id INTEGER, name TEXT, amount INTEGER,
    year INTEGER, month INTEGER
) SERVER warehouse OPTIONS (
    source '/data/sales/**/*.parquet',
    hive_partitioning 'true'
);

— DuckDB prunes Hive partitions at source
SELECT name, SUM(amount) FROM sales
WHERE year IN (2024, 2025) AND month > 6
GROUP BY name ORDER BY SUM(amount) DESC;

Foreign Data Wrappers

UQA federates external data sources through the FDW abstraction, bridging pyarrow.Table results into the posting list pipeline.

Predicate Pushdown

Comparison (=, !=, <, >), IN, LIKE, ILIKE, and BETWEEN predicates are pushed down to the external engine, enabling Hive partition pruning and reducing data transfer.

Full Query Pushdown (v0.19.0)

When all tables in a query live on the same DuckDB server, the entire SQL — including JOINs, GROUP BY, ORDER BY, window functions, subqueries, and CTEs — is deparsed via pglast.stream.RawStream and executed natively by DuckDB. For mixed foreign-local queries, small local tables (<100K rows) are shipped to DuckDB as temp tables. Arrow Flight SQL supports same-server pure-foreign pushdown. If DuckDB cannot execute (e.g., UQA-specific functions like spatial_within), the standard UQA operator pipeline takes over automatically.

Benchmarks

295 pytest-benchmark tests across 14 subsystems track performance across commits. The CI pipeline detects regressions with a 150% threshold and blocks PRs that exceed it.

View live benchmark dashboard →