Query Plan

These are the executable units that perform the raw work on the data. The plan is a tree of these operators. Common examples include:

• Scan Operators: Read data from a source (e.g., NodeIndexScan, AllNodesScan).
• Join Algorithms: Combine data from two streams (e.g., HashJoin, NestedLoopJoin, ExpandInto for graph patterns).
• Filter & Project: Apply predicates (WHERE clauses) and select/transform columns/properties.
• Sort & Aggregate: Order results and perform calculations like COUNT or SUM. Each operator consumes input and produces output for the next operator in the tree.

This specifies how data is initially retrieved from storage. The optimizer chooses the most efficient path based on available indexes and statistics.

• Index Seek: Uses an index (e.g., on a node label and property) to find specific starting points quickly.
• Index Scan: Scans all entries in a particular index.
• Full Scan: Scans all nodes or relationships in the database (often a last resort).
• Id Seek: Direct lookup using an internal node or relationship ID. In native graph databases, index-free adjacency is a critical access path, allowing traversals to follow physical pointers without secondary lookups.

For queries matching multi-hop graph patterns or joining multiple tables, the order and method of joining intermediate results is the single largest determinant of performance. The optimizer evaluates:

• Join Order: The sequence in which pattern segments are matched. The goal is to reduce the size of intermediate result sets early (a principle often called predicate pushdown).
• Join Algorithm: The physical operator used (e.g., Hash Join, Nested Loop). For graph traversals, this may be a specialized Expand operator. Poor join ordering can lead to intermediate result explosion, where temporary tables grow massively before being filtered.

Each component in the plan is annotated with metrics predicted by the optimizer's cost model:

• Estimated Cardinality: The predicted number of rows or graph elements output by an operator. This is foundational; inaccurate estimates lead to poor plan choices.
• Estimated Cost: A unitless number representing the predicted computational expense (I/O, CPU, memory) of an operator, based on cardinality and operator algorithms. These estimates are derived from database statistics (e.g., histograms on property values, distinct counts). Understanding these numbers in an EXPLAIN plan is key to diagnosing performance issues.

This defines the flow of data between operators.

• Pipelined Execution: Operators stream results to the next operator as they are produced (e.g., a filter after a scan). This minimizes memory usage.
• Materialization: An operator must consume and store its entire input before producing output (e.g., a Sort or HashAggregate). This can cause significant memory pressure. Efficient plans maximize pipelining. Some engines use vectorized execution, processing batches of rows (vectors) pipelined between operators to amortize overhead.

Modern distributed graph databases and analytical systems design plans for parallel execution across cores or cluster nodes. Plan components indicate:

• Data Partitioning Strategy: How the graph is split (e.g., by edge-cut, vertex-cut) for distributed processing.
• Parallel Operator Execution: Which stages (like scans or joins) can run concurrently on different data shards.
• Exchange Operators: Points in the plan where data is shuffled or redistributed between workers (common in the Bulk Synchronous Parallel (BSP) model used by frameworks like Pregel).

The dominant strategy for generating a query plan. A cost-based optimizer evaluates multiple semantically equivalent execution plans using a cost model that estimates resource consumption (I/O, CPU, memory). It selects the plan with the lowest estimated cost. This contrasts with rule-based heuristic optimization.

• Core Function: Enumerates plan alternatives and applies a cost function.
• Key Input: Relies heavily on cardinality estimation for accuracy.
• Example: Choosing a hash join over a nested loop join based on the estimated size of intermediate results.

A human-readable representation of the query plan generated by the database optimizer, displayed without executing the query. It is the primary tool for database administrators and developers to diagnose performance issues.

• Purpose: Visualizes the chosen operators (scans, joins, filters), their order, and estimated costs.
• Use Case: Identifying full table scans where an index should be used, or spotting expensive Cartesian products.
• Output: Typically shown as a tree or tabular format, detailing access paths and predicted row counts.

The process of predicting the number of rows or graph elements (nodes, edges) that will be produced by an operation in a query plan. Accurate estimation is the single most critical factor for effective cost-based optimization.

• Challenge: Inaccurate estimates lead the optimizer to choose highly inefficient plans.
• Techniques: Uses histograms, distinct value counts, and correlation statistics.
• Impact: A poor estimate for a join's output size can cause the optimizer to select a suboptimal join ordering.

An advanced optimization paradigm where the execution engine can modify the query plan during runtime. It corrects for inaccurate cardinality estimates observed at execution time.

• Mechanism: Monitors intermediate result sizes and can switch join algorithms or reorder operators mid-query.
• Benefit: Provides robustness against stale statistics or unpredictable data distributions.
• Example: Starting with a hash join, but switching to a broadcast join if one side is much smaller than estimated.

A fundamental rule-based optimization applied during query plan generation. It moves filtering operations (predicates) closer to the original data source.

• Goal: To reduce the volume of data processed in early pipeline stages, minimizing I/O and memory usage for subsequent operations like joins.
• Graph Context: Pushing a label or property filter to a node scan operation, rather than filtering after a large traversal.
• Result: A more efficient plan with smaller intermediate results.

The determination of the sequence in which tables or graph patterns are joined. It is a combinatorially complex problem central to plan optimization, as different orders produce intermediate results of wildly different sizes.

• Optimizer Task: To find the order that minimizes the total cost of intermediate data materialization.
• Graph Query Impact: In a Cypher or SPARQL query matching a multi-hop pattern, the order of expanding edges drastically affects performance.
• Connection: The chosen order is a central component of the final query plan.