Selection and Projection Evaluation

A selection `σ_θ(r)` returns the tuples of relation `r` that satisfy predicate `θ`. A projection `π_{A1,...,Ak}(r)` returns tuples restricted to attributes `A1,...,Ak`. In pure relational algebra, projection is a set operation, so if two output tuples become identical after dropping attributes, only one copy is kept — this is duplicate elimination. Most SQL engines default to bag (multiset) semantics and skip deduplication unless `DISTINCT` is specified, but the algorithms for doing so when required are identical either way, so we treat it as a first-class part of projection evaluation. The key architectural fact is that these two operators can be evaluated in a single pass over the data, one tuple at a time, without materializing intermediate relations — except for the deduplication step of projection, which needs to compare tuples against each other and therefore needs either sorting or hashing (unless the projected attributes include a key, in which case no duplicates can arise and the extra step is skippable entirely). Evaluation strategies fall into two families, distinguished by access path:

• File scan (linear/table scan): read every block of the relation sequentially, test the predicate tuple-by-tuple. This works for any predicate and requires no auxiliary structure.
• Index scan: use a B+-tree or hash index on some attribute(s) to retrieve only tuples (or a superset of tuples) that could possibly satisfy the predicate, via the index's search key. This is only applicable when the predicate is compatible with an existing index — e.g., an equality or range condition on the indexed attribute(s).

The choice between these, and among several index-scan variants, is normally made by a query optimizer using cost estimates (developed further in Cost Estimation for Query Plans), but the algorithms themselves — the actual mechanics of retrieving tuples — are what this article specifies.

Selection algorithms

We classify selection algorithms by the form of the predicate and the access path used.

A1 — Linear scan. Read each block of `r` into memory, test every tuple against `θ`, emit matches. Always applicable; the baseline against which every other strategy is measured.

A2 — Binary search (file scan on sorted file). If `r` is physically sorted on the attribute in an equality condition `A = v`, binary search locates the first qualifying block in `O(log₂ b)` block accesses (`b` = number of blocks), then a linear scan forward/backward retrieves all matches (since matches are contiguous in a sorted file).

A3 — Primary index, equality on key. If `A` is a candidate key with a primary (clustering) B+-tree index, a single index lookup returns at most one matching tuple. Cost: index height `h` (traversal) + 1 (fetch the record).

A4 — Primary index, equality on non-key (clustering index). If the file is sorted on `A` and `A` is not a key, matching tuples are stored contiguously; the index locates the first one, and the rest are read via sequential block access until the predicate fails.

A5 — Secondary index (or non-clustering index), equality. The index is traversed to find matching entries; each entry gives a record pointer, and the record is fetched with a separate I/O — one per matching tuple, since matches need not be contiguous on disk. This can be expensive for high-selectivity predicates (many matches) because of the "one random I/O per tuple" cost.

A6 — Primary index, comparison (`A ≥ v` or `A ≤ v`). For `A ≥ v`: locate the first entry `≥ v` via the index, then scan sequentially to the end of the file (or to where the sort order breaks the condition). For `A ≤ v`: scan sequentially from the beginning of the file up to the point found via the index.

A7 — Secondary index, comparison. Symmetric to A6 but each qualifying entry costs a separate record fetch — often more expensive than a full linear scan when the range is wide, because random I/O per tuple dominates sequential block reads. For conjunctive selections `θ = θ1 ∧ θ2 ∧ ... ∧ θn`:

• A8 — Use one index, filter the rest in memory. Pick the single most selective `θi` with a usable index (via A2–A7), retrieve candidate tuples, and test the remaining conjuncts on each candidate in memory before emitting.
• A9 — Use a composite index. If an index exists on the combination of attributes appearing in a conjunction (e.g., a composite B+-tree on `(A, B)`), a single index scan directly retrieves exactly the tuples satisfying both conditions (for equality conjuncts), avoiding any in-memory filtering.
• A10 — Intersection of record pointers. If separate indices exist on `A` and `B`, retrieve the sets of record pointers satisfying `θ1` and `θ2` independently (without fetching the actual records), intersect the pointer sets, then fetch only the tuples in the intersection. This is efficient when both indexes are highly selective, since it avoids fetching non-qualifying records at all.

For disjunctive selections `θ = θ1 ∨ θ2 ∨ ... ∨ θn`:

• A11 — Union of record pointers. If every `θi` has an applicable index, retrieve record pointers for each disjunct, take the union, eliminating duplicate pointers, then fetch the union's tuples.
• A12 — Linear scan fallback. If even one disjunct lacks a usable index, the entire disjunction generally requires a full linear scan, since any tuple in the file could satisfy that one un-indexed disjunct.

Projection algorithm

