How does a column-oriented DBMS filter on multiple columns? I'm learning how column-oriented DBMS / &quot;columnars&quot; 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?
There are a few factors which reduce the horror of a full scan of the shop column.

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.

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.

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.

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

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 &quot;shop&quot; 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.