Cost Model

The foundational input for any cost model. It predicts the number of intermediate results (e.g., rows, nodes, edges) that will be produced by each operation in a query plan. Inaccurate estimates are the primary cause of poor plan selection.

• Mechanism: Uses statistics (histograms, distinct value counts) and assumptions about data distribution.
• Challenge: Correlated predicates and complex graph patterns often violate independence assumptions, leading to significant estimation errors.
• Example: Estimating the result size of a multi-hop path query in a social network graph.

The abstract or concrete units used to quantify resource consumption. A cost model translates physical resource usage into a single, comparable numerical score.

• Common Metrics:
  • I/O Cost: Number of disk page reads/writes.
  • CPU Cost: Number of CPU cycles for operations like predicate evaluation, hash table construction, or tuple comparison.
  • Network Cost: Amount of data transferred across a cluster (for distributed graphs).
  • Memory Cost: Working memory required for operations like sorts and joins.
• Weighting: The cost model applies weights to different metrics (e.g., I/O is often 10x more expensive than CPU) based on the target hardware profile.

Mathematical functions that calculate the cost of a specific database operation based on its input cardinality and system parameters.

• Scan Operations: Cost = Pages_in_Relation * C_page_read.
• Join Operations: Vary dramatically by algorithm:
  • Hash Join: Cost = (Build_Cardinality * C_hash) + (Probe_Cardinality * C_lookup).
  • Index Nested Loop Join: Cost = Outer_Cardinality * (C_index_lookup + C_fetch).
  • Graph Traversal: Cost = Start_Vertices * (Fanout ^ Depth) * C_edge_follow, where fanout is estimated average degree.
• System Constants: Formulas rely on calibrated constants (e.g., C_page_read, C_tuple_process) that are specific to the hardware and storage engine.

The empirical data about the stored data that feeds the cardinality estimator and cost formulas. Without accurate statistics, the cost model operates on guesses.

• Core Statistics: Table/Graph size, number of distinct values per attribute/label, value histograms, correlation statistics.
• Graph-Specific Statistics: Degree distribution histograms, label frequencies, relationship selectivity.
• Maintenance: Statistics must be updated periodically via ANALYZE commands or automatically as data changes. Stale statistics render the cost model ineffective.

The process of generating alternative execution plans for a given query. The cost model is applied to each candidate plan to find the cheapest. The optimizer does not evaluate all possible plans (combinatorial explosion) but uses strategies to prune the search space.

• Join Ordering: For a query joining N tables/patterns, there are N! possible orders. Dynamic programming (e.g., System R optimizer) is used to find the optimal order without exhaustive search.
• Algorithm Selection: For each operation (e.g., a join), the optimizer must choose among algorithms like hash join, merge join, or index nested loop join, each with its own cost formula.
• Access Path Selection: Deciding whether to use a full scan, an index scan, or an index-only scan for data retrieval.

The process of adjusting the cost model's internal parameters to reflect the actual performance characteristics of the underlying hardware and software stack. A default, uncalibrated model often performs poorly.

• System Constants: Key parameters like sequential I/O cost, random I/O cost, and CPU tuple cost must be measured or tuned.
• Methods:
  • Micro-benchmarking: Running controlled, low-level operations to measure their actual latency.
  • Feedback Loop: Using execution feedback from actual queries to adjust future estimates (a form of adaptive optimization).
• Impact: Proper calibration can lead to order-of-magnitude performance improvements for complex analytical and graph queries.

The process by which a query optimizer predicts the number of rows or graph elements (e.g., nodes, relationships) that will be returned by a specific operation in a query plan. This prediction is the most critical input to a cost model, as the estimated size of intermediate results directly drives the estimated cost of operations like joins and filters. Poor cardinality estimates are the primary cause of suboptimal plan selection in cost-based optimization.

A query optimization strategy that evaluates multiple potential execution plans using a cost model to select the one with the lowest estimated resource consumption (e.g., I/O, CPU, memory). Unlike heuristic optimization, CBO uses statistical metadata about the data to make informed, quantitative decisions about join ordering, access path selection, and algorithm choice.

A sequence of low-level physical operations (a 'plan') generated by a database optimizer to execute a high-level declarative query. The optimizer uses the cost model to assign a numerical cost to different plan variants. The final selected plan is typically the one with the lowest estimated total cost, representing the engine's best-effort strategy for efficient execution.

A representation, generated by a database engine, that details the sequence of operations, chosen algorithms, and access methods it will use (or did use) to execute a given query. A key feature of an explain plan is the display of the estimated cost and estimated cardinality for each operation, allowing developers to diagnose performance issues and understand the optimizer's decisions based on the cost model.

An optimization paradigm where the query execution engine monitors runtime statistics (e.g., actual rows processed) and can dynamically modify the execution plan mid-query. This is used to correct for inaccurate predictions made during static planning, often caused by flaws in the cardinality estimation or cost model. Techniques include re-optimization and mid-query switching of join algorithms.

A query optimization strategy that applies a set of rule-of-thumb transformations to a query plan based on logical properties and algebraic equivalences, rather than detailed cost estimation. Examples include 'perform selections early' (predicate pushdown). It is often used as a preliminary step before cost-based optimization or in systems where building a detailed cost model is impractical.