Module setops 

Set algebra, and the choice between probing and merging.

SINTER, SUNION, SDIFF, SINTERCARD and the *STORE forms. This is the family aki lost worst on, at 0.75x for SINTER and 0.30x to 0.55x for the *STORE forms, and 08 section 4 sets the gate at ten times for all of them.

Two ways to do it

Probe. Take the smallest set, and for each of its members ask every other set whether it has it. Work is |smallest| * (k - 1) questions in the worst case, and far fewer in practice because a member that is missing from the second set is never asked about the third. Every question is a random access into a different table.

Accumulate. Walk every member of every set once, into one table that counts how many sets each member appeared in, and then read the answer off the counts. Work is sum(|set|) insertions, all of them into the same table.

K11 pre-registers a crossover at k around 7: below that probe, above it merge. It does not reproduce, and it is worth being exact about why, because the reason is not that the number is a little out.

The crossover is not at seven and there is not one

benches/setops.rs runs both plans over the same sets at k from 2 to 16, with sets of two hundred thousand and nine tenths of every set shared, which is the shape that gives probe the least help. Probe wins at every k. The gap narrows as k grows, from 2.95 times at k equals 2 to 1.24 times at k equals 16, and it narrows towards parity rather than towards a crossing.

The arithmetic says the same thing once the cost of an operation is measured instead of assumed. Probe does n * (k - 1) table operations. Accumulate does n * (k + 1), being one seeding insert and one count raise per member plus the read back. Those are 2.7 and 3.4 million at k equals 16, a ratio of 1.26 against a measured 1.24. Probe does less work at every k and the ratio tends to one from above, so these two never cross.

The pre-registered number assumed a probe question is much dearer than an accumulate touch, because a question is a random access into a table this operation has not otherwise touched and 08 section 4 floors that at about 40 ns on a DRAM miss. Both come out at about 25 ns here. An accumulate touch is not the cheap sequential thing the model had in mind: it hashes the member and makes its own random access, into the counting table. Two random accesses that cost the same cannot trade off against each other, however many of them there are. This is L6’s 70 ns positional probe again, which measured 13.

The third plan, which does change it

08 section 4 describes a merge that is neither of the two above: sorted arrays walked in lockstep, where a touch is a pointer step and a comparison with no hash anywhere. That genuinely is much cheaper than a probe question, and against it a crossover can exist. It was written down as needing the partitioned band and was therefore out of reach.

It is in reach now, from the other direction. An all integer set is an Intset, which is exactly a sorted array, and since #148 it stays one however big it gets rather than turning into a table at five hundred and twelve members. So whenever every operand is an intset there is something to merge, and that is most of what SINTERSTORE is called with: identifier sets, bitmap style tag sets, anything a numeric primary key went into.

Plan::Merge is that, over Walk, and it is why plan_for is a chooser with something to choose. The intersection is a leapfrog driven from the smallest set: take the value that set is on, pull the others up to it with Walk::seek, and if they all land on it then it is in all of them. The seek is what makes the asymmetric case cheap, because a set of ten against a set of a million touches ten members of the big one and skips the rest.

The counting plan stays reachable through inter_with and the benchmark keeps measuring it, because it is the control the merge has to beat.

What the merge is worth, measured

benches/setops.rs builds the same four shapes as integer sets and runs every plan over them. Milliseconds per intersection, minimum per iteration, two hundred thousand members a set:

                       k=2      k=4      k=8     k=16
  dense    merge      3.95     5.15    11.06    23.91
           probe      6.93    11.93    22.63    41.95
           count     16.32    25.91    45.03    84.90
  sparse   merge      0.04     0.06     0.12     0.26
           probe      6.17     6.21     6.38     6.54
  striped  merge      4.70     5.07     5.13     5.27
           probe      7.42     6.43     7.63     7.80
  skewed   merge     0.002    0.003    0.007    0.015
           probe     0.004    0.007    0.013    0.023

