Issue Overview: Cross Join Explosion in Multi-Table Query

The core problem revolves around a SQL query exhibiting severe performance degradation due to an unintended Cartesian product caused by improper table joining logic. The query in question uses explicit CROSS JOIN operations across three tables (tag, event, and blob) while filtering results through a complex WHERE clause and subqueries. This combination creates an intermediate result set with billions of rows that must be processed before applying filters or aggregations.

The query’s structure forces SQLite to compute the full cross product of all rows from tag, event, and qualifying blob entries before applying the LEFT JOIN constraints and WHERE conditions. With table sizes of 2,272 rows in tag, 22,623 in event, and 66 qualifying blob rows (based on the WHERE blob.rid IN (...) subquery), the intermediate result set becomes 2,272 × 22,623 × 66 = ~3.4 billion rows. Each of these rows undergoes evaluation against the LEFT JOIN conditions and subsequent filtering, overwhelming the query engine and causing indefinite execution times with 100% CPU utilization.

The inclusion of DISTINCT, ORDER BY, and LIMIT clauses further complicates execution. While LIMIT 5 suggests the query should terminate quickly, SQLite must first generate and sort the entire result set before applying the limit. The absence of indexing strategies tailored to the subqueries and join conditions exacerbates the problem, as the optimizer cannot shortcut the evaluation process.

Possible Causes: Cartesian Product and Subquery Evaluation

1. Unconstrained Cross Joins

The explicit CROSS JOIN syntax between tag, event, and blob bypasses relational filtering at the join stage. Unlike INNER JOIN or LEFT JOIN with ON clauses, CROSS JOIN unconditionally combines every row from the left table with every row from the right table. This design choice converts what might have been intended as a filtered join into a full Cartesian product. Even with a restrictive WHERE clause, the cross join forces SQLite to materialize all combinations before discarding non-matching rows.

2. Suboptimal Subquery Placement

The WHERE blob.rid IN (...) clause contains a union of four subqueries, each scanning large tables like tagxref, tag, and event. These subqueries execute repeatedly during the join process unless optimized by the query planner. The lack of covering indexes on columns like tagxref.origid, tagxref.rid, or event.comment forces full table scans, multiplying execution time.

3. Left Join Overhead

The LEFT JOIN tagxref applies to the already-massive cross join result set. The LEFT JOIN conditions (tagxref.tagid=tag.tagid, tagxref.rid=blob.rid, etc.) must be evaluated for all 3.4 billion rows, requiring repeated lookups into the tagxref table. Without indexes on tagxref.tagid or tagxref.rid, these lookups degenerate into linear searches, compounding the computational load.

4. Late Filtering via WHERE Clause

The final WHERE (tagxref.value IS NULL OR tagxref.value='markdown-footnotes') operates on the post-join dataset, failing to reduce the intermediate row count. Filters applied in WHERE instead of ON clauses prevent the optimizer from pushing down predicates, leaving the cross join result set intact until the final processing stage.

Troubleshooting Steps, Solutions & Fixes

Step 1: Analyze Query Structure and Table Sizes

Begin by quantifying the scale of the Cartesian product. Use standalone COUNT() queries to determine the size of each table involved in the cross join:

SELECT COUNT(*) FROM tag;       -- 2,272  
SELECT COUNT(*) FROM event;     -- 22,623  
SELECT COUNT(*) FROM blob WHERE rid IN (...);  -- 66  

Multiply these values to estimate the intermediate row count (2,272 × 22,623 × 66 ≈ 3.4B rows). This number confirms the query is computationally infeasible as written.

Step 2: Rewrite Cross Joins as Filtered Joins

Replace CROSS JOIN with explicit INNER JOIN or LEFT JOIN clauses that include relationship conditions in ON clauses. For example:

FROM tag  
INNER JOIN event ON tag.<related_column> = event.<related_column>  
INNER JOIN blob ON event.objid = blob.rid  

