How does a column-oriented DBMS filter on multiple columns?

Question

I'm learning how column-oriented DBMS / "columnars" work for OLAP situations.

Let's say we have a log of millions of transactions with 3 columns: timestamp, shop, product, and we want to know the products sold in the shop A in a certain time range:

SELECT DISTINCT product FROM data
WHERE timestamp BETWEEN 1600010000 AND 1602678400 
            AND shop = 'A'

This will be stored like this (admittedly, this is more or less an abstraction):

timestamp [1600000000, 1600000005, 1600000005, 1600000017, 1600000018, ... ]
shop      [A, A, B, D, C, ...]
product   [X153, S76D, TYA6, LKJ6, SDH7, ...]

For this query:

• I totally get how we can achieve fast lookup by timestamp, since this column is sorted: with 2 dichotomic searches we can find the index for which timestamp=1600010000 and 1602678400. With less than 30 read operations of a few bytes, it's done, we have rowid_start, rowid_end (I don't know if it's still called rowid in the context of a columnar) that make the boundaries of this time-range. The key thing is that we haven't had to read megabytes of data, but just a few bytes.

• Question: then, how can a columnar filter by shop = 'A'? Do we have to read each entry of the column shop in the range rowid_start .. rowid_end to test if it's A or not? This could potentially be hundreds of MB or GB of data.

TL;DR: once we have filtered by one column, how can a columnar do a second-column-filtering, without doing a FULL SCAN?

Answer 1

There are a few factors which reduce the horror of a full scan of the shop column.

1. The values of each column can be stored in the same order: the first value of timestamp corresponds to the first value in shop and to the first in product; the second to the second to the second, and so on. So a fast lookup that gives the offsets for the start and end of the timestamp range also gives the offset of the corresponding values in shop. The search can jump straight to that offset in the list of shop values, if shop codes are fixed length or can be coerced into being fixed length. More on this soon.

2. For disk-oriented rather than fully in-memory systems, meta data can be held to show which disk files correspond to what offsets for each column. So IO is limited to only the files necessary.

3. IO is still block-oriented and all the shop codes are contiguous on disk. One (relatively fast) sequential read will return a lot of shop codes into memory.

4. Those codes can be stored contiguously in memory, which is very pre-fetch- and processor cache-friendly.

5. Compression. Even if the shop codes are quite long or of variable length, likely there will be relatively few unique values (Walmart has fewer than 12,000 stores). Dictionary compression can be applied, which maps each long string to a much shorter fixed length integer. The mapping table is held once and it is these integers which become the values held in column array. Run-length encoding can further reduce the size of the "shop" array, producing a virtuous feedback with file size, memory and CPU cache utilisation.

The RowID you speak about is a useful visualisation but need not be physically implemented. Since tuples' columns are stored in the same order, the offsets perform the function the RowID would. For multi-predicate queries it is unlikely an actual array of integers representing offsets would be built for each predicate and the intersection of these computed. Rather, each predicate would produce a bitmap and these bitmaps would be AND-ed (or OR-ed) to produce the final predicate. Each bit represents the offset of a tuple that satisfies the predicate.

One of the earliest column stores (C-Store) allowed for redundant storage of column sets, each of which could be sorted differently to facilitate fast predicate lookup. I know of no recent system which implements this, but it's an interesting idea.

Answer 2

Columns-organized storage engines are vastly different in implementation, so a general answer to your question is hardly possible. At a very basic level though a DBMS with a modestly advanced query optimizer would implement something like this:

1. Values of each column are stored together (as you have mentioned). Each value has some sort of a pointer (think ROWID), which is common to all columns of that specific row; this ID allows the engine to put back together rows decomposed for columnar storage.
2. Evaluation of each column-level predicate produces a list of "row IDs" matching the predicate. In your case there will be two lists, one for rows containing matching "timestamp" values, the other for shop.
3. "Row ID" lists from multiple predicates are coalesced into a single list. In your case this will be the intersection of two lists.
4. Values of additional columns in the select list (product in your example) are fetched using the final "row IDs" and returned to the client.

For an in-depth review of one possible implementation of a column-organized storage and query engine you can check this article from Db2 developers.