Cost-Based Optimization (CBO)

The cost model is the mathematical framework that assigns a numerical cost, representing estimated resource consumption, to each operation in a potential execution plan. It is the core analytical engine of a CBO system.

• Cost Units: Costs are abstract units (e.g., I/O page reads, CPU cycles, network transfer bytes) that model the primary bottlenecks of the system.
• Statistical Inputs: The model relies on cardinality estimates and data distribution statistics (e.g., histograms, distinct value counts) to predict the size of intermediate results.
• System Calibration: Effective models are calibrated to the specific hardware profile (e.g., SSD vs. HDD latency, memory bandwidth) of the deployment environment.

The cardinality estimator predicts the number of rows, nodes, or relationships that will be produced by each operation in a query plan. Accurate estimation is the single most critical factor for correct cost calculation.

• Foundation for Costing: A join that produces 10 rows has a radically different cost than one producing 10 million. The cost model multiplies the cardinality by per-tuple cost factors.
• Relies on Statistics: Uses pre-computed statistics like histograms on property values, degree distributions for nodes, and correlation estimates between predicates.
• Biggest Source of Error: Estimation errors, especially for complex graph pattern joins, compound multiplicatively through a plan, leading the optimizer to choose a severely suboptimal execution path.

The plan space generator is responsible for enumerating the set of semantically equivalent alternative execution plans for a given query. It applies transformation rules to explore the search space.

• Logical Transformations: Includes query rewriting techniques like predicate pushdown, join reordering, and subquery flattening to create new logical plan shapes.
• Physical Implementations: For each logical operator (e.g., a join), it generates multiple physical implementations (e.g., hash join, index nested loop join, merge join).
• Search Strategy: Uses algorithms like dynamic programming or randomized search (e.g., Genetic Algorithm) to navigate the combinatorial explosion of possible plans, pruning dominated plans early.

The statistics manager collects, stores, and maintains the metadata about the data distribution within the knowledge graph that is essential for the cardinality estimator and cost model.

• Data Profiling: Creates histograms for property value ranges, calculates average node degree per relationship type, and tracks the number of distinct labels.
• Refresh Policies: Manages when statistics are updated (e.g., after a threshold of data modifications) to prevent optimization decisions from being based on stale information.
• Storage: Maintains this metadata in a system catalog, often using compact data structures like HyperLogLog for distinct count approximations.

The plan cacher stores previously optimized execution plans (or their components) to avoid the computational overhead of re-optimizing identical or similar queries.

• Keyed by Query Fingerprint: Plans are stored using a hash of the normalized query structure and relevant parameters.
• Invalidation Logic: The cache must invalidate entries when underlying data statistics change significantly or when schema modifications affect the plan's validity.
• Parameter Sensitivity: For parameterized queries, the system may store a single plan deemed robust or multiple plans keyed by parameter value ranges.

The explain and profile interface provides visibility into the optimizer's decisions, allowing database engineers to diagnose performance issues and trust the system's choices.

• Explain Plan: Outputs the chosen execution plan with estimated costs and cardinalities at each step, without running the query.
• Profile Execution: Runs the query and collects actual runtime metrics (rows produced, time spent) for each operator, highlighting discrepancies between estimates and reality.
• Debugging Tool: This feedback loop is essential for tuning statistics, identifying problematic query patterns, and validating the cost model's accuracy.

The cost model is the mathematical heart of CBO. It assigns an estimated numerical cost to each operation in a candidate query plan, representing predicted consumption of I/O, CPU, and network resources. Costs are derived from:

• Cardinality estimates for intermediate results.
• Statistical metadata (e.g., histograms, distinct value counts).
• Hardware-specific constants (e.g., disk seek time, memory bandwidth). The optimizer's goal is to find the plan with the lowest aggregate cost, simulating execution before it runs.

Accurate cardinality estimation—predicting the number of nodes, edges, or paths returned by a graph pattern—is paramount for CBO. Inaccurate estimates lead the optimizer to choose highly inefficient plans. Techniques include:

• Maintaining statistics on label distributions, property value frequencies, and degree (connection count) histograms.
• Using correlation-aware models for queries with multiple predicates.
• Employing graph sampling to estimate the selectivity of complex path patterns, which is notoriously difficult in interconnected data.

The optimizer explores a vast space of semantically equivalent execution plans. For a graph query, this involves evaluating permutations of:

