Join Ordering

The number of possible join orders grows factorially with the number of relations or patterns in a query. For a query joining n tables, there are n! possible left-deep trees and even more bushy trees. This combinatorial explosion makes exhaustive search infeasible for complex queries, forcing optimizers to rely on heuristics, dynamic programming, or randomized algorithms to explore the space efficiently.

Modern join ordering is predominantly cost-based. The optimizer:

• Estimates the cardinality (size) of intermediate results for each potential join order.
• Uses a cost model to predict I/O, CPU, and memory usage.
• Selects the order with the lowest estimated total cost. Accurate cardinality estimation is paramount; errors can lead the optimizer to choose a plan orders of magnitude slower than the optimal one.

The primary goal is to reduce the size of intermediate tables or subgraphs passed between join operations. A core heuristic is to perform highly selective joins early. This minimizes the data that subsequent, more expensive operations (like large Cartesian products) must process. In graph queries, this translates to matching the most constrained node or edge patterns first to bound the search frontier.

Optimizers consider different join tree structures:

• Left-Deep Trees: Each join has one outer relation that is the result of a previous join. This is efficient for pipelining and works well with nested-loop joins and index usage.
• Bushy Trees: Joins can have two complex inputs. This can enable greater parallelism and better use of hash joins but complicates pipelining.
• Right-Deep Trees: A variant often used for hash joins in parallel systems. The choice of tree shape is integral to the join ordering decision.

Join ordering is inseparable from the choice of physical join algorithm (e.g., hash join, merge join, nested loop). The optimal order for a nested loop join (which benefits from indexed outer relations) may differ from that for a hash join (which builds an in-memory hash table from one input). The optimizer must evaluate the logical join order and the physical implementation simultaneously.

Static cost estimates can be wrong. Adaptive query processing techniques monitor actual cardinalities during execution and may reorder subsequent joins mid-query. For example, if an intermediate result is 100x larger than estimated, the system can switch from a nested-loop to a hash join plan or adjust the order of pending joins. This provides robustness against poor statistics.

For a query joining N tables or graph patterns, there are (2(N-1))!/((N-1)!) possible join orders. For a modest 10-way join, this is over 17 billion possibilities. Exhaustive search is impossible, forcing optimizers to use heuristics and cost-based pruning. The goal is to find a plan that minimizes the size of intermediate results, as large temporary tables are the primary performance bottleneck.

Optimizers choose between two primary join tree shapes:

• Left-Deep Trees: Each join has one base relation and one intermediate result. This structure is highly amenable to pipelined execution and efficient use of indexed nested-loop joins.
• Bushy Trees: Joins can combine two intermediate results. This can dramatically reduce intermediate result sizes for some queries but may require materialization of sub-results, increasing memory pressure. Graph databases often default to left-deep plans for traversal efficiency.

In a Cypher query like MATCH (a:Person)-[:WORKS_AT]->(b:Company)<-[:WORKS_AT]-(c:Person), the optimizer must decide whether to:

1. Find all Person nodes (a), traverse to their Company (b), then find other Person nodes (c).
2. Find all Company nodes (b) first, then find all connected Person nodes. The optimal order depends on label cardinality and edge selectivity. Starting with the most selective pattern (e.g., a Company with a specific name) reduces the search space exponentially.

A cost model estimates the 'expense' of each potential join order using statistics:

• Node/Edge Counts: The total number of entities for a given label or relationship type.
• Selectivity: The estimated fraction of nodes/edges that will pass a filter (e.g., WHERE a.age > 30).
• Index Availability: The presence of indexes on properties or relationships. The optimizer generates candidate plans, estimates the cost of each (in I/O and CPU), and selects the cheapest. Poor cardinality estimation is the most common cause of bad join orders.

Before detailed cost estimation, optimizers apply heuristic rules:

