and Resolving UNION Subquery Filter Pushdown Performance Issues in SQLite

Issue Overview: Subquery UNION Filter Conditions Not Pushed Down to Constituent Queries

When working with SQLite, developers often rely on the query optimizer to transform high-level SQL statements into efficient execution plans. A common expectation is that filters applied to the results of a subquery or view will be "pushed down" into the individual components of that subquery, especially when the subquery is composed of a UNION or UNION ALL of multiple SELECT statements. This expectation arises from the desire to minimize the volume of data processed by eliminating irrelevant rows as early as possible in the query execution pipeline.

In the scenario presented, a subquery defined as a UNION ALL of two SELECT statements from different large tables (large_table and other_large_table) includes a column (foo) that is assigned a constant or literal value in each branch of the union. The outer query applies a filter condition (WHERE foo = ?) to this column. The anticipated behavior is that SQLite would recognize that the foo column in each branch of the union is derived from a fixed literal or constant expression, allowing it to propagate the filter condition into each branch of the union. This would ideally result in each SELECT within the UNION ALL having its own WHERE clause that compares its literal value to the parameter, effectively pruning entire branches of the union if their literal does not match the parameter.

However, SQLite 3.44.2 does not perform this optimization. Instead, it executes both branches of the UNION ALL subquery in their entirety, scanning all rows from both large_table and other_large_table, and only applies the WHERE foo = ? filter after the unioned result set has been materialized. This leads to unnecessary table scans and a significant performance penalty, especially when the literal values in the union branches are mutually exclusive (e.g., [constexpr_or_literal] and [another_constexpr_or_literal] are distinct constants). The problem is exacerbated when the union subquery is defined in a view, as views abstract away their internal structure, making it difficult to manually rewrite queries that reference them.

Possible Causes: Limitations in SQLite’s Query Optimizer and Structural Constraints

The root cause of this performance issue lies in the interplay between SQLite’s query optimization strategies and the structural constraints imposed by UNION operations. SQLite’s optimizer is designed to be lightweight and fast, prioritizing compilation speed over exhaustive exploration of all possible query rewrites. While it implements many optimizations—such as predicate pushdown, join reordering, and index selection—it does not currently include logic to propagate filter conditions through UNION or UNION ALL subqueries when those conditions reference computed columns derived from literals or constant expressions.

1. Lack of Relational Algebra Proving Engine

SQLite does not employ a formal relational algebra proving engine capable of deducing equivalence between expressions in different parts of a query. When a column in a UNION subquery is defined as a literal or constant expression, SQLite treats it as a runtime-computed value, even though it is statically determinable. The optimizer does not infer that the foo column in the outer query’s WHERE clause could be resolved at compile time by substituting the literal values from each branch of the union. Consequently, the filter is applied post hoc to the entire unioned result set.

2. Column Aliasing and Type Affinity in UNION Operations

In a UNION or UNION ALL operation, the column names, types, and affinities are determined by the first SELECT statement in the union. Subsequent SELECT statements must conform to these definitions, but their column names are ignored. This creates an abstraction layer that obscures the origin of rows from specific branches of the union. Even if the optimizer attempted to push down filters, it would lack metadata to correlate the outer WHERE condition with the literal values in individual union branches, as the alias foo is uniformly applied to all rows regardless of their source.

3. View Materialization and Optimization Barriers

Views in SQLite act as macros that expand their definition into the outer query during parsing. However, certain optimizations are hindered when views contain complex operations like UNION ALL. The optimizer treats the expanded view as a single unit, making it reluctant to dissect and redistribute filter conditions across the union branches. This is particularly true when the view’s definition includes computed columns, as the optimizer cannot guarantee that pushing a filter into the view would preserve semantic correctness without deeper analysis.

4. Static vs. Dynamic Optimization Trade-offs

SQLite’s optimizer is designed to make quick, deterministic decisions during query compilation. Implementing optimizations that require analyzing the relationship between literals in a union and outer filter conditions would increase compilation time and complexity. For many use cases, the cost of such analysis outweighs the benefits, especially when literals are not guaranteed to be mutually exclusive or when union branches have overlapping result sets.

Troubleshooting Steps, Solutions & Fixes: Rewriting Queries and Restructuring Schemas

To address the performance penalty caused by unoptimized UNION ALL subqueries, developers must intervene at the query or schema level to guide SQLite’s optimizer toward a more efficient execution plan. Below are detailed strategies to achieve this, ranging from simple query rewrites to more invasive schema modifications.

