Data Intensive Systems: Lecture 3

Files, Pages, and Records

At the physical level a database is a file of records. This is where the access-methods and disk-space layers of the engine live: the DBMS creates and deletes files, inserts, deletes, and updates records, and reads them back through three access patterns.

• Point access. Retrieve one record by its identifier.
• Range access. Retrieve all records satisfying a condition.
• Scan. Read the entire file.

How fast each of these runs is decided entirely by how the data is laid out on disk. The physical design layer makes three choices: how records sit inside pages, how pages are arranged inside a file, and which indexes exist. The metadata recording these choices lives in the system catalog.

Storage hierarchy. A database is a set of files; a file is a set of fixed-size pages (blocks); a page stores several records; a record is a sequence of fields.

Every access path is ultimately a way of locating the right page, then the right slot inside it.

Records and Pages

Most databases use the N-ary storage model (NSM), or row store: each page holds many complete tuples, one per slot. To name a tuple the system uses a record identifier.

Record Identifier (RID). A tuple is addressed by its page id and slot number, written $\langle \text{page\_id}, \text{slot\_number} \rangle$. Some systems expose a logical identifier instead, but it still resolves to a page and a slot.

Once the page is found, the slot number points to the record inside it. Keeping that slot number stable across insertions, deletions, and reorganizations is the main goal of page design, because every index entry that names a record names its RID.

The first question a page format must answer is whether its records are fixed-length or variable-length, because that decides which slot layout is possible.

Fixed-length records. All fields have fixed size (integers, fixed char), so every record has the same length, the schema is stored once in the catalog, field $i$ begins at a fixed offset, and the page can use a compact slot layout. Two such layouts trade space against RID stability.

A packed page uses space perfectly but cannot delete without shifting; a bitmap page keeps positions fixed at the cost of one bit per slot. The moment a field is a varchar, or a single file mixes record types, neither fixed layout works.

Variable-length record. A record whose length depends on its data. A common layout places fixed-size values at the front, then one $\langle \text{offset}, \text{length} \rangle$ entry per variable field, then the variable data at the end, plus a small null bitmap for missing attributes.

Variable-length records can move within a page, so the RID can no longer be a raw byte offset. The standard answer is the slotted page, which separates the stable slot identity from the moving bytes.

Slotted page. The page header and a slot directory grow forward from the front; the records grow backward from the back; a free-space pointer marks the boundary. Each slot entry stores a record's location and size, so compaction can move the bytes without changing the slot number, leaving the RID intact.

The header holds the number of slot entries, the free-space pointer, and one location/size entry per record. Three operational issues remain. Record growth: enlarging a field may shift later records within the page. Page overflow: if the record no longer fits, it moves to another page, usually leaving a forwarding pointer at the old slot. Oversized records: some systems forbid records larger than a page, others spill large values to overflow storage.

Row Stores and Column Stores

Every layout so far is a row store: a slot holds one full tuple, so all of a tuple's attributes sit together. The alternative reorganizes data by attribute instead of by tuple.

Decomposition storage model (DSM). A column-oriented layout that stores each attribute separately. A tuple is rebuilt by reading the value at the same logical position from each needed column.

A row store answers "give me this tuple" cheaply; a column store answers "give me this attribute of every tuple".

The two models make opposite trade-offs. A row store gives fast inserts, updates, and deletes and reads or rewrites whole tuples cheaply, but a scan that needs a few of many attributes still pays I/O for all of them, and one page mixing many value types compresses poorly. A column store reads only the attributes a query touches, gains CPU cache locality, compresses each column far better, and processes values in vectorized batches; in return, reconstructing a full tuple is expensive, updates and deletes are harder, and compressed columns may need decompression first.

Row stores fit OLTP, many small transactions; column stores fit OLAP, analytical scans over few attributes; hybrid systems support both.

Pure column stores split attributes across the whole file. PAX keeps the file's page structure but applies the columnar idea inside each page.

Partition Attributes Across (PAX). Within one page, values of the same attribute are grouped into a contiguous column partition. The page still holds the same tuples as a row page; a tuple is rebuilt logically by taking the same offset in each partition.

This buys cache-friendly scans over a few attributes without abandoning the page-based design. Analytical file formats such as Parquet and ORC apply the same idea at file scale: they gather tuples into large row groups (or stripes) and store each group column by column.

Each column stream compresses well, the engine can skip irrelevant columns and often whole groups, and a scan over a few attributes never touches the rest of the file.

File Organizations and Their Cost

