3 ms·

I'm curious about this comment: > The ultimate performance boost from compression comes when operators can act directly on compressed values without needing to

I'm curious about this comment: > The ultimate performance boost from compression comes when operators can act directly on compressed values without needing to decompress. Consider a sum operator and RLE encoded values. It suffices to multiply the value by the run length. It sounds very impressive and I can see in theory how it could benefit COUNT(), COUNT(DISTINCT ), SUM(), AVG(), MIN(), and MAX()... in other words, pretty much all of the common aggregation functions. For example, COUNT(DISTINCT *), MIN(), and MAX() can literally just ignore run length as those are known duplicates, while the others simply need to use the run length as a factor. Does anyone know if this specific optimization is actually implemented in any real-world database?

ryanworl 8y ago
Many analytics databases implement something even stronger than that. They keep what are called "zone maps", which are pre-computed statistics for groups of rows that contain those same aggregate functions. This allows for those types of analytics functions, but also for pruning of data to read at all during regular table scans further in the query execution.
kwillets 8y ago
From a Vertica query plan: explain select country, count(*) from tablename group by 1 ... +-GROUPBY PIPELINED (GLOBAL RESEGMENT GROUPS) [Cost: 79, Rows: 1] (PATH ID: 1) | Aggregates: count(*) | Group By: tablename.country | Execute on: All Nodes | +---> STORAGE ACCESS for tablename [Cost: 78, Rows: 14M (1 RLE)] (PATH ID: 2) ... Note the row count at the top level. This type of thing only works when the group column is the first in the projection sort order (or for multiple columns, a prefix of it). Generally GROUPBY PIPELINED indicates that the sort order is being used (including RLE).
manigandham 8y ago
This is used by all modern column-oriented databases. Combine the compression techniques with other metadata like max, min, avg, mean, null bloom filters, and more that is stored with each partition (group of X number of rows per column compressed together) and you can actually skip reading any data at all for many aggregation queries.

ryanworl 8y ago

Many analytics databases implement something even stronger than that. They keep what are called "zone maps", which are pre-computed statistics for groups of rows that contain those same aggregate functions. This allows for those types of analytics functions, but also for pruning of data to read at all during regular table scans further in the query execution.

kwillets 8y ago

From a Vertica query plan: explain select country, count(*) from tablename group by 1 ... +-GROUPBY PIPELINED (GLOBAL RESEGMENT GROUPS) [Cost: 79, Rows: 1] (PATH ID: 1) | Aggregates: count(*) | Group By: tablename.country | Execute on: All Nodes | +---> STORAGE ACCESS for tablename [Cost: 78, Rows: 14M (1 RLE)] (PATH ID: 2) ... Note the row count at the top level. This type of thing only works when the group column is the first in the projection sort order (or for multiple columns, a prefix of it). Generally GROUPBY PIPELINED indicates that the sort order is being used (including RLE).

manigandham 8y ago

This is used by all modern column-oriented databases. Combine the compression techniques with other metadata like max, min, avg, mean, null bloom filters, and more that is stored with each partition (group of X number of rows per column compressed together) and you can actually skip reading any data at all for many aggregation queries.