• Join/Expand Ordering: The sequence in which nodes and relationships are matched (e.g., (a)-[:KNOWS]->(b)-[:WORKS_AT]->(c)).
• Physical Operators: Choosing between a traversal, an index seek, or a hash join for each step.
• Predicate Application: Deciding when to filter properties (WHERE n.name = 'Alice'). Algorithms like dynamic programming or heuristic branch-and-bound search are used to navigate this combinatorial space efficiently.

CBO in graph systems must model costs unique to graph traversal:

• Traversal Cost: Function of average degree, fan-out, and path depth. A deep, branching traversal has high cost.
• Index Utilization: Cost of an index seek on a node label/property vs. a full label scan.
• Cache Locality: Leveraging index-free adjacency—where nodes store direct pointers to neighbors—dramatically reduces the I/O cost of traversals compared to index lookups.
• Intermediate Result Size: The cost of materializing intermediate path results in memory, which can explode with poor join ordering.

CBO is often contrasted with Heuristic Optimization (Rule-Based Optimization).

• Heuristic: Applies fixed rules (e.g., 'apply selective filters early', 'use index if available') based on logical query structure. It is fast and predictable but can't adapt to data distribution.
• CBO: Uses a data-driven cost model. It can make counter-intuitive choices (e.g., using a seemingly non-selective index) that are optimal for the specific data, leading to better performance for complex, variable queries. Modern optimizers typically combine both: use heuristics to prune the plan space, then apply CBO to choose the best among the remaining candidates.

To mitigate errors in static cost estimates, systems employ Adaptive Query Processing (AQP). If runtime statistics (e.g., actual cardinality) deviate significantly from estimates, the engine can:

• Re-optimize mid-query, switching to a better execution strategy.
• Use progressive sampling to refine cardinality estimates before full execution.
• Employ materialization points to avoid re-computing expensive sub-plans. This creates a feedback loop, making CBO systems more robust to statistical anomalies and changing data.

Heuristic optimization is a rule-based query optimization strategy that applies a set of predetermined logical transformations to a query plan. Unlike CBO, it does not rely on detailed statistical cost models. Common heuristics include:

• Pushing selections (filters) down the plan tree to reduce data volume early.
• Reordering joins to process smaller tables first.
• Projection pushdown to eliminate unnecessary columns early. It is fast and reliable for simple queries but can produce suboptimal plans for complex operations where data distribution matters.

Cardinality estimation is the process of predicting the number of rows, nodes, or edges that will result from a specific operation in a query plan (e.g., a filter or a join). It is the foundational input for any Cost-Based Optimizer. Accurate estimation is critical; errors propagate and can lead the CBO to choose a plan orders of magnitude slower. Techniques include:

• Maintaining table and column statistics (min, max, distinct values, histograms).
• For graph databases, estimating pattern selectivity.
• Using assumptions like uniform data distribution when statistics are lacking.

A cost model is the algorithmic component that translates a proposed query execution plan into an abstract numerical cost representing estimated resource consumption. It is the core evaluator within a CBO. The model assigns costs based on:

• I/O Cost: Reading data from disk or memory.
• CPU Cost: Processing tuples, evaluating predicates, and performing computations.
• Network Cost: Transferring data between nodes in a distributed system.
• Memory Cost: Utilization of working memory for sorts and joins. The optimizer generates many candidate plans and uses the cost model to select the one with the lowest estimated total cost.

Adaptive Query Processing is an optimization paradigm that addresses the inherent limitations of static CBO by allowing mid-execution plan changes. It monitors runtime statistics (e.g., actual cardinalities) and can dynamically switch to a more efficient strategy if initial estimates prove inaccurate. Key techniques include:

• Mid-query reoptimization: Pausing execution to re-plan based on observed data.
• Eddy operators: A routing operator that dynamically chooses which tuple to process next.
• Progressive query optimization: Learning from past executions to improve future plans. AQP is crucial for complex, long-running queries on data with unpredictable distributions.

A query plan is a sequence of low-level physical operations generated by the optimizer to execute a high-level declarative query. It is the output of the CBO process. A plan is typically represented as a tree of operators, where leaves are data access methods (e.g., index scan, full scan) and internal nodes are processing operations (e.g., join, sort, aggregate). The CBO's role is to explore the vast space of possible plans—varying join orders, access paths, and algorithms—and select the optimal one based on its cost model.

Predicate pushdown is a fundamental optimization technique, often applied as a heuristic but critically evaluated by a CBO. It involves moving filtering operations (predicates) as close as possible to the data source. For example, a filter on a table column is pushed down to occur during the table scan, rather than after a join. This dramatically reduces the volume of intermediate data that must be processed by upstream operators. The CBO uses its cost model to decide if pushdown is beneficial, especially in cases involving expensive predicates or correlated subqueries.