Storage Engines, Indexing and Query Processing

Introduction

A database management system (DBMS) is not merely a collection of tables and SQL statements. Its performance and reliability depend on how logical data is represented on storage, transferred through memory, organized into access paths, and transformed into an executable plan. Storage engines, indexes, buffers, and query optimizers form an integrated system: a change in one layer often changes the cost and suitability of choices in another.

This chapter examines these layers from a postgraduate perspective. It distinguishes physical storage from logical relations, compares row-oriented and column-oriented engines, explains major index structures, and analyzes parsing, optimization, execution, joins, pipelining, materialization, and cost estimation. Particular attention is given to concurrency, workload characteristics, and storage-aware calibration rather than to simplistic claims that one structure is universally superior.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Explain pages, records, free-space management, buffers, and the buffer pool.

2. Compare row stores and column stores for transactional and analytical workloads.

3. Select and analyze B+-tree, hash, bitmap, and specialized indexes.

4. Explain parsing, logical rewriting, physical planning, and execution.

5. Compare nested-loop, hash, merge, and index-based join algorithms.

6. Distinguish pipelined execution from materialization and analyze their trade-offs.

7. Use cost models critically, including storage-aware calibration and cardinality uncertainty.

8. Evaluate indexing and query-processing decisions in a realistic database scenario.

1. The Physical Foundation: Pages, Records and Buffers

1.1 Pages as the unit of I/O

Although applications request rows, storage devices and database files usually transfer data in blocks called pages. A page commonly ranges from 4 KiB to 64 KiB, depending on the DBMS and workload. If a relation occupies \(B(R)\) pages and a query must scan it, the approximate sequential I/O cost is \(B(R)\) page reads, subject to caching, prefetching, compression, and parallelism.

A page normally contains a header, record or slot information, payload space, and sometimes checksums or transaction metadata. A slotted-page layout stores a directory of record offsets in the header. This allows records to move within a page while their logical identifiers remain stable, an important property for variable-length records and updates.

1.2 Records and physical identifiers

A fixed-length record is straightforward to locate because field offsets are known. Variable-length records require length descriptors or offset arrays. A record identifier (RID) is often represented as a page identifier plus a slot number. If records can move between pages, an indirection pointer may preserve RID validity, but pointer chasing adds access cost.

Heap files store records without maintaining an ordering on a search attribute. They are flexible for inserts but may require a full scan when no useful index exists. Sorted files support efficient range access but impose higher insertion and maintenance costs. Clustered storage attempts to place records with similar index-key values near one another; “clustered” is a physical organization property, not simply the existence of an index.

1.3 Free-space management

Insert and update operations require knowledge of pages with sufficient free space. A free-space map, page directory, or extent-level summary can provide this information. Poor free-space management causes excessive page splits, fragmentation, and additional I/O. Variable-length updates are especially difficult: an update that enlarges a record may force relocation, making stable physical identifiers and index maintenance important design concerns.

1.4 Buffer pools

The buffer pool caches database pages in main memory. A buffer manager decides which page to fetch, pin, unpin, and evict. A page cannot normally be evicted while pinned by an operator. Dirty pages must be written back according to the recovery and durability protocol.

The common cost approximation is:

\[

T \approx N_{IO}t_{IO}+N_{CPU}t_{CPU}+N_{net}t_{net},

\]

where the terms represent I/O, CPU, and network work. This is a model, not a law. Random and sequential I/O have different latencies; SSDs reduce but do not eliminate this distinction; cloud storage may introduce queueing and remote-network effects.

Replacement policies such as LRU, clock, and workload-aware variants attempt to retain useful pages. A single global LRU policy can perform poorly for large scans because a scan may evict frequently reused pages. Scan-resistant policies and separate buffer pools can protect transactional working sets from analytical operations.

2. Row Stores, Column Stores and Hybrid Organization

2.1 Row-oriented storage

A row store keeps the fields of one tuple together. It is effective when transactions retrieve or update many attributes of a small number of rows. It also supports efficient reconstruction of complete records and commonly provides strong locality for point lookups.

Its weaknesses appear in analytical queries that read a few columns from millions of rows. Unneeded attributes consume I/O and memory bandwidth. Updates may also cause write amplification when a large physical row must be rewritten.

2.2 Column-oriented storage

