Module sketch 

Counting distinct values, and deciding whether two columns are related, without holding either column in memory.

Every decision in spec/06-compression.md section 6.4 and 6.5 starts with a question about a column that is too big to answer exactly. Is this column worth a dictionary, which is a distinct count. Do these two columns come from the same universe, which is an overlap between two value sets. Is this column determined by that one, which is whether the pairs have as many distinct values as the left side alone. Section 6.4 also says the pair space has to be pruned, because 105 columns is 5,460 pairs and testing all of them exactly is not something a load can do.

A bottom-k sketch answers all three from one pass per column and a fixed amount of memory.

What it is

Hash every value and keep the k smallest distinct hashes. That set is a uniform random sample of the column’s distinct values, chosen by a rule that does not depend on the order they arrived in, so two sketches built on different machines from the same values are identical.

The distinct count comes out of where the k smallest hashes end. If the hashes are uniform over the 64 bit range, then after seeing d distinct values the kth smallest sits at about k / d of the way through the range, so d is about k divided by that fraction. The standard correction uses k - 1 rather than k, which is what makes the estimate unbiased rather than merely close. Relative error is about one over the square root of k, so the default k of 4096 is a bit under 2 percent, and a sketch that never filled up is not an estimate at all because then it holds every distinct hash there was.

The overlap between two columns comes from merging the two sketches and asking how many of the k smallest hashes of the union are in both. That is the Jaccard similarity, and the reason it works on sketches is that any hash small enough to be in the union’s bottom k is small enough that if it were in a column at all it would be in that column’s own bottom k. So a lookup in the sketch is a lookup in the column.

Why not HyperLogLog

Section 6.5 says HyperLogLog for the distinct count and that is the right structure if counting is all you want, because it answers in a kilobyte where this wants tens. It cannot do the other two questions. A HyperLogLog register holds a leading zero count and not a value, so two HyperLogLogs can be merged into a count of the union but they cannot tell you which values the union kept, and the intersection they give by inclusion and exclusion is the difference of three noisy numbers, which for two columns that barely overlap is noise. The sketch here keeps actual hashes, so an intersection is a set intersection and the error on it is the error on the sample rather than the error on the difference. 32 KB per column at the default k, for 105 columns, is 3 MB for a whole table, and the pair pruning it buys is worth more than the 3 MB.

The hash

Values are hashed with a multiply and fold over 8 byte words. This is a sketching hash and not a persisted one: nothing on disk depends on it, so it can be replaced with something faster without a format version. What it does have to be is uniform, because every estimate here assumes it is, and the tests measure that rather than asserting it.

Structs

Sketch

A bottom-k sketch of the distinct values of a column.

Constants

DEFAULT_K

The default number of hashes to keep, which puts the relative error a bit under 2 percent.

Functions

dependence

How close a column is to being determined by another one, from a sketch of the left column and a sketch of the two of them paired.

hash64

The hash used by every sketch here.

pair_hash

The hash of two values as a pair, for dependence.

pair_of

The same pair hash for two values whose hashes are already known.