Predicate Pushdown

The optimizer analyzes a declarative query (e.g., in Cypher or SPARQL) and identifies filtering predicates—conditions like WHERE n.age > 30 or FILTER (?cost < 100). It then rewrites the logical or physical execution plan to apply these filters immediately during the initial data scan or traversal, before expensive operations like joins or global aggregations. This prevents the unnecessary propagation of irrelevant data through the query pipeline.

This is the most significant performance gain. By filtering at the source:

• Disk I/O is minimized as fewer data pages are read from storage.
• Network transfer is reduced in distributed graph databases (e.g., using sharding or graph partitioning), as only relevant data is sent across the network for further processing.
• Memory pressure is lowered because smaller intermediate results are held in working memory. This directly translates to lower latency and resource consumption.

Effective predicate pushdown relies on specific database engine capabilities:

• Indexes: Predicates on indexed properties (e.g., WHERE user.id = 123) can be pushed down into an index seek operation, bypassing full scans.
• Storage Layer APIs: Modern graph and vector databases expose APIs that allow the query layer to delegate filters to the storage engine.
• Partition Pruning: In partitioned graphs, predicates on partition keys allow the engine to skip entire irrelevant shards or partitions. Without these, the 'pushdown' may be purely logical within the query engine itself.

Predicate pushdown does not operate in isolation; it synergizes with other techniques:

• Cost-Based Optimization (CBO): The optimizer uses cardinality estimation to decide if pushing a predicate down is beneficial (e.g., a non-selective filter may not be worth it).
• Join Ordering: Early filtering drastically reduces the size of inputs to join operations, making optimal join ordering more impactful.
• Early Termination: When combined with a LIMIT clause, aggressive pushdown can allow the engine to find the required number of matching records almost instantly.
• Materialized Views: Predicates may be pushed down into a precomputed materialized view scan.

Not all predicates can be pushed down. Key constraints include:

• Derived Values: Filters on expressions or functions computed after the initial scan (e.g., WHERE upper(n.name) = 'ALICE') often cannot be pushed.
• Cross-Entity Predicates: Filters that require a join to evaluate (e.g., WHERE n.manager.department = 'Sales') must typically be applied after the join is performed.
• Optimizer Intelligence: The optimizer must correctly identify pushdown opportunities, which depends on the sophistication of its heuristic and cost-based rules.
• Trade-offs: Excessive pushdown complexity at the storage layer can sometimes offset benefits.

Consider a property graph query to find active projects in a department: MATCH (d:Department {name:'Engineering'})<-[:PART_OF]-(p:Project) WHERE p.status = 'Active' AND p.budget > 100000 RETURN p.name

Without Pushdown: The engine might scan all Project nodes, join them to Department, and then apply the status and budget filters.

With Pushdown: The optimizer pushes the predicates p.status = 'Active' and p.budget > 100000 into the scan of the Project label. It uses an index on Project(status) or a storage filter to retrieve only active, high-budget projects before performing the join to Department. This can reduce the join workload by orders of magnitude.

In a traditional RDBMS like PostgreSQL, the optimizer pushes WHERE clause predicates down to the table scan operation.

Example Query:

sqlCopy
SELECT name, department
FROM employees
JOIN salaries ON employees.id = salaries.emp_id
WHERE employees.salary > 100000 AND employees.department = 'Engineering';

Optimization: The filter employees.salary > 100000 AND employees.department = 'Engineering' is applied during the scan of the employees table, before the join with salaries. This drastically reduces the number of rows joined, improving performance by orders of magnitude.

Systems like Snowflake or Amazon Redshift leverage columnar storage. Predicate pushdown is critical for column pruning and partition elimination.

Key Mechanisms:

• Column Pruning: If a query only selects columns A and B, only those column files are read from storage.
• Partition Elimination: If a table is partitioned by date and the query filters WHERE date = '2024-01-15', the query engine reads only the specific partition directory, ignoring all others.
• Zone Map Filtering: Metadata (min/max values) for data blocks is checked first. Blocks that cannot contain rows matching the predicate are skipped entirely, reducing I/O.

Spark's Catalyst optimizer performs predicate pushdown to the underlying data source connector (e.g., Parquet, JDBC).

Example with Parquet:

pythonCopy
# Original logic
filtered_df = spark.read.parquet("data.parquet")\
    .filter("salary > 100000")\
    .select("name", "department")

What Happens:

1. Catalyst pushes the salary > 100000 filter into the Parquet reader.
2. The Parquet reader uses column statistics and page-level indexes to skip row groups and data pages.
3. Only the name and department columns are read (projection pushdown). This minimizes the data deserialized into Spark's JVM memory.