This ensures rows are filtered during the join process rather than after. If relationships between tag, event, and blob are non-trivial, introduce junction tables or WHERE conditions that reflect actual data dependencies.

Step 3: Precompute Subquery Results

Extract the WHERE blob.rid IN (...) subquery into a Common Table Expression (CTE) or temporary table to compute qualifying blob.rid values once:

WITH eligible_rids AS (  
  SELECT rid FROM tagxref NATURAL JOIN tag  
  WHERE tagtype>0 AND tagname='sym-markdown-footnotes'  
  UNION  
  SELECT srcid FROM tagxref WHERE origid IN (  
    SELECT rid FROM tagxref NATURAL JOIN tag  
    WHERE tagname='sym-markdown-footnotes'  
  )  
  UNION  
  SELECT objid FROM event WHERE comment LIKE '_branch/markdown-footnotes'  
  UNION  
  SELECT e.objid FROM event e  
  INNER JOIN blob b ON b.uuid=substr(e.comment, 10) AND e.comment LIKE '_checkin/%'  
  LEFT JOIN tagxref tx ON tx.rid=b.rid AND tx.tagid=8  
  WHERE tx.value='markdown-footnotes'  
)  
SELECT DISTINCT ...  
FROM eligible_rids  
INNER JOIN blob ON blob.rid = eligible_rids.rid  
INNER JOIN event ON event.objid = blob.rid  
LEFT JOIN tagxref ON tagxref.rid = blob.rid AND tagxref.tagtype > 0  
INNER JOIN tag ON tag.tagid = tagxref.tagid  

This restructuring eliminates the cross join by anchoring the query to a pre-filtered set of blob.rid values.

Step 4: Index Critical Columns

Create indexes to accelerate subqueries and join conditions:

CREATE INDEX idx_tagxref_rid ON tagxref(rid);  
CREATE INDEX idx_tagxref_origid ON tagxref(origid);  
CREATE INDEX idx_event_comment ON event(comment);  
CREATE INDEX idx_event_objid ON event(objid);  
CREATE INDEX idx_blob_rid ON blob(rid);  

These indexes allow rapid lookups on columns frequently used in WHERE, JOIN, and IN clauses.

Step 5: Leverage EXPLAIN QUERY PLAN

Use SQLite’s EXPLAIN QUERY PLAN to identify full table scans and inefficient join orders:

EXPLAIN QUERY PLAN  
SELECT DISTINCT ... (original query)  

Look for lines like SCAN TABLE tag or SCAN TABLE event USING COVERING INDEX in the output. If the plan shows SCAN without USING INDEX, revisit indexing strategies.

Step 6: Simplify the Query Logic

Break the monolithic query into smaller components tested incrementally. For example:

1. Validate the eligible_rids CTE returns the expected 66 rows.
2. Test joins between eligible_rids and blob/event separately.
3. Gradually integrate tag and tagxref with proper join conditions.

Step 7: Avoid DISTINCT with Proper Joins

The DISTINCT keyword often indicates redundant rows caused by overly broad joins. If the restructured query uses precise INNER JOIN conditions, DISTINCT may become unnecessary, reducing post-processing overhead.

Step 8: Test with Reduced Limits

Add LIMIT 1 to the original query to gauge baseline performance. If even a single row takes minutes to retrieve, the Cartesian product remains the bottleneck.

Step 9: Utilize Materialized Views

For recurring queries, precompute and refresh results periodically using a materialized view (via triggers or application logic). This shifts computational load to write operations, sparing read-time evaluation.

Step 10: Monitor Query Progress with Application Logs

Instrument the application to log query execution times and intermediate result counts. This helps correlate SQL structure changes with performance improvements.

By systematically addressing Cartesian products, optimizing join conditions, and leveraging indexing, the query’s execution time can be reduced from hours/days to milliseconds. The key lesson is to avoid unconstrained cross joins in favor of filtered relationships early in the query pipeline.