A column store keeps values of the same attribute together. A query such as

```sql

SELECT region, SUM(revenue)

FROM Sales

WHERE sale_date >= DATE '2025-01-01'

GROUP BY region;

```

may read only the date, region, and revenue columns. Column stores support compression because adjacent values often have similar types or distributions. Dictionary encoding, run-length encoding, bit packing, and delta encoding are common techniques. Vectorized execution processes batches of values rather than invoking an operator for every tuple, improving CPU efficiency.

Column storage is not automatically faster. Point updates, frequent multi-column modifications, and transactional constraints can make it expensive. Many systems therefore use a hybrid approach: row-oriented storage for operational data and columnar copies, projections, or materialized views for analytics.

2.3 Storage format and execution together

Compression changes the cost model. A compressed column may require fewer page reads but more CPU for decompression. Predicate pushdown can avoid decompressing irrelevant segments. Zone maps or min–max metadata can eliminate segments whose value ranges cannot satisfy a predicate. Thus, physical design and execution strategy must be considered jointly.

3. Index Structures

An index is an auxiliary access path mapping search-key values to records or pages. It accelerates selected operations but consumes storage and imposes maintenance, logging, and concurrency costs.

3.1 B+-trees

A B+-tree is a balanced multiway search tree. Internal nodes contain separator keys and child pointers; leaf nodes contain keys and record pointers, often with links to adjacent leaves. All search paths have similar height, and leaf links support ordered scans.

If the effective fan-out is \(f\), a height estimate is approximately

\[

h \approx \lceil \log_f(N) \rceil,

\]

where \(N\) is the number of leaf-level entries. This estimate assumes reasonably uniform occupancy and ignores root-level special cases. Real costs depend on cache residency, page occupancy, key size, compression, and concurrency.

B+-trees support equality, range predicates, prefix searches, ordering, and sometimes index-only scans. Inserts and deletes may cause splits, merges, or redistribution. Fill factors reserve space for future modifications, reducing immediate splits at the cost of additional pages.

#### Composite indexes

For an index on \((A,B,C)\), the leading-key principle generally permits efficient access using predicates on \(A\), and often on \(A\) and \(B\). A predicate only on \(B\) usually cannot use the index for a narrow ordered seek, although an optimizer may choose an index scan or specialized skip-scan technique. Equality conditions on leading columns followed by a range condition are often particularly effective.

#### Covering indexes

An index is covering for a query if it contains all columns needed to evaluate the query and produce its result. It can avoid base-table lookups, but wider indexes reduce fan-out, consume more storage, and increase write cost. Covering is therefore a workload trade-off, not an unconditional improvement.

3.2 Hash indexes

A hash index applies a hash function to a key and directs the search to a bucket. Expected equality lookup can be close to constant-time under good distribution and sufficient bucket capacity. Hash indexes are poorly suited to ordered range queries because hash values do not preserve key order.

Dynamic hashing methods, such as extendible or linear hashing, grow gradually. Overflow chains and skew can substantially worsen performance. Hash indexes also require careful handling of concurrent bucket splits and durable metadata.

3.3 Bitmap indexes

A bitmap index maintains a bit vector for each value or value range; bit position \(i\) represents whether row identifier \(i\) has that value. Bitwise AND and OR operations can evaluate combinations of low-cardinality predicates efficiently. Bitmap indexes are common in read-intensive analytical systems.

The update cost is not universally high or low. It depends on the representation—uncompressed or compressed—the encoding scheme, row-identifier stability, insertion pattern, cardinality, and whether updates alter indexed values. In a compressed bitmap, a local change may be cheap or may trigger substantial run rewriting. Stable, append-oriented identifiers often simplify maintenance; arbitrary inserts or row movement can be expensive. Consequently, bitmap indexes should not be characterized simply as “unsuitable for updates”; their suitability must be evaluated against the specific encoding and workload.

3.4 Specialized indexes

Full-text indexes use inverted lists mapping terms to documents and may support ranking, stemming, and positional searches. Spatial indexes such as R-trees organize bounding rectangles for multidimensional data. GiST-like frameworks support extensible search predicates, while BRIN-style summaries store coarse information for physically correlated data and use very little space. Function-based indexes materialize an expression, such as `LOWER(email)`, when the query uses the same deterministic expression.

