Specialized access paths — extended reference

This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.

Part 2: Representing and locating data

Prerequisites: Lesson 11 and the preceding foundations.

Learning outcomes

Explain the access patterns served by columnar, inverted, time-series, spatial, and vector indexes.
Separate candidate generation from exact filtering or reranking.
Evaluate specialized indexes using update cost, recall or precision, pruning effectiveness, and retained state.

One query language can hide several different search problems

An application asks for one order by identifier, all documents containing two words, nearby delivery drivers, and the ten vectors closest to a query embedding. All four requests can be expressed through database APIs, but they have different mathematical and physical structure. A general ordered index is useful for some and insufficient for others.

A specialized access path reduces the set of candidates the engine must inspect. It may exploit physical ordering, token membership, geometric bounds, compression, or approximate search. The engine must still apply residual predicates and preserve the result contract. “Uses an index” does not mean “reads exactly the final result and nothing else.”

Columnar access and analytical locality

A columnar representation groups values from one attribute across many records. A query computing average price by category may need only a few columns. Avoiding unrelated fields reduces bytes read and can improve compression and vectorized processing.

For an illustrative table with 100 equal-width columns, scanning three columns touches 3% of the uncompressed column payload. If the full table is 1 TB under those simplifying assumptions, selected column bytes are 30 GB. This does not imply a 33-fold end-to-end speedup: decompression, predicate evaluation, aggregation, metadata, and output remain, and actual columns rarely have equal width.

A sparse primary index or block-level summary can prune regions whose value ranges cannot match a predicate. This is different from a point index that identifies one row directly. Data order affects how useful pruning becomes. Randomly interleaved values may make every block’s range broad, while ordered values create selective block boundaries.

Frequent small updates create another tradeoff. Immutable columnar blocks can favor batched ingestion and later merging. Maintaining a current point-updated view may require additional representations or version handling. Analytical throughput and transactional mutation latency therefore benefit from different physical assumptions.

Inverted indexes and full-text search

An inverted index maps a term to a posting list of matching document identifiers and possibly positions or frequencies. A query for documents containing both “database” and “latency” can intersect their posting lists. A phrase query also needs positional relationships. Ranking may use statistics rather than returning every match in arbitrary order.

Tokenization defines what a term means. Case folding, stemming, language rules, punctuation, and Unicode handling affect both indexing and query interpretation. A tokenizer change can require rebuilding or versioning the index. Search semantics are therefore part of the data model, not merely an implementation optimization.

Posting lists often use compressed sorted identifiers. Intersections can exploit ordering and skip information. A rare term can greatly reduce candidates before processing a common term. Updates and deletions require the index to stop returning documents that are no longer visible, or to recheck candidates against authoritative state.

A search index can lag behind transactional writes if maintained asynchronously. That may be acceptable for discovery but not for enforcing a uniqueness or ownership invariant. The application should distinguish “search may not show it yet” from “the transaction did not commit.”

Time-series organization

Time-series workloads commonly append observations identified by time and a series key such as a device or metric. Queries may scan a time range for selected series, aggregate into windows, and discard old data under retention policies.

Partitioning by time can make retention efficient by dropping entire old partitions. It can also concentrate all new writes in the current partition. Including a series or hash dimension can spread ingestion while complicating global time-range reads. Late-arriving observations require rules for modifying older partitions or creating correction records.

Compression often benefits from related timestamps and slowly changing values. Delta and delta-of-delta encodings can exploit those patterns. A highly irregular event stream or wide sparse attributes may behave differently. A time-series label does not guarantee that every dataset compresses well.

Retention and downsampling change information. Replacing per-second observations with per-minute averages prevents some later analyses and can hide short spikes. The engine or application must preserve the intended aggregate semantics, including counts, missing observations, and boundaries. Averaging averages without weights can produce an incorrect global result.

Spatial indexes and conservative candidates

Spatial predicates include point containment, intersection, distance, and nearest-neighbor queries. An index can organize bounding boxes, hierarchical cells, or another geometric approximation. It commonly returns candidates that require an exact geometric check.

A bounding rectangle may overlap a query even when the represented shape does not. Such false positives are acceptable if residual checking removes them. False negatives are not acceptable for an exact query. The index’s approximation must therefore be conservative with respect to the promised predicate.