Projection without duplicate elimination is a trivial single pass: for each tuple, output the restricted-attribute tuple. Projection with duplicate elimination needs to detect equal output tuples, which requires bringing equal tuples together — done via sorting or hashing. ``` PSEUDOCODE — Projection with duplicate elimination (external sort-based) function PROJECT_DISTINCT(relation r, attribute-list L, memory buffer of M pages): // Phase 0: projection pass for each block b of r: for each tuple t in b: t' = restrict t to attributes in L write t' to temporary file T // no dedup yet // Phase 1: create sorted runs (external merge sort, pass 0) runs = [] while T has unread pages: load up to M pages of T into memory sort the in-memory tuples on all attributes of L write sorted run to disk runs.append(run) // Phase 2: repeated (M-1)-way merge passes while len(runs) > 1: new_runs = [] for each group of up to (M-1) runs: merged = MERGE(group) // standard k-way merge new_runs.append(merged) runs = new_runs // Phase 3: final pass — merge remaining run(s) and drop adjacent duplicates result = empty output previous = NONE for each tuple t in final merged stream (in sorted order): if previous is NONE or t != previous: emit t previous = t return result ``` ``` PSEUDOCODE — Projection with duplicate elimination (hash-based) function PROJECT_DISTINCT_HASH(relation r, attribute-list L, memory buffer of M pages): // Partitioning phase: use a hash function h1 to split into (M-1) partitions partitions = [empty file for i in 1..(M-1)] for each tuple t in r: t' = restrict t to attributes in L i = h1(t') mod (M-1) append t' to partitions[i] result = empty output // Duplicate-elimination phase: process one partition at a time for each partition p in partitions: if p fits in memory (<= M-1 pages): build an in-memory hash table H using a second hash function h2 for each tuple t' in p: if t' not already in H: insert t' into H emit t' else: recursively apply PROJECT_DISTINCT_HASH to p with a new hash function return result ``` Both algorithms rely on a crucial fact: duplicates of the same projected tuple, after restriction to attributes `L`, are indistinguishable and must collide — either landing in the same sorted run position or the same hash partition/bucket — so a single local comparison (adjacent-tuple check after sorting, or hash-table lookup) suffices to catch every duplicate, no matter how far apart the original tuples were in the source file.

Let `b` = number of blocks of relation `r`, `n` = number of tuples, `h` = height of a B+-tree index, and `M` = number of buffer pages available.

Selection costs (in block transfers, ignoring seek-time constants which the standard cost model folds into a per-access cost):

Correctness of selection algorithms. Each algorithm's correctness reduces to an access-path soundness and completeness argument: the retrieval step must return a superset of qualifying tuples that is refined (if necessary) by an explicit filter, and it must never skip a block or leaf entry that could contain a qualifying tuple.

• For sorted-file / clustering-index strategies (A2, A4, A6), correctness relies on the sort-order invariant: since the file is physically ordered by `A`, all tuples with a given value of `A` are contiguous, and the boundary between "less than v" and "not less than v" is a single cut point locatable by binary search or index traversal. Once located, sequential scan in the correct direction is guaranteed to enumerate exactly the qualifying run and then correctly detect its end (predicate first fails).
• For B+-tree traversal (A3, A5), correctness follows from the B+-tree search invariant: at each internal node, the key ranges of children partition the domain, so following the unique child whose range contains `v` is guaranteed to reach the (unique) leaf that would contain an entry for `v`, if one exists.
• For intersection/union strategies (A10, A11), correctness is set-theoretic: `θ1 ∧ θ2` holds for tuple `t` iff `t`'s pointer is in both retrieved sets, and `θ1 ∨ θ2` holds iff it is in either — so intersecting or unioning record-pointer sets before fetching is exactly equivalent to filtering fetched tuples, but cheaper.

Projection costs.

• No duplicate elimination: `O(b)` I/O (single pass), `O(n)` time — a strict linear scan and restrict.
• Duplicate elimination via external sort: the classic external merge-sort cost applies. With `M` buffer pages, the number of merge passes after the initial run-generation pass is `⌈log_{M-1}(b/M)⌉`, giving total I/O cost

``` 2·b·(1 + ⌈log_{M-1}(b / M)⌉) ``` (each pass reads and writes all `b` blocks; the `+1` accounts for the initial run-formation pass). Comparison-based sorting of `n` tuples costs `O(n log n)` CPU time, matching the information-theoretic lower bound for comparison sorts.

• Duplicate elimination via hashing: expected cost is `O(b)` I/O for partitioning plus `O(b)` for the in-memory hash/dedup phase, i.e. linear, provided each partition fits in memory (recursive partitioning otherwise). Expected CPU time is `O(n)` under a reasonably uniform hash function; worst case (pathological hash collisions or highly skewed data) degrades toward `O(n²)`-like blowup if a partition never shrinks — analogous to hash join's known Achilles' heel.