Approximate structures, including Bloom filters, can reject nonmatching values with low memory usage but cannot safely prove that a matching value exists. They are useful as filters in storage and distributed execution, not as substitutes for exact indexes.

3.5 Index concurrency and recovery

Index operations occur concurrently with reads, inserts, updates, and deletes. Latch coupling may protect page structure during tree traversal; logical locks protect transaction-level visibility and isolation. Modern B+-tree algorithms seek short-duration page latches and avoid holding structural latches across long transactions. Splits must be made crash-safe using write-ahead logging or equivalent recovery mechanisms.

A useful distinction is between latches and locks. Latches protect in-memory physical structures for short periods; locks express transactional conflicts and may be held until commit. Incorrectly treating one as the other can cause corruption or excessive blocking. Hot root or leaf pages may require optimistic techniques, key-range partitioning, or contention-aware designs.

4. From SQL Text to an Execution Plan

4.1 Parsing and binding

The DBMS first tokenizes SQL and constructs a parse tree. Syntax errors are detected at this stage. Name resolution binds table and column references, checks data types and privileges, and expands views or macros where appropriate. Parameterized statements separate query structure from values and can improve security and plan reuse.

4.2 Logical query processing

The bound query is transformed into a relational algebra representation involving selection, projection, join, grouping, and ordering. Algebraic equivalences permit transformations such as:

\[

\sigma_{p}(R \Join S) \equiv (\sigma_{p}(R)) \Join S,

\]

when predicate \(p\) refers only to attributes of \(R\) and the join semantics permit the transformation. Such rules are not universally valid for outer joins, nondeterministic functions, user-defined functions, or expressions with side effects.

Common rewrites include predicate pushdown, projection pruning, constant folding, subquery decorrelation, join elimination using trusted constraints, and simplification of redundant predicates. The optimizer must preserve SQL’s three-valued logic and null semantics.

4.3 Physical planning

The optimizer chooses access paths, join order, join algorithms, parallelism, aggregation strategies, and materialization points. A cost-based optimizer estimates the cost of candidate plans using table statistics, histograms, distinct-value counts, correlation information, and system parameters.

The optimizer’s problem is combinatorial. Dynamic programming can find good join orders for moderate query sizes, while randomized or greedy methods are used for larger join graphs. Hints can be useful but may become harmful when data distributions change.

5. Operator Execution: Pipelining and Materialization

5.1 Pipelining

In a pipelined plan, an operator produces tuples directly for its parent. A selection can filter tuples as they pass through a scan, reducing memory requirements and allowing the first results to appear quickly. Iterator models commonly use a `next()` interface, while vectorized engines pass batches.

Pipelining is most effective for streaming operators such as selection and projection. It is constrained by blocking operators, including sort, hash aggregation, and many forms of duplicate elimination, which must consume substantial input before producing output.

5.2 Materialization

Materialization writes an intermediate result to memory or storage before a later operator consumes it. It can be advantageous when an intermediate is reused, when a blocking boundary simplifies parallel scheduling, or when it limits repeated computation. It is costly because it adds writes, reads, memory pressure, and possibly temporary-file management.

A hybrid plan may pipeline filters into a hash build, materialize a reusable dimension relation, and then pipeline probe results into an aggregation. The correct choice depends on cardinality, reuse, buffer availability, spill risk, and failure recovery. Pipelining is not always faster: repeated rescans or severe memory pressure can make controlled materialization preferable.

6. Join Algorithms

Let \(B(R)\) and \(B(S)\) denote page counts, and let \(M\) be the number of available buffer pages. The following formulas are idealized and assume no cache effects, suitable partitioning, and conventional page-oriented execution.

6.1 Nested-loop joins

A tuple nested-loop join compares each tuple of one relation with tuples of the other and is generally expensive. A block nested-loop join reads a block of outer pages and scans the inner relation. Its approximate cost, with \(R\) as outer, is

\[

B(R)+\left\lceil\frac{B(R)}{M-2}\right\rceil B(S),

\]

assuming at least one page for input management and one for the inner scan. The formula is a simplified I/O estimate; buffer policies and output costs are excluded.

If an index exists on the join attribute of \(S\), an index nested-loop join may be effective when \(R\) is small or highly selective. Its cost depends on the number of outer tuples, index height, clustering, and matching tuples. An unclustered index can cause many random base-table reads.