1. Manual Query Rewriting to Bypass View Abstraction

When the union subquery is defined in a view, the simplest workaround is to manually inline the view’s definition into the outer query and apply the filter condition to each branch of the union. This eliminates the optimization barrier posed by the view and allows explicit control over predicate placement.

Example:

-- Original query with view
SELECT * FROM my_view WHERE foo = ?;

-- Inlined and optimized query
SELECT large_table.field1, [constexpr_or_literal] AS foo
FROM large_table
WHERE [constexpr_or_literal] = ?
UNION ALL
SELECT other_large_table.field2, [another_constexpr_or_literal]
FROM other_large_table
WHERE [another_constexpr_or_literal] = ?;

Advantages:

• Directly applies filters to each union branch, avoiding full table scans.
• Leverages indexes on large_table and other_large_table if available.

Drawbacks:

• Requires duplicating the view’s logic, violating the DRY (Don’t Repeat Yourself) principle.
• Increases maintenance overhead if the view’s definition changes.

2. Using Common Table Expressions (CTEs) with Filter Pushdown

SQLite supports Common Table Expressions (CTEs), which can be materialized or inlined depending on the optimizer’s decision. By structuring the union as a CTE and applying the filter within the CTE definition, developers can encourage predicate pushdown.

Example:

WITH filtered_union AS (
  SELECT large_table.field1, [constexpr_or_literal] AS foo
  FROM large_table
  WHERE [constexpr_or_literal] = ?
  UNION ALL
  SELECT other_large_table.field2, [another_constexpr_or_literal]
  FROM other_large_table
  WHERE [another_constexpr_or_literal] = ?
)
SELECT * FROM filtered_union;

Advantages:

• Centralizes the union logic while allowing per-branch filtering.
• Maintains readability and reduces code duplication compared to manual inlining.

Drawbacks:

• Requires modifying existing queries to replace view references with CTEs.
• May not be feasible if the CTE is referenced multiple times in complex queries.

3. Schema Restructuring to Eliminate Union-Based Views

If the union subquery serves to combine rows from different tables with a common "type" indicator (e.g., a tag column), consider restructuring the schema to store these rows in a single table with a discriminator column. This replaces the UNION ALL with a simple SELECT on a unified table, enabling straightforward predicate pushdown.

Example:

-- Original tables
CREATE TABLE large_table (field1 INTEGER);
CREATE TABLE other_large_table (field2 INTEGER);

-- Unified table with discriminator
CREATE TABLE unified_table (
  id INTEGER PRIMARY KEY,
  value INTEGER,
  source CHECK (source IN ('large', 'other_large'))
);

-- Query against unified table
SELECT value, 
  CASE source
    WHEN 'large' THEN [constexpr_or_literal]
    WHEN 'other_large' THEN [another_constexpr_or_literal]
  END AS foo
FROM unified_table
WHERE foo = ?;

Advantages:

• Eliminates the need for UNION ALL by consolidating data into a single table.
• Enables indexing on the source and value columns for efficient filtering.

Drawbacks:

• Requires significant schema changes and data migration.
• May not be practical if the original tables have divergent schemas or access patterns.

4. Leveraging Generated Columns for Precomputed Literals

SQLite 3.31.0 introduced generated columns, which can store precomputed values derived from other columns or literals. By adding a generated column to each table that holds the literal value, queries can filter on this column directly, bypassing the need for a union subquery.

Example:

-- Add generated column to large_table
ALTER TABLE large_table ADD COLUMN foo INTEGER
  GENERATED ALWAYS AS ([constexpr_or_literal]);

-- Add generated column to other_large_table
ALTER TABLE other_large_table ADD COLUMN foo INTEGER
  GENERATED ALWAYS AS ([another_constexpr_or_literal]);

-- Query with direct filtering
SELECT field1 AS value, foo FROM large_table WHERE foo = ?
UNION ALL
SELECT field2, foo FROM other_large_table WHERE foo = ?;

Advantages:

• Allows indexing on the generated column for fast lookups.
• Preserves the original table structure while enabling efficient filtering.

Drawbacks:

• Requires altering existing tables, which may not be permissible in production environments.
• Increases storage overhead due to the added generated columns.

5. Conditional Query Construction at the Application Layer

