Cardinality Estimation

Cardinality estimation is inherently probabilistic. Optimizers rely on statistical summaries of the data, such as histograms, to estimate selectivity—the fraction of rows that satisfy a given predicate. For graph queries, this extends to estimating the number of nodes matching a label or the edges traversed by a pattern. The accuracy depends heavily on the statistical independence assumption, which often breaks down with correlated data, leading to significant estimation errors.

The estimated cardinality of intermediate results is the primary driver for join ordering decisions in relational databases and pattern matching order in graph queries. The optimizer aims to sequence joins to minimize the size of intermediate Cartesian products. A poor estimate can cause the optimizer to choose a suboptimal order, resulting in a plan that is orders of magnitude slower. For example, joining a large, incorrectly estimated result set early can blow up memory usage and CPU time.

The quality of estimation is directly tied to the database statistics maintained by the system. Key structures include:

• Histograms: Distribute column values into buckets to estimate predicate selectivity.
• Distinct Value Counts: The number of unique values for an attribute or label.
• Correlation Statistics: Capture relationships between columns (e.g., multi-column statistics).
• Graph-Specific Statistics: For property graphs, this may include degree distributions for nodes with specific labels. Outdated or missing statistics force the optimizer to use default, often inaccurate, heuristics.

A major source of estimation error is data correlation. Traditional histograms often assume attribute values are independent. In real-world data, correlations are common (e.g., city = 'New York' and state = 'NY'). A query with predicates on both correlated attributes will have its selectivity vastly underestimated if treated independently. Advanced techniques like multi-dimensional histograms, sampling, and machine learning models are used to mitigate this, but they add computational overhead.

In graph databases, estimation faces unique challenges:

• Path Cardinality: Estimating the number of results for a variable-length path (e.g., (:Person)-[:KNOWS*1..5]->(:Person)) is exponentially harder, requiring models of the graph's degree distribution and clustering coefficient.
• Label and Property Distribution: The distribution of node labels and edge types significantly impacts traversal estimates.
• Subgraph Isomorphism: For pattern matching, the estimator must predict how many subgraphs in the data match the query pattern, which involves complex combinatorial reasoning.

Cardinality estimates are not used in isolation; they are the critical input to the optimizer's cost model. The cost model translates estimated row counts into predicted consumption of system resources (I/O, CPU cycles, memory). An operation with an estimated cardinality of 10 rows will be assigned a low cost, making it likely to be executed early. Therefore, cardinality errors propagate directly into cost miscalculations, causing the optimizer to select a genuinely expensive plan.

Cost-based optimization is a query optimization strategy that evaluates multiple potential execution plans using a cost model to select the one with the lowest estimated resource consumption (I/O, CPU, memory). It fundamentally relies on cardinality estimation to predict the size of intermediate results, making accurate estimates critical for choosing the optimal plan. Without good cardinality estimates, CBO can select disastrously slow plans.

• Core Dependency: Cardinality estimation provides the primary input (row counts) to the cost model's calculations.
• Plan Space Exploration: The optimizer uses cost to prune the vast space of possible join orders and access methods.

A cost model is a component of a query optimizer that assigns a numerical cost, representing estimated resource usage, to each operation in a potential execution plan. It translates physical operations (e.g., sequential scan, index seek, hash join) and their predicted cardinalities into a single comparable metric. The model incorporates:

• I/O Cost: Estimating page reads/writes based on data size and access paths.
• CPU Cost: Estimating processing cycles for predicates, joins, and aggregations.
• Memory Cost: Estimating working memory for operations like sorts and hash tables.

Inaccurate cardinality estimates propagate through the cost model, leading to incorrect cost assignments and poor plan selection.

A query plan is a sequence of low-level operations generated by a database optimizer to execute a high-level declarative query. It is the direct output of the optimization process, which uses cardinality estimation and a cost model to choose between plan alternatives. Key components influenced by cardinality estimates include:

• Join Order: The sequence of joins, which is highly sensitive to the predicted size of intermediate tables.
• Join Algorithm Selection: Choice between Nested Loop, Hash Join, or Merge Join based on expected data volumes.
• Access Path Selection: Decision to use a full scan versus an index seek.

An EXPLAIN plan often shows the optimizer's estimated cardinality for each step alongside the actual rows, highlighting estimation errors.

Adaptive query processing is an optimization paradigm where the execution engine monitors runtime statistics and can dynamically modify the execution plan mid-query. It is designed to correct for poor cardinality estimates made during initial optimization. Techniques include:

• Mid-Query Re-Optimization: Pausing execution after processing a portion of data, re-estimating cardinalities based on observed statistics, and switching to a better plan if needed.
• Adaptive Joins: Starting with one join algorithm (e.g., Nested Loop) and seamlessly switching to another (e.g., Hash Join) if the incoming row stream is larger than expected.

AQP acts as a runtime safety net for cardinality estimation failures, especially useful for complex queries with correlated predicates.

A histogram is the most common data structure used by query optimizers for cardinality estimation. It summarizes the distribution of values in a table column by dividing the value domain into a series of buckets (ranges). Each bucket stores:

• The range of values (e.g., 10-19).
• The number of distinct values in the range.
• The frequency of rows in that range.

When estimating the selectivity of a predicate like WHERE price > 100, the optimizer uses the histogram to approximate the fraction of rows satisfying the condition. Multi-dimensional histograms and correlation statistics are advanced techniques to improve estimates for predicates on multiple columns.

Predicate selectivity is the estimated fraction of rows from a table or intermediate result that will satisfy a given filter condition (predicate). It is a core probability used in cardinality estimation. The optimizer calculates it for each predicate (e.g., status = 'active', date > '2024-01-01') and combines them, often assuming independence, to estimate the final cardinality.

• High Selectivity: A predicate that filters out most rows (e.g., user_id = 1234). Favors index usage.
• Low Selectivity: A predicate that filters few rows (e.g., gender = 'female'). May favor a full scan.

Selectivity estimation error is the primary source of cardinality misestimation, especially when predicates are correlated or data is skewed.