Query Rewriting

Predicate pushdown is a fundamental rewriting rule that moves filtering conditions as close as possible to the data source. In graph queries, this means applying node or edge property filters during the initial traversal or scan, drastically reducing the size of intermediate result sets passed to subsequent operations like joins.

• Example: A query to find (p:Person)-[:WORKS_AT]->(c:Company) where c.name = 'Inferensys' is rewritten to scan only for Company nodes with that name first, before performing the expansive WORKS_AT traversal.
• Impact: Minimizes I/O and memory usage by eliminating non-matching data early in the pipeline.

View unfolding replaces a reference to a predefined view or named subquery with its underlying definition. This allows the optimizer to apply global transformations—like predicate pushdown or join reordering—across the entire expanded query, rather than treating the view as a black box.

• Use Case: A view SeniorEmployees defined as MATCH (p:Person) WHERE p.years_exp > 10 RETURN p is inlined into a larger query. The optimizer can then push a predicate like p.department = 'Engineering' directly into the view's scan.
• Benefit: Enables holistic optimization that can reveal redundant operations or more efficient join paths.

This technique rewrites the order and structure of joins (or graph pattern matches) to minimize the computational cost. Join reordering sequences patterns to produce the smallest intermediate results first. Common subexpression factorization identifies and computes duplicate sub-patterns once, caching the result for reuse.

• Graph Example: A query matching (a)-[:KNOWS]->(b), (a)-[:WORKS_WITH]->(c), (b)-[:KNOWS]->(c) might be reordered to find the smallest KNOWS subgraph first.
• Optimization Goal: Reduces the combinatorial explosion inherent in matching multi-hop graph patterns, which is critical for cost-based optimization.

Decorrelation transforms a nested subquery (e.g., a correlated subquery that executes once for each row of an outer query) into an equivalent, non-nested form using joins or semi-joins. This removes iterative execution, allowing for set-based, parallel processing.

• SPARQL/Cypher Context: A OPTIONAL or EXISTS sub-pattern that references variables from an outer match is rewritten into a left-outer-join or an anti-join.
• Performance Impact: Eliminates the performance penalty of repeated subquery execution, often resulting in orders-of-magnitude speedups for complex existential checks.

Constant folding evaluates expressions composed solely of constants at compile time (e.g., rewriting WHERE age > 18+2 to WHERE age > 20). Constant propagation then pushes these known values through the query, potentially simplifying other expressions or enabling more aggressive predicate pushdown.

• Graph Application: Propagating a constant node ID or unique property value can allow the optimizer to select a highly efficient direct lookup or index scan instead of a full label scan.
• Benefit: Reduces runtime computation overhead and provides the optimizer with more concrete information for plan selection.

This class of rewrites removes operations that do not affect the final query result. This includes eliminating duplicate predicates, removing unnecessary DISTINCT operators when uniqueness is guaranteed by constraints, and pruning unreachable query branches based on contradictory conditions.

• Example: A WHERE clause with p.name = 'Alice' AND p.name = 'Alice' has the duplicate removed. A MATCH for a node with two mutually exclusive labels is simplified.
• Goal: Streamlines the logical query plan, reducing both compilation and execution overhead for cleaner, faster plans.

Query rewriting is a logical optimization phase. It operates on the high-level, declarative query structure (e.g., an abstract syntax tree or relational algebra expression) before a cost-based optimizer translates it into a physical execution plan with specific algorithms (e.g., hash join vs. merge join) and access methods.

• Logical Transformations: Include pushing filters down, eliminating redundant joins, and simplifying expressions. These are generally cost-independent.
• Physical Optimization: Follows rewriting and is cost-dependent, selecting specific operators and data structures based on estimated I/O, CPU, and memory usage.

Rewriters apply a catalog of equivalence-preserving rules. Key heuristics aim to reduce the size of intermediate results early in the plan.

• Predicate Pushdown: Move filtering conditions (WHERE, FILTER) as close to the base data scan as possible.
• Projection Pushdown: Eliminate unused columns early to reduce data volume in pipes.
• Join Elimination: Remove unnecessary joins where foreign key constraints guarantee the join does not alter cardinality.
• View Unfolding: Replace a reference to a view with its underlying query definition, enabling further optimization.
• Constant Folding: Evaluate constant expressions at compile time (e.g., rewrite WHERE price > 10+5 to WHERE price > 15).