For applications that generate SQL dynamically, conditionally assemble the query to include only the relevant branches of the union based on the expected value of the foo parameter. This approach effectively "prunes" the union at runtime by omitting branches that cannot match the filter.

Example (Pseudocode):

# Application logic
query = ""
if param == constexpr_or_literal:
    query += "SELECT field1, [constexpr_or_literal] AS foo FROM large_table"
if param == another_constexpr_or_literal:
    if query:
        query += " UNION ALL "
    query += "SELECT field2, [another_constexpr_or_literal] FROM other_large_table"

Advantages:

• Eliminates unnecessary table scans by excluding irrelevant union branches.
• Maintains the use of a single query without schema changes.

Drawbacks:

• Introduces application complexity, especially when dealing with multiple parameters.
• Requires tight coupling between the application and database schema.

6. Utilizing Partial Indexes on Literal Expressions

If the literals in the union subquery are known at schema design time, create partial indexes on each table that include rows only when the literal matches a specific value. This optimizes queries that filter on those literals by limiting index scans to relevant rows.

Example:

-- Partial index for large_table
CREATE INDEX idx_large_table_foo ON large_table(field1)
  WHERE [constexpr_or_literal] = ?;

-- Partial index for other_large_table
CREATE INDEX idx_other_large_table_foo ON other_large_table(field2)
  WHERE [another_constexpr_or_literal] = ?;

Advantages:

• Dramatically reduces I/O by indexing only rows that match the literal condition.
• Works seamlessly with existing queries without requiring rewrites.

Drawbacks:

• Requires prior knowledge of possible literal values, limiting flexibility.
• Increases index maintenance overhead for tables with frequent writes.

7. Exploring SQLite Compiler Directives and Pragmas

While SQLite does not support optimizer hints, certain compiler directives and pragmas can influence query planning. Experimenting with these settings may yield marginal improvements, though they are unlikely to resolve the core issue.

Example:

PRAGMA optimize; -- Request optimization based on recent query patterns
PRAGMA analysis_limit=1000; -- Increase statistics collection for better index selection

Advantages:

• Non-invasive and easy to implement.
• May improve performance for related queries.

Drawbacks:

• No direct control over predicate pushdown in union subqueries.
• Effects are situational and not guaranteed.

8. Profiling and Analyzing Query Plans with EXPLAIN

Use SQLite’s EXPLAIN and EXPLAIN QUERY PLAN commands to diagnose how the optimizer processes the query. This reveals whether the filter is applied after the union (indicating no pushdown) and helps validate the effectiveness of applied fixes.

Example:

EXPLAIN QUERY PLAN
SELECT * FROM (
  SELECT field1, [constexpr_or_literal] AS foo FROM large_table
  UNION ALL
  SELECT field2, [another_constexpr_or_literal] FROM other_large_table
) WHERE foo = ?;

Interpretation:

• Look for SCAN TABLE large_table and SCAN TABLE other_large_table in the output, indicating full table scans.
• After applying optimizations, expect SEARCH TABLE ... USING INDEX ... or SCAN ... USING COVERING INDEX ....

Advantages:

• Provides concrete evidence of optimization failures or successes.
• Guides iterative refinement of queries and indexes.

Drawbacks:

• Requires familiarity with SQLite’s virtual machine opcodes.
• Does not directly solve the problem but informs corrective actions.

9. Advocating for Engine-Level Optimizations

As a long-term solution, engage with the SQLite community to advocate for optimizer enhancements that enable predicate pushdown through union subqueries. This could involve submitting feature requests, contributing test cases, or even proposing code changes.

Example Contribution Areas:

• Extending the WHERE clause pushdown logic to handle UNION ALL subqueries with constant expressions.
• Enhancing the view flattening algorithm to propagate outer filters into union branches.

Advantages:

• Benefits the broader SQLite user base.
• Addresses the root cause rather than symptoms.

Drawbacks:

• Requires significant time and expertise to implement.
• No guarantee of adoption by the SQLite development team.

By systematically applying these strategies, developers can mitigate the performance impact of unoptimized UNION ALL subqueries in SQLite. The choice of solution depends on factors such as the application’s flexibility, schema constraints, and willingness to engage in engine-level modifications. In most cases, a combination of query rewriting, schema adjustments, and index optimization will yield the best results, transforming a sluggish union-based query into a performant operation that leverages SQLite’s strengths while avoiding its current limitations.