• Apply Selective Filters Early: Push WHERE clauses down to scan operations.
• Small Relations First: Join the relations with the smallest estimated cardinality early to grow intermediate results slowly (often encapsulated in the System R optimizer's greedy algorithm).
• Exploit Foreign Keys: Prefer joins that have equi-join predicates on foreign-key relationships.
• Avoid Cartesian Products: Postpone cross-joins until necessary. These rules prune the search space for the cost-based optimizer.

The impact of join ordering is non-linear. Consider a social network query finding friends-of-friends:

• Good Order: Start from a highly indexed user, traverse 1-hop friends, then 2-hop friends. Execution time: < 100ms.
• Poor Order: Start by scanning all 'FRIEND_OF' edges in the graph, then filter. Intermediate result: Billions of edges. Execution time: > 30 minutes (or timeout). This makes join ordering a primary focus for database tuning and query plan analysis.

A query plan is the low-level sequence of physical operations (e.g., index scans, joins, filters) generated by a database optimizer to execute a declarative query. It is the concrete output of the optimization process, where join ordering decisions are finalized. The plan dictates data access paths and the flow of intermediate results.

• Physical Operators: Include Hash Join, Merge Join, Index Scan, and Filter.
• Visualization: Tools like EXPLAIN or EXPLAIN ANALYZE render the plan as a tree for performance debugging.
• Execution: The database's query engine interprets this plan to retrieve the final result set.

Cost-Based Optimization is the dominant strategy where an optimizer evaluates numerous alternative execution plans—including different join orders—using a cost model. It selects the plan with the lowest estimated resource consumption (I/O, CPU, memory).

• Cost Model: Uses database statistics (cardinality, data distribution) to predict the expense of each operation.
• Search Space: The number of possible join orders grows factorially; CBO uses dynamic programming (e.g., System R optimizer) or heuristic searches to navigate this space.
• Dependency: Accurate cardinality estimation is critical for CBO to produce efficient join orders.

Cardinality estimation is the process of predicting the number of rows or graph elements (nodes, edges) that will be produced by a query operation. It is the most critical input for a cost-based optimizer when evaluating join orders.

• Foundation for Costing: Inaccurate estimates lead the optimizer to choose suboptimal join sequences, causing performance degradation.
• Techniques: Relies on histograms, distinct value counts, and correlation assumptions. For graph queries, estimating path selectivity is particularly challenging.
• Impact: A poor estimate for an early join can exponentially inflate the size of incorrect intermediate results.

Predicate pushdown is an optimization that applies filtering conditions as early as possible in the query plan, often before join operations are executed. This directly influences effective join ordering by drastically reducing the size of the datasets to be joined.

• Principle: Move WHERE clause filters and attribute selections closer to the base table or index scan.
• Benefit: Reduces the cardinality of intermediate results, making subsequent joins cheaper and altering the optimal join sequence.
• Graph Context: In a graph query, this equates to filtering nodes by labels or properties immediately during traversal, not after paths are materialized.

Heuristic optimization applies rule-of-thumb transformations to a query plan based on logical algebraic properties, often before or instead of detailed cost estimation. It provides a fallback or preliminary strategy for join ordering.

• Common Heuristics: "Apply selective joins first," "Perform Cartesian products last," and "Push selections and projections down."
• Use Case: Used when statistics are unavailable, or to reduce the search space for a subsequent cost-based optimizer.
• Limitation: While generally beneficial, heuristics are not data-aware and can sometimes prevent the discovery of a truly optimal plan.

Adaptive Query Processing is a runtime optimization paradigm where the execution engine monitors actual intermediate result sizes and can dynamically reorder remaining join operations mid-query. It corrects for inaccurate cardinality estimates made during static planning.

• Mechanisms: Includes techniques like mid-query reoptimization and adaptive join operators (e.g., hash join switching to a broadcast join).
• Solves Join Ordering Mistakes: If the initial plan chooses a poor join order that produces a much larger intermediate set than predicted, AQP can alter the sequence for subsequent joins.
• Graph Relevance: Particularly valuable for complex graph pattern matching where path cardinalities are highly variable and difficult to predict statically.