Dremel compresses its data, because compressed data gives faster querying and faster retrieval.
The data is a JSON document. JSON is a set of key value pairs, and it also has objects. The schema is a document a search engine has picked up:
- A document has an ID, links and names.
- Each link is an object with a set of forward links and backward links.
- A name has a list of languages and a URL string.
- A language is an object with a string code and a country.
These are classes, and inside them are classes, lists and values. Dremel stores this in columns, not as a row.
The compression for a column is non zero run length encoding. Values that are the same are clustered together and replaced with a single value.
A column of restaurants in Mumbai, Delhi and Chennai is sorted, so each city sits together. Each city gets a value and a frequency: 3 Mumbais, 2 Delhis, 1 Chennai. Six data points store many data points of a column.