And the other three commands, where the merge’s opposite number is the table for the union and the probe for the other two:

                       k=2      k=4      k=8     k=16
  union    merge      1.47     4.35    14.76    54.49
           table     13.30    31.21    69.84   149.82
  diff     merge      4.40     5.16     8.60    15.98
           probe      6.94    10.02    16.65    29.07
  store    merge      7.17    10.36    16.59    29.79
           probe     13.88    23.95    36.69    63.24

The merge wins every row at every k. The narrowest is 1.27 times and the widest is 141, which is a spread wide enough to be worth explaining rather than averaging.

Where the spread comes from, and the shape that nearly broke it

sparse and striped hold the same sets with the same one percent overlap and differ only in where each set’s unshared members sit. In sparse they are in a range of their own, so a cursor that lands in another set’s range steps over the whole range in one binary search. In striped they are interleaved one for one, so there is nothing to skip and a step is worth a single member. That is 141 times against 1.6, on data that is identical by every summary statistic an optimiser could look at. Real data lies between the two and the number to quote is the striped one.

Getting that row right took two goes and it is the reason the shape is in the benchmark. The first merge was symmetric: no set in charge, the largest value any cursor held as the target, every cursor visited in turn. On striped it was nine times slower than the probe at k of 16, and it deserved to be. A symmetric leapfrog costs a step per member of the union of every operand, because proving that nothing matches means looking at everything, and the union is k times the smallest set. The probe reads the smallest set once and fails on its first question, so it is flat in k, which is exactly what sparse_probe and striped_probe do at about 6 to 8 ms across the range.

Driving the leapfrog from the smallest set fixes it, because it puts the merge on the probe’s own bound: a step per member of the smallest operand, plus one per overshoot, over a step that is cheaper than a hash and a random access. striped_merge is 4.70 ms at k of 2 and 5.27 at k of 16, which is the same flatness the probe has with a smaller constant.

So the honest claim is not that the merge is a different order of cost. It is that the merge is never worse than the probe by more than its constant and is sometimes better by two orders, and that the plan is free to take because the representation already sorted the data.

The one row with a slope worth watching is the union, which finds the smallest value by looking at every cursor and is therefore quadratic in k where the table is linear. It wins by 9.1 times at k of 2 and 2.75 at k of 16, and extrapolating the two slopes they would cross somewhere past k of 50. A heap would make it log k at the cost of a comparison per push, and there is no point paying that until a SUNION with fifty keys turns up.

Ordering

A probe or a count returns members in the order the first relevant set holds them, which is insertion order for a listpack or a table and ascending for an intset. A merge returns them ascending. Redis makes no ordering promise for any of these, and picking the order the data is already in means the walk is sequential and there is nothing to sort.

For the intersection and the difference the two agree, because the plan only changes when every operand is an intset and the set being walked is then ascending either way. For the union they do not: the table walks the sets in turn and the merge interleaves them. That is the one place a plan is visible from outside, and it is visible only to a client that was relying on something Redis never promised.

The three representations

The operand is a Set, which is one of three things, and not the element table it used to be. The walked set gives up members through the same Set::iter everything else uses, and the questioned sets answer through Set::has, which is Set::contains with the parse and the hash lifted out into a Needle so they happen once per member rather than once per question.

What that buys is that the algebra never has to know what it is holding. It also means the members cross between representations correctly, which is not automatic: an intset member is a number that has no digits anywhere, and a table stores that same member as its digits, so SINTER ints table only finds anything because the needle carries both forms.

Presizing

The *STORE forms hand the destination a size before they start filling it, taken from the smallest input, which is Y18’s rule and an upper bound on any intersection. 05 section 3.1 wants that to be one arena bump. Until the arena is under this, the destination’s own hint is the same promise with a different allocator behind it.

Structs

Scratch

The tables a set operation fills in on its way to an answer.

Enums

Plan

How to answer a set operation.

Functions

collect

The *STORE forms: run the operation and build the result as a set.

diff

The members of the first set that no later set has.

diff_with

The same, with the plan named rather than assumed. See union_with.

inter

The members every set has, in the order the smallest set holds them.

inter_with

The same, with the plan named rather than assumed.

union

Every member of any of the sets, each once.

union_with

The same, with the plan named rather than assumed.