Index Selection

Modern index selection is primarily a cost-based optimization (CBO) process. The optimizer enumerates viable access paths for a query, consults a cost model to estimate the I/O, CPU, and memory consumption of each, and selects the plan with the lowest estimated cost. This model relies heavily on accurate cardinality estimation for each operation. Poor estimates can lead to the selection of suboptimal indexes, causing significant performance degradation.

The optimizer identifies all relevant indexes that could satisfy the query's predicates and join conditions. For a property graph query, this includes:

• Label-property indexes for lookups like MATCH (p:Person {name: 'Alice'}).
• Relationship type indexes for fast edge traversal.
• Full-text indexes for semantic search on text properties.
• Composite indexes for multi-property predicates. The optimizer evaluates scanning the base table (a full graph traversal) versus using one or more of these indexed access paths.

Index selection is deeply influenced by higher-level optimization decisions, especially join ordering. The choice of which index to use for the first node in a graph pattern directly determines the size of the initial working set, which cascades through the cost of all subsequent joins. Techniques like predicate pushdown are enabled by indexes, allowing filters to be applied at the source scan rather than on intermediate results. The use of early termination with LIMIT clauses can also make certain index scans more favorable.

While indexes speed up reads, they impose a write penalty. Each insert, update, or delete of a vertex, edge, or property must be reflected in all relevant indexes. The optimizer's cost model typically only considers read-time performance, but the administrative decision of which indexes to create must balance this trade-off. Materialized views represent an extreme form of this trade-off, pre-computing entire query results at a significant maintenance cost for predictable read patterns.

• Static Selection: Traditional optimizers perform index selection once, during query compilation, based on stored statistics. The chosen plan is cached and reused.
• Dynamic Selection (Adaptive): In adaptive query processing (AQP) systems, the engine may re-evaluate index choices mid-execution if runtime cardinalities diverge sharply from estimates. This is crucial for graph queries with highly variable data distributions.

Beyond standard B-tree indexes, graph databases employ specialized structures:

• Index-free adjacency: Not an index in the traditional sense, but a storage design where nodes hold direct pointers to neighboring edges, making traversals a pointer chase rather than an index lookup. This is the ultimate 'index' for local graph navigation.
• Spatial indexes (e.g., R-trees): For geolocation queries on nodes.
• Vector indexes: For similarity search on embedded node properties, crucial for graph-based RAG systems. The optimizer must understand the capabilities and cost profiles of these diverse structures.

Cost-based optimization is the overarching strategy that makes index selection possible. The optimizer generates multiple candidate execution plans, estimates the resource cost of each using a cost model, and selects the plan with the lowest estimated cost. Index selection is a primary lever within CBO, as the choice of index dramatically impacts I/O and CPU estimates for scan and join operations.

Cardinality estimation is the process of predicting the number of rows or graph elements returned by a query operation. Accurate estimates are fundamental to effective index selection. If the optimizer underestimates the result size of a filter, it may incorrectly choose a full table scan over a highly selective index scan. Poor cardinality estimates are a leading cause of suboptimal index choices.

Predicate pushdown is an optimization that moves filtering conditions as close to the data source as possible. This technique directly interacts with index selection. A pushed-down predicate on an indexed column allows the storage engine to use the index for a highly efficient range or point lookup, filtering out irrelevant data before it enters the query pipeline. The optimizer evaluates which predicates can be pushed down to inform its index choices.

A materialized view is a precomputed result set stored as a physical table. In optimization, materialized views act as sophisticated, pre-joined indexes. The query optimizer may select to rewrite a query to use a materialized view instead of accessing base tables, a decision analogous to index selection. This is often governed by a cost-based comparison between scanning the view and executing the original query plan against raw data and indexes.

An explain plan is the output of the query optimizer, detailing the step-by-step execution strategy for a query. It is the primary tool for diagnosing index selection decisions. Database engineers analyze explain plans to verify:

• Which indexes were chosen (e.g., Index Scan using user_email_idx).
• Which indexes were not used (a potential sign of missing or unsuitable indexes).
• The estimated vs. actual row counts, highlighting cardinality estimation errors.

The cost model is the internal algorithm that assigns a numerical cost to operations in a query plan. It is the decision engine for index selection. The model incorporates statistics like:

• I/O Cost: Reading index pages vs. data pages.
• CPU Cost: Comparing keys in an index tree.
• Selectivity: The proportion of rows a filter will return. The optimizer uses the cost model to compare the expense of an index scan + bookmark lookup against a full table scan.