6.2 Hash joins

A partitioned hash join hashes both inputs into corresponding partitions and joins matching partitions. Under adequate memory and a reasonably uniform hash function, its idealized cost is approximately

\[

3(B(R)+B(S)),

\]

representing one read/write partitioning pass and one read for the join pass. This is not guaranteed: skew, insufficient memory, recursive partitioning, spills, and skew-handling strategies alter the cost. Hash joins are generally appropriate for equality joins, not arbitrary inequalities.

6.3 Sort-merge joins

Sort-merge join sorts both inputs and then scans the sorted streams. It supports equality and ordered merge predicates and can exploit pre-existing ordering. External sorting requires multiple passes when the inputs exceed memory. A rough external-sort analysis uses the number of initial runs and merge fan-in; exact costs depend on page allocation and implementation details. Sort-merge is attractive when inputs are already sorted, when output ordering is useful, or when a non-equality merge is required.

6.4 Join selection

No join algorithm dominates universally. The optimizer considers relation sizes, selectivity, indexes, ordering, available memory, skew, parallelism, and whether intermediate results can be pipelined. Join order is often more important than small differences in operator implementation because an early selective join can reduce later work dramatically.

7. Cardinality Estimation and Cost Models

For a simple selection on attribute \(A\), an optimizer may estimate

\[

|\sigma_{A=a}(R)| \approx \frac{|R|}{V(R,A)},

\]

where \(V(R,A)\) is the estimated number of distinct values, under a uniform-distribution assumption. This assumption fails with skew. Histograms improve estimates for range predicates, but correlations between columns remain difficult.

For a join \(R\bowtie S\) on attribute \(A\), a common approximation is

\[

|R\bowtie S| \approx \frac{|R||S|}{\max(V(R,A),V(S,A))},

\]

assuming compatible domains and independence-like conditions. It is an estimate, not an identity. Foreign-key constraints, heavy hitters, nulls, and correlated predicates can invalidate it.

7.1 Storage-aware calibration

A mature cost model should be calibrated using measurements rather than fixed folklore constants. Relevant parameters include sequential and random page latency, CPU cost per tuple or vector, decompression cost, memory bandwidth, network transfer, parallel startup overhead, and spill cost. Calibration should use representative data and should distinguish warm-cache from cold-cache behavior.

Statistics must be refreshed as data evolves. Monitoring actual cardinalities, chosen plans, execution time, spills, and buffer misses enables adaptive diagnosis. However, adaptive reoptimization must account for plan instability and overhead. A plan that is optimal for one parameter value may be poor for another, making parameter-sensitive planning valuable.

8. Worked Application: An Illustrative Retail Analytics Case

Background

Consider an online retailer with a row-oriented operational database containing `Orders`, `OrderItems`, `Customers`, and `Products`. Analysts repeatedly ask for monthly revenue by region and product category. The `OrderItems` table contains 800 million rows, while `Orders` contains 120 million rows. Transactional queries require rapid lookup by `order_id` and updates to order status.

Problem

The analytical query scans only a few attributes but competes with transactions for buffer space. A composite B+-tree on `(customer_id, order_date)` does not efficiently support the principal report, whose filters are on date and status and whose grouping is by region and category.

Analysis

The operational workload favors row storage and B+-trees for point lookups. The report favors columnar access, compression, predicate pushdown, and vectorized aggregation. A bitmap index on a low-cardinality status column could help an analytical store, but its update behavior in the operational system would depend on row movement, bitmap compression, and update frequency; it should not be introduced solely on the assumption that all bitmap updates are expensive.

Approach

The organization creates a columnar analytical projection refreshed through change capture. It stores date, status, region, category, quantity, and revenue-related measures, with sorting or clustering by date. Zone maps eliminate irrelevant date segments. The operational database retains B+-tree indexes for order identifiers and transaction predicates. In the analytical engine, a date filter is pushed below the join, projections remove unused columns, and a vectorized hash aggregation computes revenue. The optimizer’s cost model is calibrated separately for compressed scans and decompression CPU cost.

The execution plan pipelines filtered column batches into the aggregation when memory is sufficient. If a dimension table is reused across parallel tasks, it may be materialized or broadcast. Spill monitoring is enabled because a severe cardinality underestimate could make an in-memory hash table exceed its budget.

