A database does two things: you give it data and it stores it; you ask for the data later and it gives it back. Chapter 2 was about the format in which you hand data over and ask for it. This chapter is about what the database does underneath to store it and find it again. You will probably never write your own storage engine, but you will pick one, tune it, and be asked in interviews why a write-heavy workload prefers RocksDB while a read-heavy one prefers InnoDB, so you need a working mental model of what happens on disk.

The chapter divides storage engines into two families: log-structured engines (Bitcask, LevelDB, RocksDB, Cassandra, HBase, Lucene) that only ever append to files and clean up later, and page-oriented engines (B-trees, used by almost every relational database and many non-relational ones) that update fixed-size pages in place. It then widens the lens from transaction processing to analytics, where a completely different layout, column-oriented storage, wins.

In one minute

• The simplest database is an append-only log. Appending is fast; finding a key means scanning everything. Every index is extra structure that speeds up reads at the cost of slowing writes, which is why databases make you choose indexes.
• A hash index (Bitcask) keeps every key's byte offset in RAM, writes to append-only segments, and reclaims space by compaction (keeping only the latest value per key). It needs all keys in memory and cannot do range queries.
• SSTables are segments sorted by key. Sorting lets you merge segments like mergesort, keep a sparse in-memory index, and compress blocks. Writes go to an in-memory balanced tree (memtable) plus a write-ahead log, and are flushed as SSTables. This is the LSM-tree.
• LSM reads can touch several segments; Bloom filters make non-existent keys cheap. Size-tiered and leveled compaction are the two ways to merge.
• B-trees split the database into fixed-size pages (commonly 4 KB), keep keys sorted in a balanced tree with a high branching factor, and update pages in place. Crash safety comes from a write-ahead log (WAL), or from copy-on-write (LMDB); concurrency from latches.
• LSM-trees generally offer higher write throughput and better compression; B-trees give more predictable latency and simpler transactional locking because each key lives in exactly one place. Write amplification is the metric at the center of the comparison.
• Other indexes: secondary (non-unique), clustered versus heap-file versus covering, concatenated multi-column, R-trees for spatial data, full-text and fuzzy indexes, and in-memory stores (Redis, VoltDB) whose speed comes from avoiding on-disk encoding, not from avoiding disk reads.
• OLTP workloads touch few rows per query with random access; OLAP queries scan millions of rows and aggregate a few columns. Data warehouses use star schemas and column-oriented storage with bitmap and run-length compression, vectorized execution, multiple sort orders and materialized aggregates (data cubes).

The simplest database and the cost of indexes

An append-only log

Two shell functions make a working key-value store:

db_set () {
  echo "$1,$2" >> database
}