Coordinate systems matter. Euclidean distance over raw latitude and longitude is not a universal measure of real-world distance. Dateline crossing, poles, projection, and precision affect results. An engine integration needs explicit units and geometry semantics. A fast algorithm over the wrong coordinate interpretation is still incorrect.

Updates can be expensive when moving objects cross spatial partitions or alter bounding structures. A realtime world with many moving entities may prefer coarse cells plus exact local checks over a sophisticated structure whose maintenance dominates. The chosen granularity trades candidate count against update work and subscription churn.

Vector similarity and approximation

Vector search ranks candidates by a distance or similarity function over numeric embeddings. Exact search compares the query with every relevant vector or uses a structure that preserves exact results under its assumptions. Approximate nearest-neighbor methods trade exhaustive work for a probability of finding sufficiently good candidates.

Recall measures how many true neighbors are recovered under a defined reference set and query. It must be evaluated alongside latency, memory, build time, update cost, and filtering. A result that is fast but misses required matches may not satisfy the product contract. Conversely, an approximate result can be entirely appropriate for recommendations or semantic discovery.

Filtering complicates approximate retrieval. If an index first finds candidates globally and then removes those outside the tenant or category, too few results may remain. Increasing candidate search can improve recall while spending more work. Building separate indexes improves locality or isolation while increasing management overhead and reducing sharing.

The pgvector project documents exact and approximate index options within PostgreSQL. It is a useful example of a specialized access method integrated with a broader transactional system. The presence of vector search does not make every filtered nearest-neighbor query equally cheap or remove the need to measure recall against the intended workload.

Combining access paths

A query can combine several restrictions: tenant, time, text, geometry, and similarity. One index may narrow candidates for another, or the optimizer may choose one primary path and recheck the rest. Intersecting candidate sets can help, but materializing and combining them also consumes resources.

A cost model should estimate candidate cardinality at each stage. Suppose a tenant filter leaves 1% of ten million records, or 100,000 candidates. A text restriction leaves 1% of that subset, or 1,000 candidates under the stated conditional selectivity. Applying the tenant restriction first can matter greatly, but only if the physical structure supports doing so efficiently.

Selectivity assumptions can be wrong when predicates are correlated. A term used almost exclusively by one tenant has different conditional behavior from an independently distributed term. Specialized indexes still depend on realistic statistics and query shapes. Lesson 16 returns to this problem in cost-based planning.

Maintenance and operational boundaries

Every access path has a construction and maintenance lifecycle. Building it can consume memory, I/O, and CPU. Updating it can add transaction work. Rebuilding after an encoding or schema change can interfere with foreground traffic. Replication and backup need a policy for reproducing or restoring it.

Some indexes are authoritative structures needed to recover data; others can be rebuilt from base records. Rebuildability changes backup and failure strategy, but rebuild time can still exceed an application’s recovery objective. An index that takes twelve hours to reconstruct may need its own preserved state even if it is logically derived.

Security filters must be applied consistently across candidate generation and result delivery. A shared approximate index must not leak another tenant’s identifiers or values through results, timing-sensitive diagnostics, or cached output. Resource limits are also a security concern when an authorized query can trigger an unbounded scan.

Candidate generation and exact checking form one contract

A specialized index commonly answers a weaker question than the full query. A block minimum and maximum answer “could this block contain a matching value?” An inverted list answers “which documents contain this token under this tokenizer?” A geometric box answers “which shapes might overlap?” The executor then evaluates remaining predicates. Correctness comes from the composition: candidate generation must not omit a required answer, and residual checking must remove invalid candidates.

This distinction explains why an index can be useful despite many false positives. Suppose a spatial index reduces ten million objects to 20,000 boxes, and exact geometry checks reduce those to 500 true matches. The index eliminated 99.8% of the original objects even though only 2.5% of its candidates were final matches. Reporting candidate precision alone would understate its benefit. The total cost includes index traversal, candidate materialization, and 20,000 exact checks.

Approximate nearest-neighbor search has a different contract because candidate generation may intentionally omit some true neighbors. Exact residual distance computation cannot recover a neighbor never generated. “Rechecked exactly” therefore does not turn approximate candidate search into an exact global top-k result. The guarantee must be stated at the level of the complete pipeline.

A worked inverted-list intersection

Assume token A occurs in documents [2, 5, 9, 20, 31] and token B in [1, 5, 8, 20, 40]. A merge intersection advances the lower current identifier until they match, producing [5, 20]. Because the lists are sorted, each iterator only moves forward. Its work is proportional to the visited list lengths rather than the size of the document collection.

