noria icon indicating copy to clipboard operation
noria copied to clipboard

Detect key subsumption to reduce evictions and index duplications

Open jonhoo opened this issue 5 years ago • 0 comments

If an operator n sources a replay path on [0, 1], and also one on [0], it should be able to satisfy both of these with a single compound index on [0, 1]. Today, it creates two indices instead, since all indices are multi-keyed and not nested. Realizing this kind of key-subsumption also has the potential to reduce the number of join evictions we need to issue, as we know that if a given value is present in the index for [0], we haven't discarded any rows for any value of [1] for that [0], and thus don't need to evict them downstream. Or, said differently, if we miss on a given value for [0, 1], but [0] is present in the index, we know that [0, 1] must be empty.

jonhoo avatar Sep 19 '18 15:09 jonhoo