CSE Roadmap

Specialist tier · about 2 hours · 6 parts

Part 4 of 6 · 2 min read

Sort order

Think of a column store's sort order like alphabetizing a filing cabinet by last name, then by first name within each last name. Reordering the whole cabinet this way still lets every drawer's contents be split out by field afterward.

In plain words: A column store does not have to sort each column independently, since that would destroy the ability to reassemble a row from matching positions across columns. Instead, the engine sorts entire rows together by a chosen set of sort key columns, then stores each column in that resulting row order. Whichever column is the first sort key ends up with long runs of repeated or nearby values, which compresses extremely well with run-length encoding, and also lets a query filtering on that column skip straight to the relevant range. Later sort keys compress progressively less well, since their values are only sorted within ties of the earlier keys. Because data is typically replicated across several machines anyway, some column stores keep more than one physical copy, each sorted by a different set of keys, so a query can use whichever copy best matches its own filter pattern.

A worked example. Sorting sales_fact by date_key first means every day's rows sit together, so a query filtering on a date range only scans that contiguous slice, and date_key itself compresses down to a handful of run-length-encoded runs instead of one value per row.

The key lines. No new SQL; sort order is a storage design choice.

Sorted by date_key, then book_id:
date_key:  140102 140102 140103 140103 140103
book_id:   7       31      7      7      42

Sort key (column store)

A sort key in a column store is a column, or ordered set of columns, chosen to determine the physical order every column's values are stored in, sorted a full row at a time rather than independently per column.

Example: sorting by date_key then book_id above groups same-date rows together and, within each date, groups same-book rows together.