Contents
Disjunctive Search across Normalized Hierarchy, Low Selectivity (Score Sort)
- Join: users → stackoverflow_posts → comments
- Description: Disjunctive (OR) full-text search across normalized relational tables with relevance score ranking. This pattern represents the normalized relational equivalent of searching across a single flattened/denormalized document (e.g., Elasticsearch index). In ParadeDB, users can execute broad full-text searches across normalized table boundaries without paying the storage, memory, or ingestion cost of denormalizing parent/child entities.
- Note: We benchmark the “score sort” variant separately from the “local sort” variant to track the impact of scoring and top-K sorting on disjunctive join scans.
Query Info (statistics from 20m dataset):
- ‘code’ selectivity:
- comments.text ||| ‘code’: ~2.88M matches (~9.94%, ~2.83M joined rows)
- stackoverflow_posts.title ||| ‘code’: ~147K matches (~0.74%, fanning out to ~293K joined rows)
- users.about_me ||| ‘code’: ~29K matches (~1.27%, fanning out to ~1.85M joined rows)
- Combined disjunctive (
OR) joined selectivity: ~16.58% (~4.72M / 28.45M joined rows). Under database convention, this wide filter represents low selectivity (unselective filter with a large candidate pool).
Native PostgreSQL Variants
A naive PostgreSQL query with a cross-table OR filter (u.about_me @@ q OR p.title @@ q OR c.text @@ q) cannot use per-table GIN indexes: PostgreSQL executes a full 3-table Parallel Seq Scan + Parallel Hash Join across all 28.45M joined rows (~120s) and suffers from NULL score propagation when users.about_me (81.5% NULL) or stackoverflow_posts.title (61.5% NULL) is NULL. We instead benchmark two GIN + B-Tree rewrites (both set enable_indexonlyscan = off so ParadeDB’s bm25 index-only scan cost estimate does not hijack unpredicated B-Tree join branches):
postgres_union_agg.sql— Canonical 3-branchUNION ALL+GROUP BY(~73.0 s, 100% exact recall):- Rewrites the cross-table
ORinto a 3-branchUNION ALLwhere each branch drives from one table’s GIN index and joins the other two tables via B-Tree foreign-key/primary-key indexes. - Each branch computes
ts_rank()only on its GIN-filtered driving table inside an optimization-fenced subquery (WITH _ AS (SELECT 1)). This fence preventspull_up_subqueriesfrom flattening the branch, enablingParallel Appendand avoiding redundantto_tsvector()evaluations across the1:Njoin fanout. - Because
(users.id, stackoverflow_posts.id, comments.id)is a unique 3-tuple per branch,GROUP BY u_id, p_id, c_idwithSUM(part_score)deduplicates and sums the partial scores of multi-table matches while avoidingNULLscore propagation. - Tradeoff: Guarantees 100% exact recall across all match combinations, but at low selectivity must execute 2.79M B-Tree probes into
stackoverflow_posts_pkey(for the 2.97M matching comments), expand 36K matching users into 1.85M joined rows, and materialize + hash-aggregate ~4.72M joined triples before sorting.
- Rewrites the cross-table
postgres_early_topk.sql— Hierarchy-aware early-terminating 3-branch Top-K (~20.2 s, 20/20 recall on this dataset):- Exploits
ts_rank() >= 0and the1:Nschema hierarchy (users → stackoverflow_posts → comments) so each branch sorts its GIN-filtered driving stream first (LIMIT 100lookahead window per parallel worker) before expanding child B-Tree joins viaLATERAL+Incremental Sort ... LIMIT 20:- Branch 1 (covers
(1,0,0)user-only matches): Sorts matching users byu_score DESC LIMIT 100(top-N heapsort in parallel workers) and expandsposts → commentsviaLATERAL+Incremental Sort LIMIT 20. At low selectivity, halts after inspecting the top 2 users instead of fanning out across 36K users (1.85M joined rows). - Branch 2 (covers
(0,1,0)and(1,1,0)post + optional user matches):Parallel Hash Left Joins GIN-matching posts with GIN-matching users, sorts byup_score DESC LIMIT 100, and expandsusers + commentsviaLATERAL+Incremental Sort LIMIT 20. At low selectivity, halts after inspecting ~28 posts. - Branch 3 (covers comment matches
(0,0,1),(0,1,1),(1,1,1)):Parallel Hash Left Joins GIN-matching comments with the GIN-filtered(posts LEFT JOIN users)hash table onc.post_id = p_m.id, sorts byupc_score DESC, c.id DESC LIMIT 100inside each parallel worker, and only probesstackoverflow_posts_pkey/users_pkeyviaLATERALfor the final 20 rows (avoiding 2.97M random B-Tree lookups). At low selectivity, the remaining ~20s runtime is dominated by scanning and evaluatingto_tsvector()+ts_rank()across the 2.97M matchingcommentsheap rows (768K heap pages = 6.0 GB).
- Branch 1 (covers
- Why inner
LIMIT 100is required: Without an innerLIMITinside each branch’s parallel subquery, parallel workers underGather Mergesort all matching rows and fill their 64 KBshm_mqtuple queues when the outerIncremental Sort + Limit 20stops early, blocking worker exit and starving subsequentAppendbranches of parallel workers (max_parallel_workers = 8). - Tradeoff: Avoids
1:Njoin fanout and millions of random B-Tree probes, but relies on two assumptions that could affect recall on adversarial data: (1) the top 100 parent rows in Branches 1 and 2 join to at least 20 child rows, and (2) because Branch 3’s hash table only includes posts matching the query,(1,0,1)triples (whereusersandcommentsmatch, but the intermediate bridgestackoverflow_posts.titledoes not) are scored asmax(u_score, c_score)rather thanu_score + c_score. On this dataset, all 20 top results are 3-way(1,1,1)matches whose 3-table scores strictly dominate 2-table matches, yielding 20/20 exact recall across all three selectivity tiers.
- Exploits