Signed-off-by: Ben Pfaff <[email protected]>

Until now, in dbsp::storage::file::writer, the ColumnWriter,
DataBlockBuilder, and IndexBlockBuilder haven't needed to be parameterized
by their key or auxdata types.  An upcoming commit will need that, so this
commit prepares for it by parameterizing them.

This shouldn't affect the storage format.

Signed-off-by: Ben Pfaff <[email protected]>

…ded.

Columns 1 (and greater) in a layer file are essentially B-trees over tuples
(R,K), where R is the row number and K is the key.  Each row in column 0
includes as auxiliary data a range R0..R1 of rows in column 1 (the "row
group"), so R in the B-tree allows that range to be looked up.  Storing
the minimum and maximum keys of child blocks in the index allows efficient
lookup of keys in row groups that span multiple data blocks.

However, when a row group starts at the beginning of a data block, there's
little value in including that key in its index block, because it won't
usually help us to avoid reading the data block.  It only helps if we're
searching for a key less than the minimum, which is rarely the case; more
often, we're iterating through the keys, and usually we're doing nested
iteration through the column-0 keys too, so that we'd typically have to
read the data block for another one of those anyhow.

Similarly, when a row group ends at the end of a data block, there's little
value in including its last key in the index block.

This can be a significant optimization when keys in column 1 are large.

In layer files where each row in column 0 has exactly one row in column 1,
this optimization means that the column-0 index will have no bounds at all.
Other layer files will benefit less.

Signed-off-by: Ben Pfaff <[email protected]>

Until now, any row in column 0 had to have at least one row in column 1.
This commit allows there to instead be none.

Signed-off-by: Ben Pfaff <[email protected]>

Indexed Z-sets are commonly used for updating indexes on primary keys.
For this purpose, each key usually has one value (for insertions and
deletions) or two values (for updates).  Writing this small number of
values to a second column maintained separately in the layer file causes
I/O to additional data blocks.

This commit introduces a new way to store these indexed Z-sets.  With
this commit, when a key has just one or two values, those values are
written inline with the key, which reduces the number of data blocks
that need to be fetched to read a key along with its values.  This
should improve performance.

This commit does drop two performance-oriented features from
FileIndexedZSet: push_cursor() and fetch().  I don't think that either
of these have really been used without explicit enabling via DevTweaks.
If they prove important, then we can figure out how to re-implement
them with the new format.

Signed-off-by: Ben Pfaff <[email protected]>

Add circuit profile metadata for inlined values and omitted bounds.

Signed-off-by: Ben Pfaff <[email protected]>

Signed-off-by: feldera-bot <[email protected]>

mythical-fred left a comment

mythical-fred left a comment