while A and B have entries:
    if A.id == B.id:
        emit A.id
        advance A and B
    else if A.id < B.id:
        advance A toward B.id
    else:
        advance B toward A.id

The pseudocode abstracts skip blocks and compression. A rare term can act as a driver, probing a much larger common-term list near its candidate identifiers. Position lists extend the representation for phrase matching. If A occurs at position 7 and B at position 8 in one document, a two-token phrase can match; the same document containing both tokens far apart does not satisfy that phrase.

Deletion and authorization remain necessary after intersection. A document identifier can survive briefly in an asynchronously maintained index after its source row changes. The query must honor the promised visibility contract. A search result that reveals a forbidden document title before a later permission check is already an information leak. Efficient candidate generation cannot move authorization after observable output.

Ordering makes block summaries effective

Suppose each block stores 10,000 event rows and its timestamp minimum and maximum. With chronological clustering, a one-hour query can eliminate blocks covering unrelated days. With timestamps randomly distributed across all blocks, each block may span nearly the full retained period, so the same summary eliminates little. Identical summary metadata can have radically different value because of physical order.

A block summary is conservative: if the requested timestamp is outside its range, the block cannot match. If it lies inside, the block may contain no exact match and still must be considered. Multiple summaries, such as tenant and time, can help, but correlations matter. Independent minima and maxima do not necessarily describe which attribute combinations coexist in a row.

For a constructed 1 TB table where a query needs three equal-width columns out of one hundred, raw projected bytes are 30 GB. If block pruning then eliminates 90% of those projected blocks, candidate column bytes fall to about 3 GB. This multiplication assumes pruning applies uniformly to the selected data and ignores metadata, compression, and output. The two optimizations attack different dimensions: columns reduce width, pruning reduces regions.

Data ordering has a write-side cost. Maintaining global order can require buffering and merging or expensive insertion. Partitioned ordering relaxes the requirement to a file or segment. Queries then combine ordered runs and may sort or merge intermediate output. The engine chooses a useful compromise between ingestion, compression, pruning, and ordering work.

Time windows require mathematically valid summaries

Suppose minute A contains ten requests averaging 100 milliseconds, and minute B contains one thousand requests averaging 10 milliseconds. Averaging the two averages gives 55 milliseconds. The actual combined mean is (10 × 100 + 1000 × 10) / 1010, approximately 10.89 milliseconds. A downsampled representation needs both sum and count to combine means correctly.

Percentiles are more demanding: two p99 values do not reconstruct the p99 of their combined observations. A mergeable distribution summary can support an approximation with a stated error, while storing only percentiles generally loses the necessary information. Downsampling is therefore a change in what questions remain answerable. Its schema should preserve sufficient statistics for required aggregates.

Window boundaries also need explicit semantics. Does a sample at exactly 12:01 belong to the previous or next minute? A half-open convention such as [start, end) avoids double counting across adjacent windows. Event time and ingestion time differ when observations arrive late. A system must decide whether to revise historical windows, retain correction streams, or stop accepting changes after a defined horizon.

Retention can exploit time partitions, but deleting a partition must respect references, replicas, and recovery requirements. A dashboard that tolerates approximate rollups may still require raw events for fraud analysis or audit. One storage-saving policy should not silently remove data needed by another contract.

Spatial cells trade update churn against candidate count

A simple world can divide space into square cells and index entities by cell identifier. A nearby-entity query reads intersecting cells and checks exact distances. If cells are large, each query examines many irrelevant entities. If cells are tiny, moving objects cross boundaries frequently and subscriptions must add and remove membership more often. The best size follows entity density, movement speed, query radius, and update rate.

Assume a constructed square world with uniform density of one entity per 100 square meters. A 100-by-100-meter cell contains about 100 entities on average. Reading nine cells around a location yields roughly 900 candidates before distance checks. Real worlds often have crowds and empty regions, so average density alone is inadequate. A marketplace cell can dominate while most cells remain cheap.

A spatial tree can adapt to uneven geometry but introduces structural maintenance. A fixed grid has simpler keys and routing but may need subdivision or special handling for hotspots. Neither structure guarantees low latency if every client in a crowd needs updates about every other entity. Interest policy and presentation requirements determine whether aggregation, limited visibility, or other semantics are acceptable.

