Access Path Selection in an RDBMS

Why this paper matters

Selinger et al.’s 1979 paper Access Path Selection in a Relational Database Management System marks the first rigorous, implemented solution to the optimizer problem in a declarative query language. Before System R, relational systems either ignored performance or resorted to brute-force scanning. This paper provides a cost-based framework for selecting access paths-indexes, sequential scans, or join algorithms-given a non-procedural SQL predicate. The authors formalize the problem as a dynamic programming search over the space of possible plans, pruning dominated alternatives with cardinality estimates derived from table statistics. This approach established the core architecture for all later relational optimizers, from PostgreSQL to commercial engines like IBM Db2. In 2026, the same principles govern distributed query planning in cloud-native systems, where partition pruning, zone-aware routing, and predicate pushdown are direct descendants of System R’s cost model.

The paper’s significance extends beyond mechanics: it codified the separation of logical and physical optimization, a principle now embedded in RAG pipelines and vector databases. By treating SQL as a specification rather than a procedure, it paved the way for heterogeneous storage engines (row, columnar, vector) to coexist under a unified planner. Its influence persists in systems that optimize across storage tiers, where access path selection determines whether a query uses an in-memory B-tree, a Parquet file, or a GPU-accelerated vector index. In short, Selinger et al. did not merely build an optimizer; they defined the optimizer as the central intelligence of a database system.

The paper also laid the groundwork for transaction-aware planning, a concept later refined in systems like Google Spanner and CockroachDB. By modeling I/O and CPU costs explicitly, the authors created a framework that could later incorporate network latency, consensus overhead, and distributed consistency constraints. This adaptability is why modern systems like TiDB and YugabyteDB still rely on cost-based optimizers despite running on entirely different hardware and network topologies. The principles from 1979 now power optimizers that must balance ACID guarantees with sub-millisecond latency in globally distributed environments. Even in systems where eventual consistency is the norm, such as Amazon DynamoDB, the planner must still weigh the cost of stale reads against the latency of strongly consistent operations-a trade-off that traces back to System R’s original cost model.

Key contributions

• Introduced a cost-based optimizer that selects access paths (index, sequential scan, join method) using dynamic programming over a space of candidate plans, replacing heuristic or fixed-strategy approaches.
• Formalized cardinality estimation from table statistics and predicate selectivities, enabling accurate cost comparisons between plans.
• Defined join ordering as an optimization problem, proving the need to explore permutations rather than relying on fixed left-deep or bushy heuristics.
• Implemented predicate pushdown and early selection in the query plan, reducing intermediate result sizes before joins or aggregation.
• Demonstrated extensibility by allowing new access methods (e.g., hash joins) to be integrated without changing the planner’s core algorithm.
• Delivered a production-quality implementation in System R, validating the approach with real workloads and tuning the cost model for IBM’s hardware.
• Proposed a modular optimizer architecture that separated logical and physical optimization, enabling storage engines and access methods to evolve independently.

Impact on modern systems

The optimizer in System R is the direct ancestor of every cost-based planner in use today. PostgreSQL’s planner.c still uses dynamic programming for join ordering and applies the same pruning logic Selinger et al. introduced. When PostgreSQL chooses between an index-only scan and a sequential scan on a partitioned table, it is executing a 1979 algorithm, albeit with modern statistics and I/O cost models. More striking is the lineage in distributed databases. CockroachDB’s distributed planner inherits the same cost-based framework but extends it with zone-aware routing and partition pruning, two optimizations that reduce cross-AZ latency by orders of magnitude. In CockroachDB 23.1, the planner uses per-region statistics to prune entire partitions, a technique that would be unrecognizable to Selinger’s team but is a direct evolution of their access path selection logic.

FoundationDB and Spanner take the idea further by integrating transaction-aware planning. Spanner’s TrueTime-aware optimizations ensure that access path choices respect external consistency guarantees, a constraint System R never faced. Yet the core planner in Spanner (née F1) is still a descendant of System R’s cost model, retrofitted for Paxos and Spanner’s lock-free reads. Even vector databases like Milvus rely on relational-style optimizers when they embed SQL-like filters alongside vector similarity searches. Milvus’ query planner uses dynamic programming to decide whether to filter rows via a scalar index before or after computing vector distances-precisely the kind of predicate-ordering problem Selinger et al. solved in 1979. The planner’s role in Milvus is now to minimize GPU memory pressure, but the algorithmic skeleton remains unchanged.

Hardware evolution has changed cost parameters, not the optimizer’s architecture. In 1979, CPU cycles dominated; today, NVMe bandwidth and DRAM locality do. PostgreSQL 16 introduced a tablesample-based cost model that weights I/O more heavily, a tweak Selinger et al. anticipated when they wrote, “The choice of access path depends critically on the relative speeds of the storage devices.” Modern systems like ScyllaDB push this further by modeling tail latency percentiles in their cost functions, but the planner still prunes plans using the same dominance rules from the original paper. The continuity is remarkable: an algorithm designed for IBM 370 disks now schedules queries on AWS io2 Block Express volumes, with only the cost constants updated.

The influence of System R’s optimizer extends to columnar databases like ClickHouse and Apache Doris. These systems use the same dynamic programming approach to decide between merging sorted runs, using skip indexes, or falling back to full scans. ClickHouse’s MergeTree engine, for instance, employs a cost-based planner to select the optimal merge strategy for LSM-trees, a technique that would feel familiar to the authors of the 1979 paper. Even LSM-tree-based systems like ScyllaDB and Cassandra implicitly rely on the same pruning logic when balancing read amplification against write throughput. The optimizer’s role in these systems is to navigate the trade-offs Selinger et al. first articulated: sequential scans versus random I/O, CPU versus memory bandwidth, and the hidden costs of compaction.

