When the same string ID meant two different things

Version 1.0.11 is on NuGet, one day after 1.0.10. There is one thing in it, and it is not a speedup: GroupBy and Pivot were returning wrong answers on DFC files that span more than one segment.

If you group over a .dfc file that you have appended to over time, please take this one.

What it looked like

Three things went wrong, and each one looked like its own bug. Group counts came back too high, so a column with ten distinct values could report sixteen groups. Strings turned up in the wrong place, so a query grouped by country could hand you a product ID. And rows from later in the file were counted into the wrong category.

That last part is what bothers me. A wrong total from a grouping query is the worst kind of bug to ship, because nothing throws. The result has the right shape, the right column names, and numbers that look believable.

What was actually wrong

String columns in DFC are dictionary encoded. The column stores integer IDs, and the file carries a table that maps each ID back to its string. IDs start at 1, and 0 is reserved for null. It is a cheap trade: a fixed-width uint32 per row instead of a length and a pile of bytes per row.

The catch is that the table is per segment. A DFC file is a sequence of segments, each written independently, each numbering its own strings from 1. Segment 0 might map 1 to "Apple" and 2 to "Banana". Segment 1, written later from different data, maps 1 to "Cherry" and 2 to "Date".

GroupBy and Pivot read the ID column across the whole file and looked every ID up in the first segment's table. So segment 1's "Cherry" rows came back as "Apple".

Why nobody caught it sooner

A single-segment file cannot hit this. One table, so a local ID is already the right ID. Most files written in one SaveAsync call are one segment, and every test that wrote its data in one pass passed.

You get segments when the data goes past the configured segment size, and when repeated AppendAsync calls roll a new one. Both of those mean a file that has grown over time, which is exactly the file where a wrong total is least likely to catch anyone's eye.

The fix

Reads that cross segments now go through one global string table that covers the whole file, built the first time it is needed and cached after that. It walks each segment's table in turn, removes duplicate values, and maps (segment, local ID) to a single global ID. Two segments holding "Apple" share an ID. Two segments using local ID 1 for different strings do not.

The segmented reader picked up GetGlobalStringId and ResolveGlobalStringId, and the grouping and pivot paths now pass the segment index along with the ID. Single-segment files short-circuit the whole thing: the global ID is the local ID, and no table gets built.

Checking it yourself

The shortest way to reproduce it is to force two segments out of four rows by setting the segment size to one byte, so each append rolls a new one. Both segments then use local IDs 1 and 2 for different strings.

var options = new VelocityOptions
{
    TargetSegmentSizeBytes = 1,
    MaxSegmentSizeBytes = 1,
    AutoCompactionEnabled = false
};

var first = new DataBlock();
first.AddColumn(new DataColumn("Category", typeof(string)));
first.AddColumn(new DataColumn("Value", typeof(int)));
first.AddRow(new object[] { "Apple", 1 });
first.AddRow(new object[] { "Banana", 2 });

var second = new DataBlock();
second.AddColumn(new DataColumn("Category", typeof(string)));
second.AddColumn(new DataColumn("Value", typeof(int)));
second.AddRow(new object[] { "Cherry", 3 });
second.AddRow(new object[] { "Date", 4 });

var block = await VelocityDataBlock.SaveAsync("categories.dfc", first, options);
await block.AppendAsync(second);
block.Dispose();

using var reopened = new VelocityDataBlock("categories.dfc", options);

DataBlock groups = reopened
    .GroupByAggregate("Category", "Value", AggregationType.Sum)
    .Execute();

Console.WriteLine(groups.RowCount);   // 4, one per category

Four rows, four categories, and a sum_Value of 1, 2, 3 and 4. Before the fix this came back as two groups. Pivot checks the same way: pivot on a string column whose values differ between segments, and every distinct value should get a column of its own.

What I take from it

Dictionary encoding is still a good trade. Swapping a repeated string for a uint32 takes a string column from roughly twelve bytes per row down to a little over four, and it lets an equality filter compare integers instead of characters.

The part that bit me is that an ID only means something next to the table that handed it out. While the file is one piece, you never notice. Split it into pieces that are written separately and the ID is only half of an identity, so every read that crosses a boundary has to carry the other half with it.

Getting it

dotnet add package Datafication.Storage.Velocity

If you run GroupBy or Pivot over a .dfc file built from more than one append, this is worth updating for today. The details are in the changelog, and the query work that shipped the day before is in faster Velocity queries, and one API removed.