How does a column-oriented DBMS filter on multiple columns?
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.