As discussed in “Stars and Snowflakes: Schemas for Analytics”, data warehouses by convention often use a relational schema with a big fact table that contains foreign-key references into dimension tables. If you have trillions of rows and petabytes of data in your fact tables, storing and querying them efficiently becomes challenging. Dimension tables are usually much smaller and more manageable (millions of rows), so in this section we will focus on storage of facts.
Although fact tables are often over one hundred columns wide, a typical data warehouse query accesses only four or five of them at one time (SELECT * queries are rarely needed for analytics). Take the query in Example 4-1: it accesses a large number of rows (every occurrence of someone buying fruit or candy during the 2024 calendar year), but it needs to access only three columns of the fact_sales table: date_key, product_sk, and quantity. The query ignores all other columns.
Example 4-1. Analyzing whether people are more inclined to buy fresh fruit or candy, depending on the day of the week
SELECT
dim_date.weekday, dim_product.category,
SUM(fact_sales.quantity) AS quantity_sold
FROM fact_sales
JOIN dim_date ON fact_sales.date_key = dim_date.date_key
JOIN dim_product ON fact_sales.product_sk = dim_product.product_sk
WHERE
dim_date.year = 2024 AND
dim_product.category IN ('Fresh fruit', 'Candy')
GROUP BY
dim_date.weekday, dim_product.category;
How can we execute this query efficiently?
In most OLTP databases, storage is laid out in a row-oriented fashion: all the values from one row of a table are stored next to one another. Document databases are similar: an entire document is typically stored as one contiguous sequence of bytes. You can see this in the CSV example of Figure 4-1.
To process a query like the one in Example 4-1, you may have indexes on fact_sales.date_key and/or fact_sales.product_sk that tell the storage engine where to find all the sales for a particular date or for a particular product. But then, a row-oriented storage engine still needs to load all those rows (each consisting of over 100 attributes) from disk into memory, parse them, and filter out those that don’t meet the required conditions. That can take a long time.
The idea behind column-oriented (or columnar) storage is simple: instead of storing all the values from one row together, store all the values from each column together instead. If each column is stored separately, a query needs to read and parse only those columns that are used in that query, which can save a lot of work. Figure 4-7 shows this principle using an expanded version of the fact table from Figure 3-5.
Note
Column storage is easiest to understand in a relational data model, but it applies equally to nonrelational data. For example, Parquet is a columnar storage format that supports a document data model based on Google’s Dremel using a technique known as shredding or striping.
Diagram comparing traditional row-based storage and columnar storage layout for relational data.
Figure 4-7. Storing relational data by column rather than by row
The column-oriented storage layout relies on each column storing the rows in the same order. Thus, if you need to reassemble an entire row, you can take the 23rd entry from each of the individual columns and put them together to form the 23rd row of the table.
In practice, columnar storage engines don’t actually store an entire column (containing perhaps trillions of rows) in one go. Instead, they break the table into blocks of thousands or millions of rows, and within each block they store the values from each column separately. Since many queries are restricted to a particular date range, it is common to make each block contain the rows for a particular timestamp range. A query then needs to load only the columns it needs in those blocks that overlap with the required date range.
Columnar storage is used in almost all analytical databases nowadays, ranging from large-scale cloud data warehouses such as Snowflake to single-node embedded databases such as DuckDB and product analytics systems such as Pinot and Druid. It is used in storage formats such as Parquet, ORC, Lance, and Nimble and in-memory analytics formats like Apache Arrow and Pandas/NumPy. Some time-series databases, such as InfluxDB IOx and TimescaleDB, are also based on column-oriented storage.
Column compression
Besides loading from disk only those columns that are required for a query, we can further reduce the demands on disk throughput and network bandwidth by compressing data. Fortunately, column-oriented storage often lends itself very well to compression.
Take a look at the sequences of values for each column in Figure 4-7. There’s a fair amount of repetition, which is a good sign for compression. Depending on the data in the column, different compression techniques can be used. One technique that is particularly effective in data warehouses is bitmap encoding, illustrated in Figure 4-8.
Diagram illustrating bitmap indexes for a column with various values and their corresponding run-length encoding, highlighting how repetitive data can be efficiently compressed.
Figure 4-8. Compressed, bitmap-indexed storage of a single column
Often the number of distinct values in a column is small compared to the number of rows (for example, a retailer may have billions of sales transactions, but only 100,000 distinct products). We can now take a column with n distinct values and turn it into n separate bitmaps: one bitmap for each distinct value, with one bit for each row. The bit is 1 if the row has that value, and 0 if not.
One option is to store the bitmaps using one bit per row. However, these bitmaps typically contain a lot of 0s (we say that they are sparse). In that case, the bitmaps can additionally be run-length encoded, which involves counting consecutive 0s or 1s and storing the counts, as shown at the bottom of Figure 4-8. Techniques such as roaring bitmaps switch between the two bitmap representations, using whichever is the most compact. This can make the encoding of a column remarkably efficient.
Bitmap indexes such as these are very well suited for the kinds of queries that are common in a data warehouse. For example:
WHERE product_sk IN (31, 68, 69)
Load the three bitmaps for product_sk = 31, product_sk = 68, and product_sk = 69, and calculate the bitwise OR of the three bitmaps, which can be done very efficiently.
WHERE product_sk = 30 AND store_sk = 3
Load the bitmaps for product_sk = 30 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 column’s bitmap.
Bitmaps can also be used to answer graph queries, such as finding all users of a social network who are followed by user X and who also follow user Y.
Note
Don’t confuse column-oriented databases with the wide-column (also known as column-family) data model, in which a row can have thousands of columns, and there is no need for all the rows to have the same columns. Despite the similarity in name, wide-column databases are row-oriented, since they store all values from a row together. Google Bigtable, Apache Accumulo, and HBase are examples of systems that use the wide-column model.
Sort order in column storage
In a column store, the order in which the rows are stored doesn’t necessarily matter. It’s easiest to store them in the order in which they were inserted, since then inserting a new row just means appending to each of the columns. However, we can choose to impose an order, as we did with SSTables previously, and use that as an indexing mechanism.
Note that sorting each column independently wouldn’t make sense because then we would no longer know which items in the columns belong to the same row. We can reconstruct a row only because we know that the kth item in one column belongs to the same row as the kth item in another column.
Rather, the data needs to be sorted an entire row at a time, even though it is stored by column. The administrator of the database can choose the columns by which the table should be sorted, using their knowledge of common queries. For example, if queries often target date ranges, such as the last month, it might make sense to make date_key the first sort key. Then the query can scan only the rows from the last month, which will be much faster than scanning all rows.
A second column can determine the sort order of any rows that have the same value in the first column. For example, if date_key is the first sort key in Figure 4-7, it might make sense for product_sk to be the second sort key so that all sales for the same product on the same day are grouped together in storage. That will help queries that need to group or filter sales by product within a certain date range.
Another advantage of sorted order is that it can help with compression of columns. If the primary sort column does not have many distinct values, then after sorting, it will have long sequences where the same value is repeated many times in a row. A simple run-length encoding, like that we used for the bitmaps in Figure 4-8, could compress that column down to a few kilobytes—even if the table has billions of rows.
That compression effect is strongest on the first sort key. The second and third sort keys will be more jumbled up and thus will not have such long runs of repeated values. Columns further down the sorting priority appear in essentially random order, so they probably won’t compress as well. Still, having the first few columns sorted is a win overall.
Writing to column-oriented storage
We saw in “Characterizing Transaction Processing and Analytics” that reads in data warehouses tend to consist of aggregations over a large number of rows. Column-oriented storage, compression, and sorting all help to make those read queries faster.
Writes in a data warehouses tend to be bulk imports of data, often via an ETL process. With columnar storage, writing an individual row somewhere in the middle of a sorted table would be very inefficient, as you would have to rewrite all the compressed columns from the insertion position onward. However, a bulk write of many rows at once amortizes the cost of rewriting those columns, making it efficient.
A log-structured approach is often used to perform writes in batches. All writes first go to a row-oriented, sorted, in-memory store. When enough writes have accumulated, they are merged with the column-encoded files on disk and written to new files in bulk. As old files remain immutable and new files are written in one go, object storage is well suited for storing these files.
Queries need to examine both the column data on disk and the recent writes in memory, and combine the two. The query execution engine hides this distinction from the user. From an analyst’s point of view, data that has been modified with inserts, updates, or deletes is immediately reflected in subsequent queries. Snowflake, Vertica, Apache Pinot, Apache Druid, and many other databases do this.