Correctness of duplicate elimination. The sort-based method is correct because equal tuples are, by definition, identical in every attribute, so any total order places them adjacent after sorting; a single adjacent-pair comparison therefore suffices to detect all duplicates, including ones originally scattered across arbitrary, non-adjacent blocks of the source relation. The hash-based method is correct because any deterministic hash function `h1` applied to equal tuples produces the same hash value, guaranteeing that duplicates always land in the same partition (never split across partitions) — and within a partition, `h2` again guarantees duplicates map to the same bucket, so a hash-table membership check correctly identifies every duplicate without ever comparing tuples that are known ahead of time to differ.

Tradeoffs, stated honestly. Index scans win when selectivity is low (few matching tuples) — but a secondary (non-clustering) index scan can be more expensive than a full linear scan when many tuples qualify, because each match costs a full random I/O rather than sharing sequential block reads; optimizers must estimate selectivity accurately (see Cost Estimation for Query Plans) to avoid this trap. Sorting for duplicate elimination is robust and produces sorted output usable by later operators (e.g., merge join), but pays `O(n log n)`; hashing is asymptotically better on average but its worst case is uglier and it produces no useful ordering.

Consider relation `Employee(id, name, dept, salary)` with `n = 1,000,000` tuples stored in `b = 20,000` blocks (50 tuples/block), a primary key index on `id` (B+-tree, height `h = 3`), and a secondary B+-tree index on `dept` (height `h = 3`). Buffer memory available: `M = 202` pages.

Query 1: `σ_{dept = 'Sales'}(Employee)`, and Sales has 40,000 matching tuples (4% selectivity).

Here the linear scan (20,000) beats the secondary index scan (≈40,003) — a textbook illustration that a non-clustering index is not automatically the cheaper choice once selectivity climbs past a few percent. This is exactly why a cost-based optimizer must compare estimated costs rather than blindly preferring "any available index."

Query 2: `σ_{id = 482913}(Employee)` — an equality lookup on the primary key. Using A3 (primary index, key equality): cost = `h + 1 = 4` block accesses total. Compared to a linear scan's average `10,000` block accesses (halfway through the file, expected for equality on a key with early exit), the index is overwhelmingly cheaper — as expected, since selectivity here is `1/1,000,000`.

Query 3: `π_{dept}(Employee)` with `DISTINCT` — projecting onto `dept` alone and removing duplicates (there are only, say, 12 distinct departments among 1,000,000 rows). Trace of the hash-based algorithm with `M = 202`: 1. Partition phase: stream all 1,000,000 restricted tuples (each just a `dept` string) through `h1`, splitting into `M − 1 = 201` partitions. Since there are only 12 distinct values, `h1` maps all copies of a given department name to the same partition (by determinism), so at most 12 of the 201 partitions receive any tuples at all — the rest are empty. 2. Dedup phase: each non-empty partition, however many raw tuples it holds, contains very few distinct values (values from a subset of the 12 departments) and easily fits in memory; build an in-memory hash table keyed by `dept`, emit the first occurrence of each, skip later ones. 3. Result: 12 output tuples emitted, one per department. I/O cost: one full read of the base relation to project (`20,000` blocks, folded into the projection pass) plus one write and one read of the partitioned intermediate tuples (`≈ b' ` blocks, where `b'` is much smaller since only the `dept` attribute survives) — dramatically cheaper than sorting all 1,000,000 tuples, because the number of distinct values is tiny. This illustrates why hashing is attractive when the output cardinality after deduplication is low relative to the input.

Every commercial and open-source relational database — PostgreSQL, MySQL/InnoDB, Oracle, SQL Server, SQLite — implements exactly this family of scan operators as the leaves of its query execution plans; `EXPLAIN`/`EXPLAIN ANALYZE` output in these systems literally names strategies like "Seq Scan," "Index Scan," "Index Only Scan," and "Bitmap Index Scan" (a close relative of the record-pointer intersection/union strategies A10/A11). Columnar analytic engines (e.g., data-warehouse and OLAP systems) rely on efficient projection to select only needed columns, dramatically reducing I/O in wide tables. Search engines and information-retrieval systems use analogous "postings list" intersection/union techniques for boolean-query evaluation, mirroring A10/A11. Distributed data-processing frameworks that run SQL-like queries over huge datasets push these same filter-and-project operations down to the storage layer (predicate and projection pushdown) precisely because they are the cheapest place to discard irrelevant data, before any expensive join processing begins.

Ask the tutor: How does the query optimizer decide, at plan time, which of these selection strategies to actually use for a given query?