In property graph and RDF databases, rewriting leverages graph-specific semantics and pattern matching.

• Path Pattern Simplification: Collapse linear chains of nodes and relationships into more efficient single-step traversals where possible.

• Label and Type Filter Pushdown: Push node/edge label filters to the initial scan or traversal operation, leveraging index-free adjacency.

• SPARQL-to-SQL Rewriting: In RDF triplestores, complex SPARQL queries with OPTIONAL, UNION, and property paths are often rewritten into a series of optimized SQL queries against the underlying triple table or property tables.

A powerful application of query rewriting is automatic query rewriting with materialized views. The optimizer recognizes that part or all of a query can be answered by a precomputed materialized view, rewriting the query to scan the view instead of the base tables.

• This requires view matching, a complex subgraph isomorphism problem, to check if the view's definition is equivalent to, or contains, the query's needs.
• It dramatically accelerates queries on aggregated or joined data, trading storage for compute time.

This advanced form of rewriting uses integrity constraints and domain knowledge (e.g., from an ontology) to transform queries. It's central to semantic reasoning engines.

• Example Using Constraints: If a query asks for Employee and a constraint states Manager SubClassOf Employee, the rewriter can include Manager instances in the result, or rewrite to search the superclass.
• Inference-Based Rewriting: In a knowledge graph, if :hasParent is defined as transitive, a query for ancestors can be rewritten into a simpler, bounded traversal.

While powerful, query rewriting has boundaries.

• Semantic Equivalence: The rewritten query must produce the exact same result set as the original. Not all faster forms are equivalent.
• Rule Explosion: The number of possible rewrites can be large. Optimizers use heuristics to prune the search space.
• Cost Blindness: Pure logical rewriting does not consider data distribution or physical storage. A logically "better" form (e.g., a different join order) may be physically worse, which is why it is followed by cost-based optimization.
• Complexity with Subqueries and Aggregation: Rewriting nested subqueries and queries with aggregation requires careful handling to preserve grouping and scoping rules.

Cost-based optimization is the dominant strategy in modern query optimizers. It evaluates multiple candidate execution plans using a cost model that estimates resource consumption (I/O, CPU, memory). The optimizer selects the plan with the lowest estimated cost. Unlike heuristic rules, CBO relies on cardinality estimation to predict intermediate result sizes, making it data-driven but sensitive to statistical accuracy.

Heuristic optimization applies rule-of-thumb transformations to a query based on logical algebraic properties. Common heuristics include:

• Predicate pushdown: Moving filters closer to the data scan to reduce early result size.
• Projection pushdown: Eliminating unused columns/attributes early.
• Removing redundant operations. These rules are applied before or alongside cost-based optimization to generate a better starting set of candidate plans.

A specific, critical heuristic and rewrite rule. Predicate pushdown moves filtering conditions as close as possible to the base data access operation (e.g., a node label scan). For example, rewriting MATCH (p:Person) WHERE p.age > 30 RETURN p.name to ensure the p.age > 30 filter is applied while scanning Person nodes, not after joins. This dramatically reduces the volume of data flowing through subsequent pipeline stages.

Join ordering is arguably the most impactful decision in optimizing complex graph pattern matches involving multiple nodes and relationships. The optimizer must determine the sequence for joining graph patterns. A poor order can create massive intermediate results (cartesian products). Optimizers use cost models to evaluate permutations, often employing dynamic programming for complex queries. For a query like MATCH (a)-[]->(b), (b)-[]->(c), (a)-[]->(c), the choice of starting point (a, b, or c) is crucial.

A materialized view is a precomputed result set stored as a physical table or graph. Query rewriting can transparently redirect a query to use a materialized view if it is semantically equivalent, bypassing expensive joins and aggregations. For example, a view containing (Customer)-[PURCHASED]->(ProductCategory) could rewrite a detailed transactional query. This is a powerful form of optimization that trades storage for compute time.

Adaptive query processing addresses the limitations of static optimization by allowing the execution engine to modify its plan at runtime. If cardinality estimates prove severely inaccurate during execution, an AQP system can switch to a more efficient algorithm or join order mid-query. This represents a shift from purely compile-time optimization (like classic query rewriting) to a hybrid runtime approach for handling data skew and unpredictable distributions.