Incorrect Query Results Due to Push-Down Optimization Bug in Complex Joins

Issue Overview: Complex Join Structures Yield Inconsistent Rows When Window Functions or Constants Are Used

The core problem arises when executing SQL queries involving multiple joined tables with specific optimizations applied. A combination of RIGHT OUTER JOIN, CROSS JOIN, and subqueries with ORDER BY clauses interacts unexpectedly with SQLite’s internal optimizations, particularly the "push-down" optimization. This interaction causes queries that should logically return identical results (e.g., when replacing a window function with a constant) to produce different row counts (0 rows vs. 1 row in the original test cases).

Key Components of the Failure Scenario:

1. Table Structure:

   • t1, t2, t3 are base tables with a single integer column pkey.
   • t4 and view v5 are introduced in later test cases to demonstrate the issue’s generality.
   • Views with DISTINCT (like v5) prevent query flattening, forcing the push-down optimization to act on them.

2. Join Logic:

   • INNER JOIN with ON (false) between t2 and t3 creates an empty intermediate result.
   • RIGHT OUTER JOIN with ON (true) preserves all rows from t1 (right side) regardless of the left side’s emptiness.
   • CROSS JOIN with a subquery containing ORDER BY introduces a dependency on sorting, even when all columns are NULL.

3. Expression Ambiguity:

   • The CASE WHEN (true) THEN 1 ELSE RANK() OVER (...) expression should always evaluate to 1, making its replacement with a constant 1 logically equivalent. However, the mere presence of the window function RANK() alters how the query optimizer processes joins.

4. Push-Down Optimization Failure:
   SQLite attempts to push ON clause constraints (like false) from outer joins into subqueries or views that cannot be flattened. This erroneously restricts data flow in parts of the query where constraints should not apply, causing missing rows.

Symptom Manifestation:

• Test Case 1: Returns 0 rows because the push-down optimization incorrectly propagates the ON (false) constraint from the t2-t3 join into later parts of the query, effectively nullifying the CROSS JOIN with subq_0.
• Test Case 2: Returns 1 row because the simplified expression (1) avoids triggering the push-down optimization, allowing the CROSS JOIN to operate as intended.

Possible Causes: Optimization Misapplication in Join Reordering and Constraint Propagation

1. Incorrect Push-Down of Join Constraints

The push-down optimization is designed to move WHERE clauses and ON constraints into subqueries or views to limit the number of rows processed early. However, when applied to RIGHT OUTER JOIN or CROSS JOIN structures, it may violate join semantics by:

• Pushing a constraint meant for the left side of a RIGHT JOIN into the right side’s processing pipeline.
• Applying constraints to subqueries that should remain unaffected due to their position in the join order.

2. Window Functions Altering Optimization Eligibility

Even though the RANK() window function in the CASE expression is never executed (due to true making the ELSE clause unreachable), its presence changes the query’s optimization eligibility. Window functions often disable certain optimizations (e.g., query flattening) because they require ordered processing. This creates a discrepancy between queries that look logically identical but have different optimization paths.

3. Join Reordering with Empty Intermediate Results

The INNER JOIN on (false) between t2 and t3 produces an empty result. SQLite’s optimizer might:

• Short-circuit the evaluation of subsequent joins, assuming no rows will flow through.
• Miscompute the cardinality of the RIGHT OUTER JOIN, incorrectly propagating emptiness to other parts of the query plan.

4. View Flattening Restrictions

Views containing DISTINCT (like v5) or GROUP BY cannot be flattened into the outer query. This forces the optimizer to handle them as black boxes, increasing the likelihood of push-down errors. Constraints meant for upstream joins leak into the view’s execution, artificially restricting its output.

Troubleshooting Steps, Solutions & Fixes: Diagnosing and Resolving Push-Down Errors in Join-Heavy Queries

Step 1: Verify SQLite Version and Patch Status

• Check SQLite Version:
  Run SELECT sqlite_version(); to confirm the version is 3.42.0 or newer. Versions prior to the 2023-05-10 patch contain the push-down optimization bug.
• Apply the Fix:
  Update to a version that includes check-in da3fba18742b6e0b, which corrects the constraint propagation logic in push-down scenarios.

Step 2: Simplify the Query to Isolate the Optimization Trigger

• Remove Window Functions:
  Replace non-essential window functions with constants or simple expressions to see if result consistency improves. This identifies whether the optimization discrepancy is tied to window function presence.
• Disable Specific Optimizations:
  Use pragmas like PRAGMA optimize=0x00000; to selectively disable push-down (0x00010000) or join reordering (0x00000002). Compare results with optimizations on/off.

Step 3: Analyze the Query Plan for Constraint Misplacement

• Generate the Query Plan:
  Prepend EXPLAIN QUERY PLAN to the problematic query to visualize how joins are reordered and constraints are applied.
• Look For:
  • Constraints (ON false) appearing in unexpected parts of the plan, especially within subqueries or views.
  • RIGHT JOIN converted to LEFT JOIN due to reordering, altering constraint applicability.

Step 4: Rewrite the Query to Bypass the Push-Down Optimization

• Materialize Subqueries Early:
  Use WITH clauses or temporary tables to force subquery execution before joins, preventing constraint push-down:

  WITH subq_0 AS (
    SELECT ref_5.pkey AS c0, NULL AS c1, NULL AS c2, NULL AS c3, NULL AS c4, NULL AS c5
    FROM t1 AS ref_5
    ORDER BY c0 ASC
  )
  SELECT ... FROM subq_0 ...;
  

• Use LEFT JOIN Instead of RIGHT JOIN:
  Rewrite the query to avoid RIGHT OUTER JOIN, which is less commonly optimized and more prone to push-down errors:

  SELECT ... FROM t1 LEFT JOIN (t2 JOIN t3 ON false) ON true ...
  

Step 5: Force Consistent Empty Set Handling with COALESCE

• Wrap Join Results in COALESCE:
  Explicitly handle potential nulls from empty joins to prevent optimization-induced omissions:

  SELECT COALESCE(ref_0.pkey, 0) AS pkey ... 
  

Step 6: Report and Test Against Edge Cases

• Minimize the Test Case:
  Create a self-contained script that reproduces the issue with minimal tables/joins, as seen in Richard Hipp’s simplified example. This aids in debugging and communication.
• Validate Fixes with Edge Cases:
  After applying patches or workarounds, test queries with:
  • All permutations of empty/non-empty tables.
  • Mixed INNER JOIN, LEFT JOIN, and CROSS JOIN structures.
  • Subqueries containing ORDER BY without LIMIT, which can trigger sorting optimizations.

Final Solution: Update SQLite and Restructure Queries for Optimization Safety

• Apply the Official Patch:
  The root cause is fixed in SQLite’s source code; updating is the most reliable solution.
• Adopt Optimization-Resilient Patterns:
  • Avoid mixing RIGHT JOIN with complex subqueries or views.
  • Use WITH clauses to materialize intermediate results.
  • Prefer explicit LEFT JOIN over RIGHT JOIN for better optimizer behavior.