groupBy with subtotalsSpec doesn't fully group each set

[gianm]

These two queries (if posed in GroupByQueryRunnerTest) return different results, but I think they should return the same results. The only difference between query 1 and query 2 is that query 2 has an additional dimension that is not referenced in the subtotalsSpec.

I believe the issue is that GroupByStrategyV2.processSubtotalsSpec calls mergeResults on rows returned by GroupByRowProcessor.getRowsFromGrouper for each subtotal dimension list, but this isn't enough to fully group them. The result rows from the grouper are sorted based on the original dimension set, and mergeResults only merges adjacent rows.

i.e. Imagine you have two dimensions and they each have values A, B, and C. The original grouper might have rows like this:

AA
AB
BA
BB

Passing "dimsToInclude" with just the second dim would yield these rows from the Grouper:

A
B
A
B

Which cannot be merged by mergeResults.

I can think of a couple of fixes:

1. Re-sorting the Grouper rows each time they are pulled out. However, not all Groupers support re-sorting (e.g. SpillingGrouper cannot change its sort order once it has spilled to disk) so it might not always be possible.
2. Using two Groupers (with two merge buffers), one to store the initially grouped rows and one to store subtotal groupings. The act of adding results to the subtotal Grouper will properly and fully group them. Takes more memory but should work in all cases.

Query 1:

    GroupByQuery query = makeQueryBuilder()
        .setDataSource(QueryRunnerTestHelper.dataSource)
        .setQuerySegmentSpec(QueryRunnerTestHelper.firstToThird)
        .setDimensions(
            ImmutableList.of(
                new DefaultDimensionSpec("market", "market")
            )
        )
        .setAggregatorSpecs(Collections.singletonList(QueryRunnerTestHelper.rowsCount))
        .setGranularity(QueryRunnerTestHelper.allGran)
        .setSubtotalsSpec(ImmutableList.of(ImmutableList.of("market")))
        .build();

Query 2:

    GroupByQuery query = makeQueryBuilder()
        .setDataSource(QueryRunnerTestHelper.dataSource)
        .setQuerySegmentSpec(QueryRunnerTestHelper.firstToThird)
        .setDimensions(
            ImmutableList.of(
                new DefaultDimensionSpec("quality", "quality"),
                new DefaultDimensionSpec("market", "market")
            )
        )
        .setAggregatorSpecs(Collections.singletonList(QueryRunnerTestHelper.rowsCount))
        .setGranularity(QueryRunnerTestHelper.allGran)
        .setSubtotalsSpec(ImmutableList.of(ImmutableList.of("market")))
        .build();

/cc @himanshug

[himanshug]

thanks, yes that sounds correct.

I think current code "works" as long as first dimension from top level is included in the subtotal spec . That could be treated as a special optimized case and could use existing code path.

(2) should work in all cases.

We should do above to fix the bug.

then, following optimizations could be done...

• many users wouldn't enable disk spilling(or there wouldn't be enough data to require disk writes) , we could detect both these cases and use (1) here

• sorting is retained as long as first dim is included . Let say, top level dimensions are [d1, d2, d3, d4] and subtotal specs are..

[d1, d3] ....can be computed from sorted results on [d1,d2,d3,d4]
[d2, d3] ...can be computed from sorted results on [d2,d3,d4]
[d2, d4] ...can be computed from sorted results on [d2,d3,d4]
optimization would be that for computation of 2nd and 3rd subtotal spec we can put data once inside the grouper for [d2,d3,d4] but this one might not be as important because this doesn't reduce the number of required merge buffers.

are you working on it or would you like me to send the PR to fix it ?

[gianm]

I think current code "works" as long as first dimension from top level is included in the subtotal spec . That could be treated as a special optimized case and could use existing code path.

I think it would need to be a stricter condition. The subtotal spec would need to be a prefix of the dimensions list for the current code to work. Even if it includes the first dimension, if it then skips the second and includes the third, the same issue can happen.

[d1, d3] ....can be computed from sorted results on [d1,d2,d3,d4]
[d2, d3] ...can be computed from sorted results on [d2,d3,d4]
[d2, d4] ...can be computed from sorted results on [d2,d3,d4]

The middle one is true, but the first and last aren't, since the skipping of dimensions means that any later dimensions might not be seen in order.

are you working on it or would you like me to send the PR to fix it ?

I am not working on a fix, I just noticed the problem while working on a different patch.

[himanshug]

thanks, got it.... what was I thinking :)

I will send in a patch soon. I am surprised that my ex-colleagues haven't noticed this , meaning it is mostly being used in the prefix case you described where it "worked" .