Outcome

The operational workload avoids large reporting scans, while the analytical workload reads fewer bytes and uses batch processing. The design adds data freshness delay, storage duplication, change-capture complexity, and governance requirements. It is therefore a workload-architecture decision rather than a claim that column stores are universally superior.

Learning points

1. Physical organization must match access patterns.

2. Index choice depends on selectivity, clustering, maintenance, and concurrency.

3. Query plans are sensitive to statistics and storage-specific costs.

4. Pipelining, materialization, and spill behavior must be analyzed together.

5. Separating operational and analytical workloads can be more effective than over-indexing one system.

9. Challenges, Governance and Best Practices

Important challenges include skewed data, stale statistics, parameter-sensitive queries, index bloat, fragmentation, write amplification, hot pages, memory pressure, and plan regressions after upgrades. Distributed systems add network cost, data movement, locality, and fault-tolerance considerations.

Database governance includes access control, encryption, audit logging, retention, and protection of sensitive indexed values. Indexes may duplicate personal or confidential data, so they must be included in classification, deletion, and access-control procedures. Query logs and execution plans can also reveal sensitive literals or business behavior and should be governed accordingly.

Recommended practices are to:

• measure representative workloads before adding indexes;
• inspect actual execution plans, not only estimated plans;
• maintain statistics and validate them after major data changes;
• avoid redundant or overlapping indexes unless their benefits are demonstrated;
• test under realistic concurrency and cache conditions;
• distinguish logical locks from physical latches;
• monitor spills, buffer misses, page splits, and index contention;
• calibrate cost parameters on the target hardware and storage tier;
• use columnar projections or materialized views for recurring analytical patterns;
• document freshness, recovery, and governance implications of derived data.

Contemporary Directions

Modern engines increasingly combine vectorized execution, just-in-time compilation, adaptive joins, learned or enhanced cardinality models, tiered storage, and cloud elasticity. Learned models can capture distributions that traditional histograms miss, but they introduce training, drift, explainability, and operational-maintenance concerns. Autonomous indexing and tuning systems can recommend structures from workload traces, yet recommendations must be constrained by write cost, privacy, and change-control policy.

Research continues on learned indexes, persistent-memory layouts, disaggregated storage, approximate query processing, differential privacy for analytical data, and robust optimization under cardinality uncertainty. These developments reinforce a central principle: query processing is an evidence-driven systems problem involving data, hardware, workload, and operational constraints.

Chapter Summary

Pages are the fundamental transfer units through which records move between persistent storage and memory. Slotted pages, free-space maps, buffer replacement, pinning, and dirty-page management determine physical behavior. Row stores favor transactional access to complete tuples, while column stores favor selective analytical scans, compression, and vectorized execution.

B+-trees support equality, range, and ordered access; hash indexes favor equality; bitmap indexes are powerful for suitable analytical workloads but have representation- and identifier-dependent maintenance costs. Specialized structures address text, spatial, approximate, and physically correlated data. Index concurrency requires a clear distinction between latches and transactional locks.

SQL processing proceeds from parsing and binding through logical rewriting, physical optimization, and execution. Join selection depends on sizes, selectivities, indexes, ordering, memory, skew, and parallelism. Pipelining reduces intermediate storage and latency, whereas materialization can support reuse, blocking boundaries, and memory control. Cost models are estimates whose quality depends on statistics and storage-aware calibration. The appropriate design is therefore a measured fit between workload, physical organization, concurrency, and governance requirements.

Key Terms

Page: Fixed-size unit of database storage transfer.

Slotted page: Page layout using a slot directory for record locations.

Record identifier (RID): Physical reference to a record, commonly page plus slot.

Buffer pool: Main-memory cache managed by the DBMS.

Heap file: Unordered collection of stored records.

Clustered storage: Physical arrangement that groups records according to an ordering key.

B+-tree: Balanced multiway index with data references at the leaf level.

Fan-out: Number of child pointers supported by an internal index node.

Hash index: Index that maps keys to buckets through a hash function.

Bitmap index: Bit-vector representation of row membership by value or category.

Covering index: Index containing all data needed by a query.

Inverted index: Mapping from terms to documents or row identifiers.