db_get () {
  grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

db_set appends a line to a file, which is close to the fastest write a storage engine can do. Old values are not overwritten; db_get takes the last occurrence, so updates work. Many real databases use the same idea internally, a log, meaning an append-only sequence of records (not to be confused with application log output).

db_get has terrible performance: it scans the whole file, O(n). To find a key efficiently you need an index, an additional structure derived from the primary data that acts as a signpost. Adding or removing an index does not change the data, only query performance. The universal trade-off: well-chosen indexes speed up reads, but every index slows down writes, because the index must be updated on every write. This is why databases do not index everything by default and leave the choice to the developer.

Hash indexes

Bitcask's design

The simplest index for a key-value store is a hash map kept in memory. Map every key to the byte offset where its latest value lives in the data file. On write, append the record and update the offset in the map; on read, look up the offset, seek, read. This is essentially how Bitcask, the default storage engine in Riak, works. It offers high-performance reads and writes as long as all keys fit in RAM, and values can be larger than memory since they are loaded from disk with one seek (or from the filesystem cache with none). It suits workloads where each key is updated frequently, such as a view counter per video URL: many writes, not too many distinct keys.

Segments, compaction and merging

An append-only file eventually fills the disk. The fix is to break the log into segments of a certain size: when a segment reaches its limit, close it and start writing to a new one. Closed segments are then compacted: throw away duplicate keys in the log and keep only the most recent update for each key. Compaction makes segments smaller, so several segments can also be merged into one at the same time. Segments are never modified after being written, so the merged output goes to a new file. Merging and compaction happen in a background thread while reads and writes continue against the old segments; once done, read requests switch to the new merged segment and the old files are deleted.

Each segment has its own in-memory hash map. A lookup checks the most recent segment's map, then the next older one, and so on. Because merging keeps the segment count small, a lookup does not need to check many maps.

Details that matter in practice

• File format. CSV is a bad choice; use a binary format with a length prefix followed by the raw bytes, no escaping needed.
• Deletion. Append a special deletion record, a tombstone. During merging, a tombstone tells the merge process to discard all previous values for that key.
• Crash recovery. The in-memory hash maps are lost on restart. Rebuilding them by scanning every segment is slow for large segments; Bitcask stores a snapshot of each segment's hash map on disk so recovery is fast.
• Partially written records. A crash mid-append leaves a torn record. Checksums detect and skip such corrupted parts of the log.
• Concurrency. Writes are appended in strictly sequential order, so a common implementation uses a single writer thread. Segments are append-only and otherwise immutable, so they can be read concurrently by many threads.

Why append-only wins and where it loses

Append-only may look wasteful compared with updating in place, but it is a good design for several reasons. Appending and merging are sequential operations, far faster than random writes on spinning disks and still preferable on SSDs (the B-tree comparison later in this chapter explains why). Concurrency and crash recovery are much simpler if segments are immutable: you never have to worry about a crash while a value was half-overwritten. And merging old segments avoids the data file fragmenting over time.

The hash index has two hard limits. The hash table must fit in memory; an on-disk hash map performs poorly due to random I/O, is expensive to grow, and hash collisions need fiddly logic. And range queries are not efficient: to scan keys kitty00000 through kitty99999 you have to look up every key individually. The next structure fixes both.

SSTables and LSM-trees

Sorted String Tables

Make one change to the segment files: require that the sequence of key-value pairs is sorted by key, and that each key appears only once per merged segment (compaction already ensures this). This format is called a Sorted String Table (SSTable). The requirement seems to break append-only writing, since incoming writes arrive in any order, but it buys three advantages:

1. Merging segments is simple and efficient, even when files are bigger than memory. Use the mergesort approach: read the input files side by side, look at the first key in each, copy the lowest to the output, repeat. If the same key appears in several segments, keep the value from the most recent segment and discard the rest, because every segment contains all values written during a period of time.
2. You no longer need an index of all keys in memory. To find handiwork, you only need to know the offsets of handbag and handsome; jump to the handbag offset and scan forward. A sparse in-memory index with one key per few kilobytes of segment is enough, since a few kilobytes scan quickly.
3. Compression. Since a read request scans several key-value pairs in the requested range anyway, group those records into a block and compress it before writing to disk. Each sparse index entry then points at the start of a compressed block. Compression saves disk space and reduces I/O bandwidth.

Constructing and maintaining SSTables

Incoming writes are unsorted, so maintaining sorted order on disk is possible (B-trees do it) but easier in memory with a balanced tree such as a red-black tree or AVL tree, which lets you insert keys in any order and read them back sorted. The storage engine works like this:

• When a write comes in, add it to the in-memory balanced tree, called the memtable.
• When the memtable exceeds some threshold (typically a few megabytes), write it out to disk as an SSTable file. This is efficient because the tree already maintains sorted order. The new SSTable becomes the most recent segment while writes continue to a fresh memtable.
• To serve a read, first try the memtable, then the most recent on-disk segment, then the next older, and so on.
• From time to time, run merging and compaction in the background to combine segment files and discard overwritten or deleted values.

One problem: if the database crashes, the most recent writes in the memtable are lost. To avoid that, keep a separate log on disk to which every write is immediately appended, in write order (unsorted), whose only purpose is to restore the memtable after a crash. When the memtable is flushed to an SSTable, the corresponding log can be discarded.

Making an LSM-tree out of SSTables

This algorithm is what LevelDB and RocksDB use; both are key-value storage engine libraries designed to be embedded in other applications (RocksDB powers MySQL's MyRocks, CockroachDB's early versions, TiKV, Kafka Streams state stores and many more). Similar storage engines are used in Cassandra and HBase, both inspired by Google's Bigtable paper, which introduced the terms SSTable and memtable.

Originally the structure was described by Patrick O'Neil and colleagues as the Log-Structured Merge-Tree (LSM-tree), building on earlier work on log-structured filesystems. Storage engines based on this principle of merging and compacting sorted files are called LSM storage engines.

Lucene, the indexing engine for full-text search used by Elasticsearch and Solr, uses a similar method for its term dictionary. A full-text index maps a term (word) to the posting list of document IDs containing it; in Lucene this mapping is kept in SSTable-like sorted files, merged in the background as needed.

Performance optimizations

The LSM-tree algorithm can be slow when looking up keys that do not exist: you check the memtable, then every segment back to the oldest, possibly reading each from disk, before concluding the key is absent. Storage engines use a Bloom filter to fix this. A Bloom filter is a memory-efficient probabilistic data structure that approximates the contents of a set; it can tell you definitively that a key does not appear in a segment (no false negatives) with a small false-positive rate, saving many unnecessary disk reads. Each SSTable carries its own filter.

There are two main strategies for the order and timing of merging and compaction:

	Size-tiered compaction	Leveled compaction
How it works	Newer, smaller SSTables are successively merged into older, larger ones	The key range is split into smaller SSTables, and older data is moved into separate levels; each level is a non-overlapping sorted run of about 10x the size of the previous
Space overhead	Can temporarily need roughly double the space during a large merge	Low: a key appears in at most one SSTable per level
Read cost	Several overlapping SSTables may need checking	At most one SSTable per level per key, so bounded
Write amplification	Lower	Higher, since data is rewritten as it moves down levels
Used by	HBase; Cassandra (SizeTieredCompactionStrategy, the default)	LevelDB, RocksDB (default); Cassandra (LeveledCompactionStrategy)

Despite the complications, the basic idea of LSM-trees is simple and effective: keep a cascade of SSTables that are merged in the background. Even when the dataset is much bigger than memory it works well. Because data is stored in sorted order, range queries are efficient, and because the disk writes are sequential, LSM-trees support remarkably high write throughput.

B-trees

Pages and the balanced tree

The log-structured family is comparatively recent in production use. The most widely used indexing structure is the B-tree, introduced in 1970 and described as ubiquitous less than a decade later. B-trees remain the standard index implementation in almost all relational databases, and many non-relational databases use them too.

Like SSTables, B-trees keep key-value pairs sorted by key, which allows efficient key lookups and range queries. Otherwise the design philosophy is very different. Where log-structured indexes break the database into variable-size segments and write them sequentially, B-trees break the database into fixed-size blocks or pages, traditionally 4 KB (sometimes bigger; InnoDB uses 16 KB), and read or write one page at a time. This matches the underlying hardware, since disks are also arranged in fixed-size blocks.

Each page can be identified by an address or location, which lets one page refer to another, like a pointer but on disk. One page is designated the root; a lookup starts there. The page contains several keys and references to child pages, and each child is responsible for a continuous range of keys, with the keys between references indicating where the boundaries lie. Following references down the tree, you eventually reach a leaf page containing individual keys, which either contains the value inline or a reference to the page where the value lives.

The number of references to child pages in one page is the branching factor, typically several hundred in practice, determined by the space needed for page references and range boundaries. Because the tree is balanced, a B-tree with n keys always has depth O(log n). Most databases fit in a tree three or four levels deep: a four-level tree of 4 KB pages with a branching factor of 500 can store up to 256 TB.

Updates, inserts and splits

To update the value for an existing key, search for the leaf page containing that key, change the value in that page, and write the page back to disk. Any references to the page remain valid because it stays at the same location.

To add a new key, find the page whose range encompasses the new key and add it. If there is not enough free space, split the page into two half-full pages and update the parent page to account for the new subdivision of key ranges. Occasionally a split propagates up to the root, which is how the tree gains a level. This algorithm keeps the tree balanced.

The basic underlying write operation of a B-tree is thus overwriting a page on disk in place. On a magnetic disk this means moving the head, waiting for the platter, and overwriting the sector; on an SSD it is more complicated, since the drive must erase and rewrite large blocks of its storage chip at a time. Either way, it is a fundamentally different assumption from the log-structured family, which never modifies a file once written. Some operations require several pages to be overwritten: a split writes two new pages plus the parent. That is dangerous, because a crash after only some of those pages have been written leaves a corrupted index, for example an orphan page with no parent.

Making B-trees reliable

The standard remedy is a write-ahead log (WAL), also called a redo log: an append-only file to which every B-tree modification is written before it is applied to the pages of the tree itself. When the database recovers after a crash, this log restores the B-tree to a consistent state. (Note the irony: a page-oriented engine still needs a log, and the WAL doubles the write cost of every modification.)

Concurrency is the other complication. Multiple threads accessing the B-tree at once may see the tree in an inconsistent state mid-update. Databases protect the tree's internal structures with latches, lightweight locks held for the duration of a page operation. Log-structured approaches are simpler here: all merging happens in the background without interfering with incoming queries, and old segments are atomically swapped for new ones.

B-tree optimizations

Many variants have been developed over decades. The book mentions:

• Copy-on-write instead of a WAL. Some databases, such as LMDB, never overwrite pages. A modified page is written to a new location and a new version of the parent page is created pointing to it, up to a new root. This gives crash safety without a WAL and makes concurrency control simpler, because readers can keep using the old root while a writer builds a new one (Chapter 7 shows this is also useful for snapshot isolation).
• Key abbreviation. Interior pages do not need full keys, only enough of each key to act as a boundary between ranges. Packing more keys into a page increases the branching factor and reduces depth. This variant is sometimes called a B+ tree, though the term is also used for the convention that values live only in leaves.
• Sequential leaf layout. Many implementations try to lay out leaf pages in sequential order on disk so that range scans do not seek, but maintaining that order as the tree grows is difficult. LSM-trees get this for free, since merging rewrites large segments sequentially.
• Sibling pointers. Each leaf page may hold references to its left and right siblings, so a range scan can proceed without jumping back to parent pages.
• Fractal trees borrow log-structured ideas (buffering updates in interior nodes) to reduce disk seeks; they have nothing to do with fractals.

Comparing B-trees and LSM-trees

The rule of thumb is that LSM-trees are typically faster for writes while B-trees are thought to be faster for reads, because an LSM read has to check several structures and SSTables at different stages of compaction. Benchmarks are inconclusive and workload-sensitive, so you should test with your own workload, but the mechanisms behind the trade-offs are clear.

Advantages of LSM-trees

A B-tree index writes every piece of data at least twice: once to the WAL and once to the tree page itself (and again if a page splits), and it writes an entire page even if only a few bytes changed. Some engines overwrite the same page twice to avoid a torn page on power loss. Log-structured indexes also rewrite data multiple times due to repeated compaction and merging. This effect, one write to the database resulting in multiple writes to disk over its lifetime, is write amplification. It is a particular concern on SSDs, which can only overwrite blocks a limited number of times before wearing out.

In write-heavy applications the performance bottleneck may be the rate at which the database can write to disk, in which case write amplification directly costs throughput: the more the engine writes to disk, the fewer writes per second it can handle within the available bandwidth. LSM-trees are typically able to sustain higher write throughput than B-trees, partly because they sometimes have lower write amplification (depending on configuration and workload), and partly because they write compact SSTable files sequentially rather than overwriting several pages in the tree. This matters most on magnetic disks, where sequential writes are much faster than random writes.

LSM-trees also compress better and often produce smaller files on disk. B-tree storage leaves some disk space unused due to fragmentation: when a page is split or a row cannot fit in an existing page, some space in a page remains unused. LSM-trees are not page-oriented and periodically rewrite SSTables to remove fragmentation, so they have lower storage overhead, especially with leveled compaction.

On many SSDs the firmware internally uses a log-structured algorithm to turn random writes into sequential writes on the chips, so the impact of the storage engine's write pattern is less pronounced; but lower write amplification and reduced fragmentation are still advantageous because representing data compactly allows more read and write requests within the available I/O bandwidth.

Downsides of LSM-trees

The compaction process can sometimes interfere with ongoing reads and writes. Storage engines try to perform compaction incrementally without affecting concurrent access, but disks have limited resources, so a request can easily have to wait while the disk finishes an expensive compaction. The impact on average response time is usually small, but at higher percentiles the response time of queries to log-structured engines can be quite high, whereas B-trees are more predictable. These compaction stalls are a classic operational problem in Cassandra and RocksDB deployments.

Another issue arises at high write throughput: the disk's finite write bandwidth must be shared between the initial write (logging and flushing a memtable) and the compaction threads running in the background. The bigger the database gets, the more disk bandwidth compaction requires. If write throughput is high and compaction is not configured carefully, compaction cannot keep up with the rate of incoming writes. The number of unmerged segments on disk keeps growing until you run out of disk space, and reads slow down because they must check more segment files. Typically SSTable-based engines do not throttle incoming writes even when compaction falls behind, so you need explicit monitoring to detect this situation.

Finally, an advantage of B-trees is that each key exists in exactly one place in the index, whereas a log-structured engine may have multiple copies of the same key in different segments. This makes B-trees attractive for databases that want to offer strong transactional semantics: in many relational databases, transaction isolation is implemented using locks on ranges of keys, and in a B-tree those locks can be attached directly to the tree. (Chapter 7 covers this.)

B-trees are very ingrained in database architecture and consistently deliver good performance for many workloads, so they are unlikely to go away. In new datastores, log-structured indexes are increasingly popular. There is no quick and easy rule for which is better; empirical testing is the honest answer.

Other indexing structures

Secondary indexes

So far the discussion has been about key-value indexes, which are like a primary key index in the relational model. The primary key uniquely identifies one row, document or vertex, and other records refer to it by that key. It is also common to have secondary indexes; in a relational database you create several on the same table with CREATE INDEX, and they are often crucial for performing joins efficiently.

A secondary index can easily be constructed from a key-value index. The main difference is that keys are not unique: many rows may have the same value in the indexed column. There are two ways to handle that: make each value in the index a list of matching row identifiers (like a posting list in a full-text index), or make each key unique by appending a row identifier to it. Either way, both B-trees and LSM-trees can serve as secondary indexes.

Storing values within the index

The key in an index is what queries search for, but the value can be one of two things: the actual row (document, vertex) itself, or a reference to the row stored elsewhere. In the latter case, the place where rows are stored is a heap file, which stores data in no particular order (append-only, or tracking deleted rows to overwrite them later). The heap-file approach is common because it avoids duplicating data when multiple secondary indexes are present: each index just references a location in the heap file and the data lives in one place.

Updating a value without changing the key is efficient with a heap file: the record is overwritten in place, provided the new value is not larger. If it is, the record is moved to a new location with enough space, and either all indexes are updated or a forwarding pointer is left behind at the old location.

The extra hop from index to heap file is a performance penalty for reads, so in some cases the indexed row is stored directly in the index. This is a clustered index. In MySQL's InnoDB engine, the primary key of a table is always a clustered index, and secondary indexes refer to the primary key rather than a heap-file location (so a secondary lookup is two B-tree traversals). In SQL Server you can specify one clustered index per table. PostgreSQL, by contrast, always uses a heap (its CLUSTER command sorts the heap once but does not maintain the order).

A compromise between a clustered index (all row data in the index) and a non-clustered index (only references to the data) is a covering index or index with included columns, which stores some of a table's columns within the index. That allows some queries to be answered by using the index alone, in which case the index is said to cover the query. As with any kind of duplication, clustered and covering indexes speed up reads but require additional storage and add overhead on writes, and the database must work to enforce transactional guarantees across the copies.

Multi-column indexes

The indexes discussed so far map a single key to a value. If you need to query multiple columns of a table (or fields of a document) simultaneously, you need a multi-column index. The most common type is a concatenated index, which combines several fields into one key by appending one column to another, with the index definition specifying the order. It is like an old-fashioned paper phone book, sorted by (lastname, firstname): you can find everyone with a particular last name, or a particular (last, first) combination, but it is useless for finding everyone with a particular first name. Column order in composite indexes is one of the most common practical performance questions.

Multi-dimensional indexes are a more general way of querying several columns at once, important for geospatial data. A restaurant search needs all restaurants within a rectangle of latitude and longitude:

SELECT * FROM restaurants
WHERE latitude  > 51.4946 AND latitude  < 51.5079
  AND longitude > -0.1162 AND longitude < -0.1004;

A standard B-tree or LSM-tree cannot answer that efficiently: it can give you either all restaurants in a latitude range (at any longitude) or all in a longitude range (at any latitude), but not both at once. One option is to translate a two-dimensional location into a single number using a space-filling curve (such as a Z-order or Hilbert curve, or a geohash) and then use a regular B-tree index. More commonly, specialized spatial indexes such as R-trees are used; PostGIS implements geospatial indexes as R-trees using PostgreSQL's Generalized Search Tree (GiST) feature. Multi-dimensional indexes are not just for geography: on an e-commerce site a (red, green, blue) index could search products in a color range; on a weather database a (date, temperature) index could find observations in a given year with temperatures between 25 and 30 degrees.

Full-text search and fuzzy indexes

All the indexes so far assume you have exact data and can query exact values or ranges. They do not let you search for similar keys, such as misspelled words. Such fuzzy querying requires different techniques.

Full-text search engines commonly allow a search for one word to be expanded to include synonyms, to ignore grammatical variations, and to search for occurrences of words near each other in the same document, and they support linguistic analysis of the text. To cope with typos, Lucene can search text for words within a certain edit distance (an edit distance of one means one letter has been added, removed or replaced). Lucene's SSTable-like term dictionary uses an in-memory index that is a finite state automaton over the characters in the keys, similar to a trie. This automaton can be transformed into a Levenshtein automaton, which supports efficient search for words within a given edit distance. Other fuzzy search techniques go in the direction of document classification and machine learning, which the book leaves to information retrieval textbooks.

Keeping everything in memory

Disks have two significant advantages: they are durable (contents are not lost on power off) and they are cheaper per gigabyte than RAM. As RAM becomes cheaper the cost argument erodes, and many datasets simply are not that big, so it is feasible to keep them entirely in memory, possibly distributed across several machines. This has led to in-memory databases.

Some in-memory key-value stores, such as Memcached, are intended for caching only, where it is acceptable to lose data on restart. Others aim for durability, by special hardware (battery-powered RAM), by writing a log of changes to disk, by writing periodic snapshots to disk, or by replicating the in-memory state to other machines. When an in-memory database restarts it reloads its state from disk or from a replica over the network. The disk is merely an append-only log for durability; reads are served entirely from memory. Writing to disk also has operational advantages: files are easily backed up, inspected and analyzed by external tools.

Products such as VoltDB, MemSQL (now SingleStore) and Oracle TimesTen are in-memory databases with a relational model, claiming big performance improvements by removing the overheads of managing on-disk data structures. RAMCloud is an open source in-memory key-value store with durability using a log-structured approach for data in memory as well as on disk. Redis and Couchbase provide weak durability by writing to disk asynchronously.

Counterintuitively, the performance advantage of in-memory databases is not due to the fact that they do not need to read from disk. Even a disk-based storage engine may never need to read from disk if you have enough memory, because the operating system caches recently used disk blocks. Rather, they can be faster because they avoid the overheads of encoding in-memory data structures in a form that can be written to disk. Besides performance, in-memory databases also make it easier to provide data models that are difficult to implement with disk-based indexes: Redis offers a database-like interface to priority queues and sets, which is simple when everything is in memory.

Research suggests in-memory architectures can extend to datasets larger than memory without reintroducing the overheads of disk-centric design. The anti-caching approach evicts the least recently used data from memory to disk when there is not enough memory, and loads it back when accessed again. This is similar to what operating systems do with virtual memory and swap files, but the database can manage memory more efficiently since it works at the granularity of individual records rather than whole memory pages. Future non-volatile memory (NVM) technologies may change these designs further.

Transaction processing or analytics?

Two access patterns

In the early days of business data processing, a write to the database typically corresponded to a commercial transaction (a sale, an order, a salary payment). The term transaction stuck even when databases expanded beyond money, and it now refers to a group of reads and writes forming a logical unit (Chapter 7 covers the ACID sense). Transaction processing just means allowing clients to make low-latency reads and writes, as opposed to batch processing jobs that run periodically.

The basic access pattern of this online transaction processing (OLTP) workload: an application looks up a small number of records by some key, using an index; records are inserted or updated based on user input; the application is interactive. Databases also started being used for data analytics, with a very different access pattern: an analytic query scans a huge number of records, reading only a few columns per record, and calculates aggregate statistics (count, sum, average) rather than returning raw data to the user. These queries are written by business analysts and feed reports that help management make decisions, which is why this is called business intelligence. To differentiate it from transaction processing, this pattern is called online analytic processing (OLAP).

Property	OLTP	OLAP
Main read pattern	Small number of records per query, fetched by key	Aggregate over a large number of records
Main write pattern	Random-access, low-latency writes from user input	Bulk import (ETL) or event stream
Primarily used by	End user or customer, via a web application	Internal analyst, for decision support
What the data represents	Latest state of data (current point in time)	History of events that happened over time
Dataset size	Gigabytes to terabytes	Terabytes to petabytes

Data warehousing

At first the same databases were used for both transaction processing and analytic queries, and SQL is flexible enough to do both. From the late 1980s and early 1990s there was a trend for companies to stop using their OLTP systems for analytics and run analytics on a separate database instead: the data warehouse.

An enterprise may have dozens of transaction processing systems (the customer-facing website, point-of-sale systems in stores, inventory tracking, route planning for vehicles, supplier management, employee administration), each complex and maintained by a separate team. These systems are expected to be highly available and to process transactions with low latency, since they are critical to the business; database administrators are reluctant to let analysts run ad hoc queries on them, since those queries are expensive, scan large parts of the dataset, and harm the performance of concurrently executing transactions.

A data warehouse is a separate database that analysts can query to their hearts' content without affecting OLTP operations. It contains a read-only copy of the data in all the various OLTP systems. Data is extracted from the OLTP databases (using a periodic dump or a continuous stream of updates), transformed into an analysis-friendly schema, cleaned up, and loaded into the warehouse. This is Extract-Transform-Load (ETL).

Data warehouses exist in almost all large enterprises but are rare in small companies, which have fewer OLTP systems and a small enough volume of data to query in a conventional SQL database or even a spreadsheet. The big advantage of a separate warehouse is that it can be optimized for analytic access patterns. The indexing algorithms in the first half of this chapter work well for OLTP but are not very good at answering analytic queries.

The divergence between OLTP databases and data warehouses

The data model of a data warehouse is most commonly relational, because SQL is generally a good fit for analytic queries, and many graphical data analysis tools generate SQL. On the surface a warehouse and a relational OLTP database look similar, but the internals can be very different, because they are optimized for different query patterns. Many vendors now focus on supporting either transaction processing or analytics, not both.

Teradata, Vertica, SAP HANA and ParAccel sell warehouses under expensive commercial licenses; Amazon Redshift is a hosted version of ParAccel. More recently a plethora of open source SQL-on-Hadoop projects emerged to compete with commercial warehouses: Apache Hive, Spark SQL, Cloudera Impala, Facebook Presto (now Trino), Apache Tajo and Apache Drill. Some are based on ideas from Google's Dremel. The modern cloud equivalents are Snowflake, BigQuery and Redshift.

Stars and snowflakes: schemas for analytics

A wide range of data models is used in transaction processing. In analytics there is much less diversity: most data warehouses use a fairly formulaic style known as a star schema, also called dimensional modeling.

At the center is the fact table (say, fact_sales). Each row represents an event that occurred at a particular time, such as a customer's purchase of a product. If you were analyzing website traffic rather than retail sales, each row might be a page view or a click. Facts are captured as individual events, which allows maximum flexibility of analysis later, but it means the fact table can become extremely large: a big enterprise may have tens of petabytes of transaction history, mostly in fact tables.

Some columns in the fact table are attributes, such as the price at which the product was sold and the cost of buying it from the supplier (so profit margin can be calculated). Other columns are foreign key references to other tables, called dimension tables. As each row in the fact table represents an event, the dimensions represent the who, what, where, when, how and why of the event: dim_product with SKU, description, brand, category and weight; dim_store; dim_customer; dim_promotion. Even date and time are often represented as dimension tables, because this allows additional information about dates (such as public holidays) to be encoded, so queries can differentiate between sales on holidays and non-holidays.

The name star schema comes from the shape when the relationships are visualized: the fact table in the middle, surrounded by its dimension tables like rays of a star. A variation is the snowflake schema, where dimensions are further broken down into sub-dimensions: brands and categories kept in separate tables rather than as strings in dim_product. Snowflake schemas are more normalized than star schemas, but star schemas are often preferred because they are simpler for analysts to work with.

In a typical data warehouse, tables are often very wide: fact tables often have over 100 columns, sometimes several hundred. Dimension tables can be wide too, since they include all the metadata that may be relevant for analysis.

Column-oriented storage

Storing columns, not rows

If you have trillions of rows and petabytes of data in your fact tables, storing and querying them efficiently becomes a challenging problem. Dimension tables are usually much smaller (millions of rows), so this section concentrates on facts. Although fact tables are often over 100 columns wide, a typical warehouse query only accesses four or five at a time (SELECT * is rare in analytics). A query such as "are people more inclined to buy fresh fruit or candy, depending on the day of the week?" touches date_key, product_sk and quantity, and ignores all other columns.

In most OLTP databases, storage is laid out row-oriented: all values from one row of a table are stored next to each other. Document databases are similar, an entire document stored as one contiguous sequence of bytes. To process the query above, you may have an index on date_key that finds all sales in a given month, but a row-oriented engine still needs to load all those rows (each over 100 attributes) from disk into memory, parse them, and filter out those that do not meet the conditions. That takes a long time.

The idea behind column-oriented storage is simple: do not store all the values from one row together, but store all the values from each column together instead. If each column is stored in a separate file, a query only needs to read and parse the columns used in that query, which can save a lot of work. The column-oriented layout relies on each column file containing the rows in the same order; to reassemble the 23rd row, take the 23rd entry from each column file.

Column storage is easiest to understand in a relational model but applies equally to non-relational data. Parquet is a columnar storage format that supports a document data model, based on Google's Dremel.

Column compression

Besides only loading the needed columns, column-oriented storage lends itself to compression. Column values often look repetitive: a retailer may have billions of sales but only 100,000 distinct products, and the sequence of values in a column repeats. Many compression techniques work; one particularly effective in warehouses is bitmap encoding.

The number of distinct values in a column is usually small compared with the number of rows. Take a column with n distinct values and turn it into n separate bitmaps, one per distinct value, with one bit per row: 1 if the row has that value, 0 if not. If n is very small (a country column with 200 values), the bitmaps can be stored with one bit per row. If n is bigger, there will be many zeros in most bitmaps (the bitmaps are sparse), so additionally run-length encode them: store the lengths of the runs of zeros and ones instead of the bits themselves. This makes the encoding of a column remarkably compact.

Bitmap indexes are well suited to the kinds of queries common in a warehouse:

WHERE product_sk IN (30, 68, 69)

Load the three bitmaps for product_sk = 30, 68 and 69 and calculate the bitwise OR of them, which is very fast.

WHERE product_sk = 31 AND store_sk = 3

Load the bitmaps for product_sk = 31 and store_sk = 3, and calculate the bitwise AND. This works because the columns contain the rows in the same order, so the kth bit in one column's bitmap corresponds to the same row as the kth bit in another.

There are different compression schemes for different kinds of data. Cassandra and HBase have a concept of column families, inherited from Bigtable, but it is misleading to call them column-oriented: within each column family they store all columns from a row together, along with a row key, and do not use column compression. The Bigtable model is still mostly row-oriented.

Memory bandwidth and vectorized processing

For warehouse queries that scan millions of rows, a big bottleneck is the bandwidth for getting data from disk into memory. But that is not the only bottleneck. Developers of analytical databases also worry about efficiently using the bandwidth from main memory into the CPU cache, avoiding branch mispredictions and bubbles in the CPU instruction pipeline, and making use of single-instruction-multi-data (SIMD) instructions in modern CPUs.

Column-oriented layouts help here too. The query engine can take a chunk of compressed column data that fits comfortably in the CPU's L1 cache and iterate through it in a tight loop with no function calls, which is much faster than code that handles each record with many function calls and conditions. Column compression lets more rows from a column fit in the same amount of cache. Operators such as the bitwise AND and OR above can be designed to operate on such chunks of compressed column data directly. This technique is vectorized processing.

Sort order in column storage

In a column store the order of rows does not necessarily matter; the easiest is to store them in insertion order, since inserting a new row then just means appending to each column file. But you can choose to impose an order, like with SSTables, and use that as an indexing mechanism.

It would not make sense to sort each column independently, because then you no longer know which items in the columns belong to the same row. Rows can only be reconstructed because you know the kth item in one column and the kth item in another belong to the same row. Rather, the data needs to be sorted an entire row at a time, even though it is stored by column. The administrator chooses the sort key using knowledge of common queries. If queries often target date ranges, date_key could be the first sort key, so the query engine can scan only the rows from the last month and skip the rest. A second column determines the order of rows with the same first key: with product_sk second, all sales for the same product on the same day are grouped together, helping queries that group or filter sales by product within a date range.

Sorted order also helps compression. If the primary sort column does not have many distinct values, then after sorting it has long sequences where the same value repeats many times in a row, which a simple run-length encoding compresses to a few kilobytes even if the table has billions of rows. The compression effect is strongest on the first sort key; the second and third are more jumbled and do not have such long runs. Columns further down the sort priority appear in essentially random order and do not compress as well, but having the first few sorted is still a win.

A clever extension, introduced in C-Store and adopted by Vertica, is to store the same data sorted in several different ways. Data needs to be replicated to multiple machines anyway so that a machine failure does not lose data; you might as well store that redundant data sorted differently, so that when processing a query you can use the version that best fits the query pattern. Having multiple sort orders in a column store is a bit like having multiple secondary indexes in a row store, with one big difference: the row store keeps every row in one place (heap file or clustered index) and secondary indexes just contain pointers, whereas in the column store there are normally no pointers, only columns containing values.

Writing to column-oriented storage

These optimizations make sense in warehouses because most load is large read-only queries run by analysts. Column-oriented storage, compression and sorting all make reads faster but make writes more difficult. An update-in-place approach, like B-trees, is not possible with compressed columns: inserting a row in the middle of a sorted table would most likely require rewriting all the column files, since rows are identified by their position within a column, so an insertion must update all columns consistently.

The solution is the one from earlier in the chapter: LSM-trees. All writes first go to an in-memory store, where they are added to a sorted structure and prepared for writing to disk. It does not matter whether the in-memory store is row- or column-oriented. When enough writes have accumulated, they are merged with the column files on disk and written to new files in bulk. This is essentially what Vertica does. Queries examine both the column data on disk and the recent writes in memory and combine the two, but the query optimizer hides this distinction from the user; from an analyst's point of view, data modified by inserts, updates or deletes is immediately reflected in subsequent queries.

Aggregation: data cubes and materialized views

Not every warehouse is a column store; traditional row-oriented databases and a few other architectures are also used. Column storage is a worthwhile idea that is spreading, but one more aspect of warehouses is worth mentioning: materialized aggregates.

Warehouse queries often involve an aggregate function such as COUNT, SUM, AVG, MIN or MAX. If the same aggregates are used by many different queries, it is wasteful to crunch the raw data every time. Why not cache some of the counts or sums most often used? One way is a materialized view. In a relational model it is often defined like a standard (virtual) view: a table-like object whose contents are the results of some query. The difference is that a materialized view is an actual copy of the query results written to disk, whereas a virtual view is just a shortcut for writing queries. When the underlying data changes, a materialized view needs to be updated, because it is a denormalized copy; the database can do that automatically, but such updates make writes more expensive, which is why materialized views are not often used in OLTP databases but make more sense in read-heavy warehouses.

A common special case is the data cube or OLAP cube: a grid of aggregates grouped by different dimensions. Imagine each fact has foreign keys to only two dimension tables, date and product. A two-dimensional table has dates on one axis and products on the other, each cell containing the aggregate (such as SUM(net_price)) of all facts with that date-product combination. You can then apply the same aggregate along each row or column to get a summary reduced by one dimension (sales per product regardless of date, or per date regardless of product). In general facts have more than two dimensions (date, product, store, promotion, customer), making a five-dimensional hypercube, with aggregates along each dimension and combination of dimensions.

The advantage of a materialized data cube is that certain queries become very fast because they have been precomputed: total sales per store yesterday is a lookup along one dimension. The disadvantage is that a data cube does not have the same flexibility as querying raw data: there is no way to calculate the proportion of sales from items costing more than 100 dollars, because price is not one of the dimensions. Most warehouses therefore keep as much raw data as possible and use aggregates such as data cubes only as a performance boost for certain queries.

Design trade-offs

Choice	Pick it when	Pay for it with
Hash index (Bitcask)	Keys fit in RAM, many updates to few keys, point lookups only	No range queries; recovery must rebuild or snapshot the map
LSM-tree (RocksDB, Cassandra, HBase)	Write-heavy workload, need for compression, sequential I/O matters, range scans	Read amplification across levels, compaction stalls at high percentiles, compaction falling behind under sustained writes
B-tree (InnoDB, PostgreSQL, SQL Server)	Read-heavy or mixed workload, predictable latency, range locking for transactions	Write amplification from WAL plus page writes, fragmentation, in-place updates on SSDs
Leveled compaction	Read-heavy LSM, space-constrained	Higher write amplification
Size-tiered compaction	Write-heavy LSM, time-series data	Temporary space blowup, more SSTables per read
Clustered index	Primary-key range scans need the row data immediately	Secondary lookups go through the primary key; wide rows bloat the tree
Heap file plus secondary indexes	Many secondary indexes, frequent updates to non-key columns	Extra hop from index to heap on every read
Covering index	A hot query reads a few non-key columns	Duplication and write overhead for those columns
In-memory database (Redis, VoltDB)	Dataset fits in RAM, need rich data structures or very low latency	Durability via log or replication; cost per gigabyte
Row store for OLTP	Point reads and writes on whole records	Terrible for scans that read a few columns of millions of rows
Column store for OLAP (Vertica, Redshift, Parquet)	Analytical scans and aggregates over a few columns	Writes must be batched through an LSM-like path; row reconstruction is expensive
Materialized views and data cubes	Repeated aggregates on read-heavy data	Write cost to keep them fresh; loss of flexibility if raw data is dropped

Interview angle

• Why do databases not index every column by default? Each index is a derived structure that must be updated on every write, so indexes trade read speed for write speed and storage. The developer knows the query patterns and picks indexes that pay for themselves; the database cannot know which columns matter.
• Explain how an LSM-tree handles a write and a read. Write: append to the WAL for durability, insert into the memtable (a sorted in-memory tree); when the memtable fills, flush it as an immutable SSTable. Read: check the memtable, then SSTables from newest to oldest, consulting each SSTable's Bloom filter to skip files that cannot contain the key, and using the sparse index to locate the block. Background compaction merges SSTables and drops overwritten values and tombstones.
• Compare B-trees and LSM-trees for a write-heavy workload like event ingestion. The LSM-tree writes sequentially and often has lower write amplification, so it sustains higher write throughput and compresses better. The B-tree writes each change to the WAL and then overwrites whole pages, which costs more I/O. The cost of the LSM choice is read amplification and tail latency during compaction, plus the risk of compaction falling behind, which you must monitor.
• What is write amplification and why does it matter on SSDs? The ratio of bytes written to disk to bytes written by the application over the data's lifetime. B-trees amplify through the WAL and full-page writes; LSM-trees through repeated compaction. SSD cells tolerate a limited number of erase cycles, so high amplification shortens drive life and consumes the write bandwidth that bounds throughput.
• What happens if compaction cannot keep up? Unmerged SSTables accumulate: reads slow down because each lookup checks more files, disk fills with redundant copies of overwritten keys, and eventually the disk runs out. Most engines do not throttle writes automatically, so you need metrics on pending compactions and SSTable counts, and you may need to throttle writers or add compaction threads.
• Why does a B-tree need a write-ahead log if it writes pages directly? A single logical change can modify several pages (a leaf split touches two leaves and a parent). A crash midway leaves the tree inconsistent. Writing the intended changes to an append-only log first makes recovery possible: replay the log to redo incomplete changes. Copy-on-write engines like LMDB avoid the WAL by never overwriting pages and atomically switching the root.
• Clustered index versus heap file: how does InnoDB differ from PostgreSQL? InnoDB stores row data in the primary-key B-tree (clustered), so primary-key range scans are fast and secondary indexes store the primary key, costing two traversals per secondary lookup. PostgreSQL stores rows in a heap and every index, primary included, points to heap tuple locations, so all index lookups take one extra hop but secondary indexes do not depend on the primary key's size.
• Design the storage for an analytics system over billions of click events. Model clicks as a fact table with dimension tables for user, page, time and campaign (star schema). Store it column-oriented (Parquet on object storage, or a warehouse like Redshift, BigQuery or ClickHouse), sorted by date then by a high-cardinality filter column, with bitmap and run-length compression and vectorized execution. Ingest in batches through an LSM-style buffer. Precompute common aggregates as materialized views or a data cube, but keep the raw facts for ad hoc questions.
• Why are in-memory databases fast, if the OS caches disk blocks anyway? Not because they skip disk reads; a disk-based engine with a warm page cache also reads from memory. They are fast because they avoid encoding and decoding data structures into on-disk formats and avoid the bookkeeping of a page-oriented engine. Durability comes from an append-only log, snapshots or replication, so a restart reloads state rather than losing it.
• How do bitmap indexes make WHERE a IN (...) AND b = ... fast? Each distinct value of a column has a bitmap with one bit per row. An IN list is a bitwise OR of several bitmaps; an AND across columns is a bitwise AND, valid because all columns keep rows in the same order. Sparse bitmaps are run-length encoded, so the operations run over compressed data in CPU cache.

Pitfalls and misconceptions

• "LSM-trees are always faster." They are usually faster for writes and often more compact, but reads may touch multiple levels, and compaction introduces tail-latency spikes and background I/O. Benchmarks depend on the workload; measure yours.
• Confusing the LSM write-ahead log with the SSTables. The log exists only to rebuild the memtable after a crash and is discarded once the memtable is flushed. It is not the data store; the SSTables are.
• Thinking B-trees are log-free. Every production B-tree engine keeps a WAL (or uses copy-on-write) because multi-page updates are not atomic. The WAL is a large part of B-tree write amplification.
• Believing a Bloom filter can confirm a key exists. It can only say "definitely not here" or "maybe here". False positives mean occasional wasted disk reads; false negatives never happen.
• Treating Cassandra and HBase column families as column-oriented storage. Within a column family, all columns of a row are stored together with the row key, without column compression. The Bigtable model is row-oriented; Vertica, Redshift, Parquet and ClickHouse are column-oriented.
• Putting the low-selectivity column first in a composite index out of habit. The leading column determines what prefix queries the index can serve; order it by how queries filter, and remember a (lastname, firstname) index cannot find people by first name alone.
• Assuming in-memory databases are fast because they avoid disk reads. Page caches already avoid most disk reads. The gain is avoiding serialization overhead and page-oriented bookkeeping.
• Dropping raw facts once a data cube exists. Cubes answer only the questions along their dimensions. Keep the raw fact table and treat aggregates as a cache.
• Running analysts' queries on the OLTP primary. Analytic scans evict the working set from the buffer pool, hold up transactions and spike latency. Replicate into a warehouse via ETL or change-data capture instead.

Key terms

Term	Meaning
Log (append-only)	A file to which records are only ever appended; the basis of log-structured storage and of write-ahead logs
Index	A derived structure that speeds up lookups at the cost of extra work on writes
Hash index	In-memory map from key to byte offset in a data file (Bitcask)
Segment	A chunk of the append-only log, closed when it reaches a size limit
Compaction	Discarding overwritten and deleted keys from segments, keeping only the latest value per key
Tombstone	A deletion marker appended to the log so merges can drop earlier values
SSTable	A segment file whose key-value pairs are sorted by key, each key appearing once
Memtable	The in-memory sorted tree (red-black or AVL, or a skip list in RocksDB) that buffers writes before flushing to an SSTable
LSM-tree	Log-Structured Merge-Tree: a cascade of SSTables plus a memtable, merged in the background
Bloom filter	Probabilistic set that answers "definitely absent" or "possibly present"; used to skip SSTables
Size-tiered / leveled compaction	Merging strategies: merge small SSTables into larger ones, or maintain non-overlapping levels of increasing size
B-tree	Balanced tree of fixed-size pages with high branching factor; keys sorted; pages updated in place
Page / block	The fixed-size unit (commonly 4 KB; 16 KB in InnoDB) a B-tree reads and writes
Branching factor	Number of child references per B-tree page; typically several hundred
Write-ahead log (WAL, redo log)	Append-only log of intended page modifications written before the pages, used for crash recovery
Copy-on-write	Writing a modified page to a new location and updating parents up to a new root (LMDB)
Latch	A lightweight short-duration lock protecting a data structure such as a B-tree page
Write amplification	Bytes physically written per byte logically written over the data's lifetime
Compaction stall	Latency spike when a foreground request waits for disk resources consumed by compaction
Secondary index	Index on a non-unique attribute; values are posting lists or keys made unique by appending the row ID
Heap file	Unordered storage for rows, referenced by location from indexes
Clustered index	An index that stores the row data itself in its leaves (InnoDB primary key)
Covering index	An index that includes extra columns so a query can be answered from the index alone
Concatenated index	Multi-column index that orders by the first column, then the second, and so on
R-tree / space-filling curve	Techniques for multi-dimensional (geospatial) indexing
Levenshtein automaton	Finite automaton used by Lucene to find terms within an edit distance
Anti-caching	Evicting cold records from an in-memory database to disk at record granularity
OLTP / OLAP	Online transaction processing (point reads and writes) / online analytic processing (large scans and aggregates)
Data warehouse	A separate read-only analytic copy of OLTP data, loaded via ETL
ETL	Extract-Transform-Load pipeline feeding the warehouse
Star schema / snowflake schema	Fact table surrounded by dimension tables; snowflake normalizes dimensions into sub-dimensions
Fact table / dimension table	Events (one row each) / the who, what, where, when of those events
Column-oriented storage	Storing each column's values contiguously, in the same row order across columns
Bitmap encoding / run-length encoding	One bitmap per distinct value, with runs of zeros and ones compressed as lengths
Vectorized processing	Executing operators over chunks of compressed column data that fit in CPU cache, often with SIMD
Materialized view	A query result physically stored and kept updated, as opposed to a virtual view
Data cube (OLAP cube)	Precomputed aggregates grouped by combinations of dimensions

Further reading

• DDIA, Chapter 3 (reference list at https://github.com/ept/ddia-references).
• Patrick O'Neil, Edward Cheng, Dieter Gawlick and Elizabeth O'Neil, "The Log-Structured Merge-Tree (LSM-Tree)", Acta Informatica, 1996. The original LSM paper.
• Justin Sheehy and David Smith, "Bitcask: A Log-Structured Hash Table for Fast Key/Value Data", Basho Technologies, 2010. Short and readable; the hash-index section follows it closely.
• Fay Chang et al., "Bigtable: A Distributed Storage System for Structured Data", OSDI 2006. Introduces SSTables, memtables and column families.
• Rudolf Bayer and Edward M. McCreight, "Organization and Maintenance of Large Ordered Indices", Acta Informatica, 1972. The B-tree paper.
• Goetz Graefe, "Modern B-Tree Techniques", Foundations and Trends in Databases, 2011. Everything about B-tree variants, latching and logging in one survey.
• RocksDB Wiki (https://github.com/facebook/rocksdb/wiki), especially the pages on compaction, Bloom filters and write amplification.
• Mike Stonebraker et al., "C-Store: A Column-oriented DBMS", VLDB 2005; and Daniel Abadi et al., "The Design and Implementation of Modern Column-Oriented Database Systems", Foundations and Trends in Databases, 2013.
• Sergey Melnik et al., "Dremel: Interactive Analysis of Web-Scale Datasets", VLDB 2010. The basis of Parquet and BigQuery.
• Ralph Kimball and Margy Ross, The Data Warehouse Toolkit, 3rd edition, Wiley, 2013. The standard reference for star and snowflake schemas.
• PostgreSQL documentation, Chapter "Indexes" (https://www.postgresql.org/docs/current/indexes.html), for B-tree, GiST, GIN and covering (INCLUDE) indexes in practice.