Geographic data requires an appropriate coordinate reference system and distance model. A game world with planar coordinates differs from a service measuring kilometers over Earth. Treating longitude differences as uniform meters introduces location-dependent error. The algorithm’s units and geometry assumptions belong in its interface.

Recall must be evaluated after filters

Assume an exact reference top ten exists for each query within one tenant. An approximate global index retrieves fifty candidates, after which tenant authorization leaves only three. Returning those three is not evidence that only three suitable tenant results exist. The index may have spent its candidate budget on other tenants. Increasing global candidates or applying filter-aware search can improve results, with additional cost.

A recall evaluation should use the final authorized search space and the same distance function as the product. If eight of the true top ten appear, recall at ten is 0.8 for that query under the defined reference. Ties, duplicate vectors, and insufficient eligible records need explicit evaluation conventions. Aggregate recall can hide poor behavior for small tenants or unusual query categories, just as average latency can hide tails.

Distance choice matters. Euclidean distance, inner product, and cosine similarity rank vectors differently unless transformations and normalization make them equivalent under stated assumptions. A convenient index must support the intended metric, or the application must justify a transformation. An embedding change can require rebuilding indexes and re-evaluating retrieval quality even when vector dimensionality stays constant.

Building several indexes creates a coordination problem

A transaction inserts a document that is represented in a base table, an inverted index, a time index, and a vector index. If all structures participate in one transaction, foreground work and memory pressure increase. If some update asynchronously, the system needs a durable stream, replay identity, visibility expectations, and monitoring for lag or stalled consumers.

A useful distinction is whether an index is used to discover candidates or authorize state changes. Search lag can be acceptable when a new document appears a few seconds late. A lagging access path should not independently decide whether a unique item can be sold again. The authoritative transaction must consult state meeting its correctness contract.

Rebuilds need an explicit cutover. An index built from a snapshot must incorporate later accepted changes before taking over. A dual-query period can compare results, but approximate search naturally varies, so validation needs appropriate metrics rather than exact equality. Rebuilding can also double resource use temporarily. The operational plan must reserve space, memory, and write capacity for coexistence.

Case synthesis: query shape chooses the physical advantage

The documented presence of columnar processing, specialized PostgreSQL index types, and pgvector options establishes that different candidate mechanisms coexist in modern systems. Their suitability follows the shape of the question. ClickHouse architecture, PostgreSQL index types, pgvector documentation

A point ownership lookup benefits from exact keyed access and transaction visibility. A billion-row aggregate benefits from narrow column scans, compression, and efficient aggregation. A nearby-player feed benefits from spatial candidate reduction and bounded delivery. A semantic search benefits from a justified quality/latency tradeoff. Combining these capabilities is possible, but it does not erase their different maintenance costs or guarantees. An engine designer should identify the dominant operation before selecting the specialized structure.

Draw the candidate pipeline before naming an index

query and trusted visibility scope
        |
choose access path and candidate budget
        |
index / block summary / approximate search
        |
candidate identifiers and necessary metadata
        |
exact predicates, authorization, distance or ranking checks
        |
ordered or aggregated result under stated guarantee

The diagram shows responsibilities rather than requiring authorization to occur only once. A system can push trusted filters into candidate generation and still verify them at delivery. Early filtering can save work and reduce leakage risk; final enforcement preserves the boundary when derived indexes lag or policies change.

For an exact spatial query, conservative boxes can overselect while exact geometry removes false positives. For an approximate vector query, exact reranking improves order among retrieved candidates but cannot restore omitted neighbors. For a columnar query, block summaries eliminate impossible blocks while row predicates validate actual values. The same pipeline vocabulary makes these different structures comparable without pretending they offer identical completeness or cost.

Case interpretation and design conclusion

ClickHouse’s architecture provides a concrete analytical comparison: column-oriented execution emphasizes efficient processing over substantial datasets. PostgreSQL exposes multiple index families, while pgvector adds specialized vector access. These examples illustrate different candidate-reduction strategies rather than a universal hierarchy of engines.

Choose an access path by predicate semantics, update pattern, result guarantees, and resource budget. Specify what is exact, what is approximate, what needs residual checking, and how the structure is maintained. The next part follows how a query planner turns these available mechanisms into an executable plan.

Sources and further reading

Course index · Lesson plan