In a native graph database like Neo4j, predicates on node labels and properties are pushed down to the traversal engine.

Example Cypher Query:

cypherCopy
MATCH (p:Person)-[:WORKS_FOR]->(c:Company {name: 'Inferensys'})
WHERE p.yearsExperience > 5 AND p.role = 'Engineer'
RETURN p.name

Optimization:

• The label Person and property filters yearsExperience > 5 and role = 'Engineer' are applied as the Person nodes are traversed, using indexes where available.
• The pattern (:Company {name: 'Inferensys'}) is resolved first via a unique lookup, anchoring the traversal. This prevents building a large intermediate set of all Person nodes before filtering.

Systems like Presto or Apache Calcite query across multiple, heterogeneous data sources (e.g., MySQL, Kafka, S3). Predicate pushdown is essential to avoid moving entire datasets.

Process:

1. The federated engine decomposes a global SQL query.
2. It identifies which sub-queries and predicates can be executed by the underlying source's native engine.
3. It pushes filters and projections down via the source's connector (e.g., translates to a JDBC WHERE clause for MySQL, or a filter expression for a Parquet file in S3).
4. Only the filtered, projected results are transmitted over the network to the coordinator for final processing (e.g., joins, aggregations).

Not all predicates can be pushed down. Understanding the barriers is key for performance tuning.

Common Barriers:

• User-Defined Functions (UDFs): Most external data sources cannot execute custom, user-written logic.
• Complex Expressions: Expressions involving multiple columns or subqueries may not be supported by the source's query language.
• Data Type Mismatches: Implicit casting or unsupported data types can prevent pushdown.
• Opaque Connectors: Some legacy or proprietary connectors may not expose pushdown capabilities.

Diagnosis: Use the database's EXPLAIN or EXPLAIN ANALYZE command. If a filter operation appears late in the plan (e.g., after a costly join or aggregate), pushdown may have failed, indicating a potential optimization point.

A query plan is a sequence of low-level operations (e.g., scans, joins, filters) generated by a database optimizer to execute a high-level declarative query. It represents the concrete roadmap for data retrieval.

• The optimizer's goal is to find the plan with the lowest estimated execution cost.
• Predicate pushdown is a specific transformation applied within this plan, moving filters closer to data scans.
• Viewing the EXPLAIN output of a query shows the chosen plan and where predicates are evaluated.

Cost-Based Optimization is a strategy where the query optimizer evaluates multiple potential execution plans using a cost model (estimating I/O, CPU, memory) to select the most efficient one.

• It relies heavily on cardinality estimation to predict intermediate result sizes.
• The decision to push a predicate down is often a cost-based choice; if filtering early reduces the cost of subsequent operations (like joins), CBO will favor that plan.
• Contrasts with heuristic optimization, which uses fixed rules.

Early termination is an optimization where query execution stops as soon as it has gathered enough results to satisfy the query, such as when a LIMIT or TOP N clause is used.

• While distinct from predicate pushdown, they are complementary. Pushing down a selective predicate first drastically reduces the data scanned, making early termination even faster.
• Crucial for interactive applications where returning the first few results quickly is paramount.

A materialized view is a precomputed result set of a query, stored physically as a table. It trades storage and maintenance overhead for dramatically faster query performance.

• Optimization with materialized views involves query rewriting to use the view instead of base tables.
• Predicates can be pushed down into the view definition itself, or applied against the materialized data if the view already contains filtered results.
• Effective for complex, frequently run queries on relatively static data.

Vectorized execution is a processing paradigm where database operations act on batches of data (vectors) at a time, rather than row-by-row (the tuple-at-a-time model).

• It maximizes utilization of modern CPU SIMD (Single Instruction, Multiple Data) instructions and reduces per-row function call overhead.
• Predicate evaluation is highly efficient in this model, as filtering logic can be applied to entire columns of data in a tight loop.
• Works in concert with predicate pushdown; pushed-down predicates are evaluated using these high-speed vectorized operations.

Adaptive Query Processing is a paradigm where the execution engine monitors runtime statistics and can dynamically modify the query plan mid-execution to correct for poor initial estimates.

• If the optimizer incorrectly decides not to push a predicate down (due to a bad cardinality estimate), an adaptive system might switch to a plan that does so after seeing the true data flow.
• Represents a move from static, compile-time optimization to runtime, feedback-driven optimization.
• Key for handling unpredictable data distributions and complex multi-join queries.