Cardinality: Number of tuples in a relation or result.

Selectivity: Fraction of rows satisfying a predicate.

Pipelining: Passing operator output directly to a consuming operator.

Materialization: Storing an intermediate result before further processing.

Hash join: Equality join based on hash-partitioned inputs.

Cost model: Estimator of resource consumption for a candidate plan.

Cardinality estimation: Prediction of result size used by optimization.

Latch: Short-duration protection for physical in-memory structures.

Review Questions

Short Answer Questions

1. Why does a slotted-page layout help with variable-length records?

2. Distinguish a latch from a transactional lock.

3. State one major strength and one limitation of a B+-tree.

4. Why are bitmap-index update costs representation-dependent?

5. What is the difference between pipelining and materialization?

Long Answer Questions

1. Compare row-oriented and column-oriented storage for an operational retail system and an analytical warehouse.

2. Explain B+-tree search, insertion, splitting, composite-key behavior, and concurrency considerations.

3. Describe the stages through which SQL is transformed into an executable physical plan.

4. Compare block nested-loop, index nested-loop, hash, and sort-merge joins.

5. Explain why cardinality estimation errors can produce poor plans and how storage-aware calibration can reduce them.

Analytical / Application Questions

1. A query filters a large fact table by date and groups by two low-cardinality attributes. Recommend a physical organization and access methods, and justify the choice in terms of compression, predicate pushdown, and maintenance.

2. An index nested-loop join is unexpectedly slower than a hash join even though an index exists on the inner relation. Analyze at least four possible causes.

3. A reporting query spills during hash aggregation after a data-growth event. Propose a diagnostic and remediation plan involving statistics, cardinality estimation, memory, materialization, and indexing.

Multiple Choice Questions with Answers

Question 1

Which index structure is generally best suited to ordered range scans?

A. B+-tree

B. Hash index

C. Bloom filter

D. Unordered heap file

Correct Answer: A. B+-tree

Question 2

What is the principal purpose of a buffer pool?

A. To enforce SQL syntax

B. To cache database pages in memory

C. To replace transaction logging

D. To sort every relation permanently

Correct Answer: B. To cache database pages in memory

Question 3

Under the stated idealized assumptions, what is the approximate partitioned hash-join I/O cost for relations R and S?

A. B(R) + B(S)

B. 2(B(R) + B(S))

C. 3(B(R) + B(S))

D. B(R)B(S)

Correct Answer: C. 3(B(R) + B(S))

Question 4

Which workload most naturally favors a column store?

A. Frequent updates of complete individual records

B. Analytical scans reading a few columns from many rows

C. Random equality lookups requiring every column

D. Highly contended single-row transactions

Correct Answer: B. Analytical scans reading a few columns from many rows

Question 5

Which statement about pipelining is correct?

A. It always eliminates blocking operators

B. It passes operator output directly to a parent when possible

C. It always requires writing intermediate results to disk

D. It is identical to materialization

Correct Answer: B. It passes operator output directly to a parent when possible

Question 6

A hash index is usually least suitable for which operation?

A. Equality lookup

B. Exact key matching

C. Ordered range retrieval

D. Bucket-based key access

Correct Answer: C. Ordered range retrieval

Question 7

For an index on (A, B, C), which predicate is generally most aligned with the leading-key principle?

A. B = 7 only

B. C = 9 only

C. A = 3 AND B = 7

D. C > 4 only

Correct Answer: C. A = 3 AND B = 7

Question 8

Which factor can make an index nested-loop join expensive despite the existence of an index?

A. Highly clustered inner matches

B. Very small outer input

C. Many random base-table accesses from an unclustered index

D. A selective outer predicate

Correct Answer: C. Many random base-table accesses from an unclustered index

Question 9

A bitmap index's update cost depends especially on which combination?

A. Only SQL keyword length

B. Bitmap representation, compression, and row-identifier stability

C. Only the number of database users

D. Whether the table has a primary key, regardless of representation

Correct Answer: B. Bitmap representation, compression, and row-identifier stability

Question 10

A plan has a fixed startup cost of 500 units and performs ceil(500/100) batches, each costing 2,000 units. What is the total cost?

A. 10,500 units

B. 10,000 units

C. 11,500 units

D. 1,500 units

Correct Answer: A. 10,500 units