The next layer up is how pages are arranged inside a file. The choice is again driven by the workload: full scans and cheap inserts favor one organization, ordered reads favor another.

Heap file. An unordered organization: records sit in no particular search order. Records are scanned sequentially or reached directly by RID, an insert goes into any page with free space, and the DBMS tracks free space as pages are allocated and freed. It finds heap pages either through linked lists (a header page points to a list of free pages and a list of data pages) or through page directories (directory pages hold each data page's location and remaining free space).

Heap files are ideal when most queries scan the file, since no physical order is maintained. When queries instead read by key or by key range, ordering the file pays off.

Sorted (sequential) file. Records are kept in search-key order, where the search key is the set of attributes used to physically order the file (it need not be unique). Scanning in order is cheap, and a range query becomes efficient: after the first match the DBMS reads forward.

Order makes updates costly. Deletions use pointer chains or tombstones so later records need not move immediately. Insertions find the right position and, if the target page is full, divert to an overflow page and patch the chain. Overflow pages accumulate over time, so the file must occasionally be reorganized to restore physical order.

To compare the two, we measure cost in page I/Os.

Simplified I/O cost model. Cost is counted only in page I/Os. I/O is assumed to dominate CPU work, so buffering, prefetching, and similar effects are ignored, and only the average case is considered.

Let $B$ be the number of data pages. Each operation touches one record, an equality search returns one match, a heap insert appends at the end, and a sorted file searches on its ordering attribute and stays compacted after deletes.

Scans cost the same either way. Sorted files win decisively on equality and range search over the ordering attribute, dropping from a linear scan to a binary search $\log_2 B$. Heap files win on inserts (a constant append instead of shifting half the file) and usually on deletes. A sorted file thus buys one excellent access path at a steep update cost, which is exactly the problem indexes solve more flexibly.

Indexing

A sorted file is fast only for its single physical order. If a file is sorted on ID, lookups on ID are cheap, but a predicate on salary or dept_name still forces a scan. An index removes that restriction.

Index. An auxiliary access structure mapping search-key values to records or pages, letting the DBMS answer a selection with far fewer I/Os than a full scan. Several indexes can give the same relation several efficient entry points at once, while the data file keeps one physical order.

The search key need not be unique, any subset of attributes can serve as one, and every insert, delete, and update must also maintain the affected indexes. What an index speeds up is described by a predicate.

Index search condition. A predicate of the form $\langle \text{search key}, \text{comparison operator} \rangle$. dept_name = "CS" has search key dept_name and an equality operator; gpa > 3 has search key gpa and a greater-than operator. Equality asks for one exact value; the inequalities $<, \leq, >, \geq$ define ranges and so benefit most from ordered access paths.

Indexes are classified along four independent axes: clustered vs unclustered, dense vs sparse, key vs non-key search key, and whether the data file is ordered on the indexing field. The first axis is the one with the largest performance consequences.

Clustered vs unclustered. If the physical order of the data records follows the order of the index entries, the index is clustered; otherwise it is unclustered.

A clustered index keeps matching records on nearby pages, so range queries stay efficient; an unclustered index may jump to many unrelated pages, so large result sets become expensive. A file can carry many unclustered indexes but only one clustered physical order at a time. In the clustered case, the file is ordered on ID, so neighbouring index entries point to neighbouring data pages.

The second axis is how completely the index covers the data.

Dense index. Has an index entry for every search-key value that appears in the data file.

Sparse index. Has entries for only some values, typically one per data page. A sparse index uses less space and needs fewer updates, but works well only when the data file is ordered on the search key, since after reaching the right page the DBMS still searches within it.

A dense index can answer "does K exist?" on its own; a sparse index must fetch the page to know.

For range predicates the clustered/unclustered distinction grows even larger: a clustered index costs roughly the number of data pages holding matches, while an unclustered index costs closer to the number of matching index entries, because each match may lead to a different page. So a clustered index is efficient for ranges and ordered scans but expensive to maintain when updates disturb the order, whereas an unclustered index is cheap to add as an extra access path but can trigger many random I/Os on a large result.

The shape of a dense index depends on whether its search key is a key. If the search key is a key, each value identifies one record, so a dense index has one entry per record, each pointing straight at a single RID.

If instead the file is sorted on a non-key attribute, equal values are adjacent, so a dense index keeps one entry per distinct value and points to the first record of that group.

A sparse index pushes this further by keeping one anchor entry per data page.

To locate a value $K$, find the index entry with the largest key $\leq K$, follow its pointer to that data page, and scan forward until $K$ is found or passed. Because the method relies on the file's sequential order, a sparse index is normally clustered.

When an index itself spans many pages, finding the right index page is its own search, solved by recursion.

Multilevel index. Treat the index file as a sorted file and build a sparse index on top of it, repeating until the top level is small enough to search cheaply. In a two-level design the inner index is the ordinary index on the data file and the outer index is a sparse index over the inner index's pages.

Search descends level by level to the target data page, and more levels can be added if the outer index also grows too large; the cost is that an insertion or deletion may need updates at several levels. When the indexing field is not the file's physical order, the index is necessarily unclustered, and a different structure is needed.

Secondary index. An index whose search key does not define the physical order of the data file, so it is unclustered. For a non-key search key it stores one entry per value, and each entry points to a bucket (or list) of RIDs holding all matching records.

A secondary index on an unsorted column must be dense; a sparse one would leave some matching records unreachable. This fixes the vocabulary: a clustered (primary) index sits on a file physically ordered on the indexing field and may be sparse or dense, while an unclustered (secondary) index sits on a file that is not so ordered, points to records or RID buckets, and must be dense. The core question is always whether the data file itself follows the search-key order.

Tree and Hash Index Structures

Sequential dense and sparse indexes explain the ideas, but a static index degrades under updates. Real systems prefer the B+-tree because it stays balanced.

B+-tree. A balanced search tree whose nodes are page-sized blocks: every root-to-leaf path has the same length, internal nodes store separator keys and child pointers that route a search, and leaf nodes store the sorted entries, linked left-to-right for range scans. The node capacity (the tree's order) controls fan-out, and fan-out controls height.

A small order gives limited fan-out, so the tree grows wide and deep quickly; a larger order packs more keys and pointers per node and indexes the same data with fewer levels, which is why disk-based trees aim for high fan-out. In both, leaves are linked in sorted order, so once the first matching leaf is found a range scan continues sequentially.

The B+-tree is one of two index families, each tuned to a different predicate. A hash index optimizes the other.

Hash-based index. Applies a hash function $h$ to the search key to pick a bucket. Each bucket has one primary page and may grow overflow pages as collisions accumulate.

Hash indexes are best for equality predicates: to evaluate age = 44 the DBMS computes $h(44)$ and reads one bucket, duplicates land in the same bucket, and inserts and deletes usually touch one bucket only. Because entries are not kept in order, hash indexes do not help range predicates such as age > 40: the DBMS would have to inspect nearly every bucket, which is close to a full scan.

A tree-based index, in practice a B+-tree, keeps entries sorted, so its leaf links turn a range predicate into one descent plus a sequential walk, and the same structure also serves equality, ordered scans, and prefix lookups.

Hashing trades away order for $O(1)$ equality; trees keep order and answer everything else.

This makes the index family follow directly from the predicate. For

SELECT E.dno
FROM Employees E
WHERE E.age > 40

age > 40 is a range, so a tree index on age is the natural choice and a hash index would not help. If many tuples qualify, a clustered tree index beats an unclustered one; and if the predicate matches a large fraction of the relation, a plain sequential scan may still be cheaper than any index.

Selective predicate. A predicate matching a small fraction of the relation. Indexes help most here; when most records qualify, scanning is often cheaper.

Composite Search Keys

When several predicates apply, the question becomes which attribute, and in what combination, the index should cover. Consider

SELECT sid
FROM Student
WHERE sname = 'Mary'
  AND gpa > 3.9

An index on sname helps the equality sname = 'Mary' (a hash index suffices if such lookups dominate); an index on gpa helps the range gpa > 3.9 (this must be a tree index); but an index on the pair $\langle \texttt{sname}, \texttt{gpa} \rangle$ is usually best, narrowing to Mary first and then scanning only the qualifying GPAs inside that group.

Composite search key. An index whose search key is a tuple of attributes. In a tree index entries follow lexicographic order: sorted first by the leading attribute, then, among equal values, by the next.

Field order is decisive. With age = 12 AND sal = 75, full equality, both a hash and a tree index on $\langle \texttt{age}, \texttt{sal} \rangle$ work. With only age = 12, prefix equality, the tree index still works because equal-age entries are adjacent, but the hash index on the full pair does not. With age = 12 AND sal > 20, the tree index on $\langle \texttt{age}, \texttt{sal} \rangle$ is ideal, while $\langle \texttt{sal}, \texttt{age} \rangle$ is much weaker. This is the general rule.

Leftmost-prefix rule. A composite tree index on $\langle A, B, C \rangle$ can be used efficiently only when the query constrains a prefix of the key: $A$, or $A$ and $B$, or all three.

A composite index is a phone book sorted by last name, then first name: perfect for "Smith" and for "Smith, John", useless for "everyone named John".

A well-ordered composite key can also let the index answer the query by itself.

SELECT AVG(E.sal)
FROM Employees E
WHERE E.age = 25
  AND E.sal BETWEEN 3000 AND 5000

BETWEEN is a range, so this needs a tree index, and the order $\langle \texttt{age}, \texttt{sal} \rangle$ is right: it fixes one age, then scans only the salary interval inside that age group, whereas $\langle \texttt{sal}, \texttt{age} \rangle$ would scan the salary interval for every age and then filter. Since the query reads only sal, which is already in the key, the index alone suffices.

Index-only evaluation (covering index). If every attribute the query needs is already in the index entries, the DBMS answers from the index alone, never fetching the data records. This is especially effective for aggregates such as AVG, COUNT, MIN, and MAX.

Choosing an Index

Putting the four axes together, the choice of index follows a short decision path keyed on table size, predicate shape, and update frequency.

1. Tiny or update-dominated table. With only a few hundred tuples, or with frequent updates and low-cost queries, use no index: a full scan is negligible and any index only adds write overhead.
2. No predicate, full scan, or whole-relation aggregation. Use a heap file: inserts are append-only and the query reads everything anyway.
3. Equality predicate. A hash index gives $O(1)$ lookup. If updates are infrequent, make it clustered and sparse (clustering packs matches together; sparse works because the data is sorted on the key); if updates are frequent, make it unclustered and dense to avoid maintaining physical order.
4. Range predicate. Use a B+-tree, since hashing destroys order. Again clustered and sparse for infrequent updates (the scan reads consecutive pages, sparse keeps the index small) and unclustered and dense for frequent updates.
5. Choosing the key. Index the attribute in the predicate; with several predicates, index the most selective one and apply the others as in-memory post-filters.
6. Sorted file vs B+-tree. For static data with range queries, a plain sorted file with binary search ($O(\log B)$) is enough; for dynamic data, prefer a B+-tree, since sorted files are costly to maintain under inserts and deletes.

Several traps recur in this decision.

Clustered ≠ primary key. Clustering means data pages are physically ordered on the indexed attribute, which may be non-unique (you can cluster on year). Only one clustered index per table, because physical order is a single global property.

Sparse requires clustering. A sparse index keeps one entry per data page and works only if the data is sorted on that key; an unclustered index must therefore be dense, or some matching records become unreachable.

Unclustered range can lose to a full scan. Each qualifying entry may point to a different page, so the cost is as many random I/Os as matches. Above roughly $5$-$10\%$ selectivity, a sequential scan usually wins.

Hash indexes do not support ranges. Hashing maps keys to buckets with no ordering, so year > 2010 probes nearly every bucket.

Sorted files support equality too. Binary search gives $O(\log B)$; "sorted = range only" is false. The hash advantage is $O(1)$ vs $O(\log B)$ for equality.

Inserts and deletes on a sorted file are expensive. An insert is at least $2$ I/Os and degrades to $O(B)$ when shifting; a worst-case delete on a non-sort attribute scans all $B$ pages and rewrites them, $2B$ I/Os. Prefer B+-trees for dynamic data.

PAX ≠ DSM. PAX reorganizes columns within a page, so the page count matches NSM; DSM decomposes into separate column files with different page counts.

System Catalogs

File organizations, indexes, and statistics are recorded in one place the optimizer can read.

System catalog. The DBMS's metadata repository, storing information about relations, attributes, indexes, views, constraints, statistics, and access control.

For each relation it keeps the name, backing file, file organization, attribute names and types, and integrity constraints; for each index, the name, structure (B+-tree, hash), search-key fields, and clustering status; for each view, its name and definition; and for the optimizer, statistics such as relation cardinality, page count, and average row length, plus authorization data. The catalog is itself stored as relations, so it can be queried like any table. Oracle, for example, exposes it through views such as USER_TABLES and USER_TAB_COLUMNS:

SELECT table_name, num_rows, blocks, avg_row_len
FROM user_tables

These views are exactly what the optimizer and storage manager consult: they describe the schema, give size estimates, and report which access paths already exist, closing the loop from physical layout back to query planning.