Another modern example is Apache Doris, which uses a cost-based optimizer to choose between its CBO (Cost-Based Optimizer) and RBO (Rule-Based Optimizer) modes. In Doris 2.0, the planner dynamically switches between the two based on query complexity and data distribution, a hybrid approach that echoes System R’s early experiments with heuristic and cost-based strategies. The planner’s ability to adapt to skewed data distributions or extreme cardinalities demonstrates how Selinger’s framework has scaled to petabyte-scale analytics.

AI era: how LLMs and vector databases relate to this paper

Vector databases and RAG pipelines inherit the core problem System R solved: how to choose an access path given a non-procedural specification. In RAG, the user’s prompt is the query, the vector index is the access path, and the planner must decide whether to retrieve embeddings via exact nearest neighbor, approximate search, or a hybrid filter. Pinecone’s hybrid search, for example, uses a cost model analogous to Selinger et al.’s: it weighs the latency of HNSW traversals against the precision of scalar filters, pruning dominated plans before execution. The same dynamic programming technique now runs on GPUs, but the algorithmic structure-explore candidate plans, estimate result sizes, prune the uncompetitive-is identical.

LLM inference latency has reintroduced the need for early selection and predicate pushdown. In a RAG pipeline, the planner must decide whether to filter documents by metadata (e.g., language, date) before or after retrieving embeddings. Weaviate’s query planner implements this as a two-phase optimizer: a scalar sub-planner prunes irrelevant partitions before the vector search begins, reducing the embedding retrieval space by 90% in some cases. The planner’s cost model compares the CPU cost of scalar filtering against the GPU cost of vector search, a trade-off Selinger et al. would recognize immediately. This mirrors the optimizer’s role in Google Bigtable, where column-family scans are prioritized based on predicate selectivity before full-table reads.

AI agent state stores are another frontier. Systems like LangGraph or CrewAI maintain a semantic index over task state, materialized as a vector index over JSON blobs. When an agent retrieves prior steps to plan the next action, the optimizer must choose between a full vector search (expensive) and a lightweight scalar scan on metadata (cheap). This mirrors System R’s join-order problem: the planner must sequence filters and vector searches to minimize latency. Qdrant’s raft-based replication and its query planner are direct descendants of this logic, with the twist that the cost model now includes network round-trips for consensus. The same principles apply in Amazon DynamoDB’s sparse index scans, where the planner must balance the cost of filtering against the cost of retrieving entire items.

Embedding models themselves can be seen as access methods. When a system chooses to use a 7B-parameter model versus a distilled 125M model for retrieval, it is selecting a “plan” whose cost is measured in FLOPs and memory bandwidth. Weaviate’s dynamic model switching is a cost-based optimizer applied to ML inference. The same principles govern LLM routing: a controller like vLLM uses a cost model to choose between models on different GPUs, pruning dominated options before scheduling. This is not unlike the optimizer in System R deciding between a hash join and a nested-loop join based on estimated result sizes.

Finally, semantic indexes-vector representations of SQL schemas or JSON schemas-rely on the same planner architecture. When a system rewrites a user’s prompt into SQL or MongoDB queries, it must plan the access path through the semantic index. This planner uses dynamic programming to explore join orders in the semantic graph, estimating result cardinalities from embedding distances. The algorithm is a fusion of System R’s optimizer and vector search, proving that the 1979 paper’s ideas are now foundational for AI infrastructure. Even systems like PostgreSQL’s pgvector extension implicitly use the same cost-based logic when deciding between IVFFlat and HNSW indexes for vector similarity search.

The AI era has also brought new constraints that Selinger et al. could not have anticipated, such as GPU memory pressure and token budgeting. Modern RAG systems must plan not just the retrieval but also the LLM’s context window usage. For example, LlamaIndex’s query planner uses a cost model to decide whether to truncate retrieved chunks, reorder them, or fetch additional context-all while minimizing token usage. This is a direct extension of the optimizer’s role in System R, where the goal was to minimize intermediate result sizes before joins or aggregation. The continuity is striking: an algorithm designed for 1970s hardware now schedules AI workloads on A100 GPUs, with only the cost parameters updated to reflect FLOPs and memory bandwidth.

Another critical AI-era challenge is real-time embeddings serving. Systems like Milvus or Qdrant must choose between on-the-fly embedding generation and precomputed vector search, often under strict latency budgets. The planner here is a cost-based optimizer that weighs the latency of calling a remote embedding model against the I/O cost of reading precomputed vectors. This mirrors System R’s original problem of choosing between an index scan and a sequential scan, but now the “index” is a GPU-accelerated model and the “scan” is a network call. The same dominance rules apply: if the model’s latency exceeds the I/O cost of a cache hit, the planner selects the precomputed path.

Further reading

• IBM System R: The Relational Database Management System
• PostgreSQL Source Code: src/backend/optimizer/
• CockroachDB Architecture Docs: Distributed SQL
• Weaviate Hybrid Search Whitepaper
• Pinecone Vector Indexing Guide
• The CAP Theorem and modern distributed systems
• LSM-tree: A Storage Architecture for Modern LSM Engines