Taxonomy tree traversing improvement [LUCENE-5316]

[asfimport]

The taxonomy traversing is done today utilizing the ParallelTaxonomyArrays. In particular, two taxonomy-size int arrays which hold for each ordinal it's (array #1) youngest child and (array #2) older sibling.

This is a compact way of holding the tree information in memory, but it's not perfect:

• Large (8 bytes per ordinal in memory)
• Exposes internal implementation
• Utilizing these arrays for tree traversing is not straight forward
• Lose reference locality while traversing (the array is accessed in increasing only entries, but they may be distant from one another)
• In NRT, a reopen is always (not worst case) done at O(Taxonomy-size)

This issue is about making the traversing more easy, the code more readable, and open it for future improvements (i.e memory footprint and NRT cost) - without changing any of the internals.
A later issue(s?) could be opened to address the gaps once this one is done.

---

Migrated from LUCENE-5316 by Gilad Barkai, updated Nov 24 2013
Attachments: LUCENE-5316.patch (versions: 5)

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

+1 to make the API more "abstract".

It would be nice if the new API could somehow allow for efficiently accommodating "flat" fields, where the only hierarchy is that dim's root (e.g., "Country/", and then all values are immediately under that root.

Another use-case is private ords for certain dimensions (needed for #6372.

Doesn't the current impl consume 3 ints (12 bytes) per ord? (parents, children, siblings)

[asfimport]

Gilad Barkai (migrated from JIRA)

Thanks Mike, you're right on the money.

The ram consumption is indeed an issue here.
I'm not sure that the parent array is used during search at all... and perhaps could be removed (looking into that one as well).
The youngestChild/olderSibing arrays should and could be replaces with either a more compact RAM representation, or at extreme cases, even on-disk.

For a better RAM representation, the idea of a map from ord -> int[] of it's children is a start.
In such a case, we benefit from not holding a 'youngerChild' int for each ordinal in the flat dimension - as they have no children.
2nd, we could benefit from the locality of ref, as all the children are near by and not spread over an array of millions. The non-huge-flat dimensions will no longer suffer because of the other dimensions.
Also, it would make the worst case of NRT the same as the current update (O(Taxo-size)) but might be very small if only a few ordinals were added, as only their 'family' would be reallocated and managed, rather than the entire array.

At a further phase - a compression could be allowed into that int[] of children - we know the children are in ascending order, and could only encode the DGaps, figure the largest DGAP and use packed ints instead of the int[]. It would add some (I hope) minor CPU consumption to the loop, but would benefit greatly when it comes to RAM consumption.
I hope that all the logic could be encapsulated in the ChildrenIterator and the user will benefit from a clean API and better RAM utilization.

I'll post a patch shortly, which covers the very first part - hiding the implementation detail of children arrays (making TaxoReader.getParallelTaxoArrays protected to begin with), and moving TopKFacetResultHandler to use ChildrenIterator.

Currently debugging some nasty loop-as-a-recursion related bug :)

[asfimport]

Gilad Barkai (migrated from JIRA)

TaxonomyReader.getParallelTaxonomyArrays is now protected, the implementation is only on DirectoryTaxonomyReader in which it is protected as well.

Parallel arrays are only used in tests ATM - all tree traversing is done using TaxonomyReader.getChildre(int ordinal) which is now abstract, and implemented in DirTaxoReader.

Mike, if you could please run this patch against the benchmarking maching it would be awesome - as the direct array access is now switched with a method call (iterator's .next()

I hope we will not see any significant degradation.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Thanks Gilad, I ran a performance test, on full English Wikipedia. I
indexed all dims as NO_PARENTS so we exercise visiting all children
(rollup). Also, two flat dims (username, categories) have high
cardinality ... it looks like there is a high fixed cost, because the
relatively easy queries seem to lose the most perf:

                    Task    QPS base      StdDev    QPS comp      StdDev                Pct diff
              AndHighLow       59.93      (2.6%)       44.81      (4.9%)  -25.2% ( -31% -  -18%)
               MedPhrase       42.82      (2.1%)       34.59      (4.1%)  -19.2% ( -24% -  -13%)
                 LowTerm       40.13      (1.8%)       32.68      (3.3%)  -18.6% ( -23% -  -13%)
            OrNotHighLow       33.20      (3.8%)       27.64      (4.2%)  -16.8% ( -23% -   -9%)
                  Fuzzy1       30.74      (1.6%)       26.15      (3.0%)  -14.9% ( -19% -  -10%)
                  Fuzzy2       24.95      (1.8%)       21.78      (2.9%)  -12.7% ( -17% -   -8%)
         LowSloppyPhrase       24.11      (1.2%)       21.22      (2.8%)  -12.0% ( -15% -   -8%)
            OrNotHighMed       19.85      (2.8%)       17.68      (3.4%)  -10.9% ( -16% -   -4%)
             MedSpanNear       17.94      (2.3%)       16.34      (3.4%)   -8.9% ( -14% -   -3%)
              AndHighMed       16.26      (1.3%)       14.88      (2.1%)   -8.4% ( -11% -   -5%)
             AndHighHigh       13.95      (0.9%)       12.91      (1.9%)   -7.4% ( -10% -   -4%)
                 Prefix3       13.24      (1.2%)       12.34      (1.9%)   -6.8% (  -9% -   -3%)
                 MedTerm       12.85      (0.8%)       12.01      (1.8%)   -6.6% (  -9% -   -3%)
           OrNotHighHigh        9.79      (1.5%)        9.29      (2.2%)   -5.1% (  -8% -   -1%)
               LowPhrase        9.50      (5.5%)        9.05      (4.9%)   -4.7% ( -14% -    6%)
                HighTerm        8.65      (1.2%)        8.28      (1.7%)   -4.2% (  -7% -   -1%)
             LowSpanNear        7.40      (3.8%)        7.13      (4.6%)   -3.7% ( -11% -    4%)
            OrHighNotMed        7.19      (1.4%)        6.96      (1.7%)   -3.2% (  -6% -    0%)
               OrHighMed        5.64      (1.3%)        5.51      (1.4%)   -2.3% (  -4% -    0%)
           OrHighNotHigh        4.80      (1.3%)        4.71      (2.1%)   -1.9% (  -5% -    1%)
                Wildcard        4.60      (1.8%)        4.51      (1.5%)   -1.8% (  -5% -    1%)
            OrHighNotLow        4.12      (1.1%)        4.06      (1.5%)   -1.5% (  -3% -    1%)
               OrHighLow        2.81      (1.1%)        2.78      (1.2%)   -1.0% (  -3% -    1%)
            HighSpanNear        3.24      (2.9%)        3.22      (3.0%)   -0.8% (  -6% -    5%)
              OrHighHigh        2.09      (1.1%)        2.08      (1.4%)   -0.6% (  -3% -    1%)
                  IntNRQ        1.50      (1.1%)        1.50      (0.8%)   -0.6% (  -2% -    1%)
         MedSloppyPhrase        3.20      (5.2%)        3.19      (7.0%)   -0.5% ( -11% -   12%)
              HighPhrase        2.73      (6.3%)        2.72      (5.7%)   -0.3% ( -11% -   12%)
                 Respell       52.93      (2.4%)       52.76      (3.2%)   -0.3% (  -5% -    5%)
        HighSloppyPhrase        3.28      (6.9%)        3.32      (9.3%)    1.2% ( -14% -   18%)

Maybe ... we should allow .getChildren to return null when that ord
has no children? I.e., I think the cost might be because are visiting
a great many ords for the "flat" fields.

Separately, perhaps taxo index could tell us when a dim is flat and
then we can avoid doing rollup. Really for such dims, I should index
them as ALL_BUT_DIM, but it'd be nice if I do NO_PARENTS if the facets
code detected that the dim is actually flat and optimized
accordingly...

[asfimport]

Gilad Barkai (migrated from JIRA)

I like the null for ordinals with no siblings. Made the change, and now I'm chasing all the NPEs that it caused, hope to get a new patch up and about soon.

As for allowing the taxo to say the depth for each dim - that's more trickie. Obviously, that's a temporal state, as ever flat dimension can become non flat.
Also figuring this our during search (more like, once per opening the taxo-reader) is o(taxoSize) at the current implementation.

Perhaps, if we're willing to invest a little more time during indexing, we could "roll up" and tell the parents (say, in an incremental numeric field update) "how low can you go" with its children?
In such a case, we could benefit not only from a flat dimension, but whenever an ordinal has no grandchildren. Investing during indexing will make it an O(1) operation.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

Investing during indexing will make it an O(1) operation.

Right, I think it can be very simple for starters: a per-dim boolean isFlat, that we set to false as soon as we see any grandchildren added under that dim (any CategoryPath with more than two components). We could similarly record if ever a dim was multi-valued, but I'm not sure how we can take advantage of that. We'd need to persist this somewhere...

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

Using NO_PARENTS is not that simple decision, since the counts of the parents will be wrong if more than one category of that dimension is added to a document. If it's a flat dimension, and you don't care about the dimension's count, that may be fine. But if it's a hierarchical dimension, the counts of the inner taxonomy nodes will be wrong in that case.

While indexing as NO_PARENTS does exercise the API more, I think it's wrong to test it here. NO_PARENTS should be used only for hierarchical dimensions, in order to save space in the category list and eventually (hopefully) speed things up since less bytes are read and decoded during search. But for flat dimensions, it adds the rollupValues cost. If we make the search code smart to detect this is a flat dimension, we'd save that cost (no need to rollup), but I think in general you should tweak OrdPolicy to NO_PARENTS only for hierarchical dimensions. I wonder what the perf numbers will be if you used NO_PARENTS only for the hierarchical dims - that's what we recommend the users to use, so I think that's what we should benchmark.

I'll review the patch later.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

OK I will re-test, using NO_PARENTS only for the hierarchical field. The problem is, the Wikipedia docs have only one such field, date (Y/M/D), and it's low cardinality.

Actually, Wikipedia does have a VERY big taxonomy but I've never succeeded in extracting it...

So net/net, I will re-test, but I feel this can easily give a false sense of security since my test data does not have a "big" single-valued hierarchical field...

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

How about if you make up a hierarchical category, e.g. charCount/0-100K/0-10K/0-1K/0-100/0-10? If there will be candidates in all ranges, that's 100K nodes. Also, we can hack a hierarchical dimension made up of A-Z/A-Z/A-Z... and randomly assign categories at different levels to documents.

But, NO_PARENTS is not the only way to exercise the API. By asking top-K on a big flat dimension, when we compute the top-K for that dimension we currently traverse all its children, to find which of them has count>0. So the big flat dimensions also make thousands of calls to ChildrenIterator.next().

[asfimport]

Gilad Barkai (migrated from JIRA)

Updated version, iterator now returned as null if ordinal has no children.

I think there are further improvements (a few ifs and a loop check which could be avoided) but at least currently the .next() call is avoided as per Mike's suggestion. Hope this speed things up a bit.

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

Few comments:

• In IntRollupFacetsAggregator.rollupValues, I think we shouldn't recurse if childrenIterator == null, rather than recurse, check for null and return?

  • Same for SumScoreFacetsAggregator.

• TopKFacetResultsHandler - the code checks that kids != null, but as far as I can tell from the patch, it later does childStack[localDepth] = kids, and then later sort of assumes childStack[localDepth] isn't null and calls .next(). Maybe I'm missing the bigger picture (I haven't applied the patch, just reviewing it) and the method exits if there are no children?

  • The same code is executed afterwards with the comment 'push next kid to the stack'.

• TopKInEachNodeHandler:

  • There's a nocommit which I think can be removed as the surrounding lines are commented out
  • Here too I see that ChildrenIterator is assigned to the childStack, and later on it's used, assuming it's not null. Maybe it's safe because you assign ordinalStack[localDepth] = INVALID_ORDINAL, and so the loop doesn't actually gets to use childStack[localDepth]?

• TestDirectoryTaxonomyReader - why did you have to change the declarations from TR to DTR?

Some general comments:

• If we're making changes to the API already, how about if we consolidate getPTA() and getChildren() into a single getTaxonomyTree() (return TaxonomyTree) with, for now, a single getChildren(int ord) API. It can be useful for browsing the taxonomy in general, and the search code can use it too.

  • I don't see where we make use of the parents() API besides tests and DirTaxoWriter.getParent(), but this needs to change too – TaxoWriter does not need to hold a TaxoTree object, only to be able to tell the parent of an ordinal (used when indexing the full path ordinals in the category list.

• I think that we should experiment here with a TaxoTree object which holds the children in a map. Could be that even though the ChildrenIterator may add some overhead, overall we'll see some gains.

  • Also, the title of the issue is about improving the taxonomy tree traversal, so just moving to getChildren() is not exactly an improvement :).
  • We can, if it's too complicated to resolve here, think about how to allow DirTaxoReader extensions to provide their own TaxoTree object in a separate issue.

[asfimport]

Gilad Barkai (migrated from JIRA)

The patch is not ready for commit - I just got a stackoverflow in my head while chasing this NPEs in the loop-as-recursion thing...
Shai, you are right in the sense that we could avoid an extra loop/recursion if the kids are null, but this now works, doesn't throw NPEs in weird places and allows returning null while not calling the extra CI.next().
I'm still looking into that.
I touched the recurring loop as little as possible, as I'm not 100% sure I understand it fully (also, changing a small innocent thing breaks things bad). In the old code there were hidden assumptions which are now no longer true, I traced some but not sure about others.

how about if we consolidate getPTA() and getChildren() into a single getTaxonomyTree()

As for the API change - getPTA is being quietly - though with determination - swapped off. getChildren is all that is left.
I'm not sure .getChildren() should be encapsulated with a TaxononyTree object if it's the only API.
Do you think other API should be put there as well?

I think that we should experiment here with a TaxoTree object which holds the children in a map

The current issue is not yet done, there are still tests to consider and hiding PTA even further from the users' eyes.
I feel that this issue is big enough to stand for itself, while the children map is also large enough? It would contain code for the iterations but also some code in the taxo-reopen phase, that will replace (hopefully ) the PTA reopen code.

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

I'm not sure .getChildren() should be encapsulated with a TaxononyTree object if it's the only API.
Do you think other API should be put there as well?

When I wrote it, I thought it should have a parent(int ord) API as well, but then I changed my mind. I agree that we don't need a TaxoTree with a single API at the moment. Let's stick w/ getChildren. If we'll want to allow overriding how children are represented, we may want to have an internal TaxoTree object, that's not exposed on the public API, but apps can provide their own so we delegate getChildren to it.

I feel that this issue is big enough to stand for itself, while the children map is also large enough? It would contain code for the iterations but also some code in the taxo-reopen phase, that will replace (hopefully ) the PTA reopen code.

I'm not sure, but I don't weigh the issues by the sizes of their patch. If after all this hassle, it turns out that even the map approach severely hurts performance, there's no reason to make any changes to the API. I hope that this won't be the case, but judging from the benchmark Mike ran, this change doesn't look good. I still hope it will look better when we test NO_PARENTS only for the hierarchical dimensions, but we shouldn't make changes to the API if net/net we'll only lose. The RAM consumption of the arrays is not that worrying, since taxonomies are not that large (even a huge taxonomy w/ 2.5M nodes consumes only 30MB!).

So IMO this issue should be about (and it can be done in steps):

1. Abstract the children API and verify this alone doesn't hurt performance. If so, that's great. We should also remove PTA entirely from the API in that case.
2. Experiment with a different in-memory representation - this can be done as a hack even in the current TaxoIndexArrays – when computeChildrenSiblings is called, build a the map. That way you don't need to interfere w/ any reopen logic, it's all internal to TaxoIndexArrays.
   • If we discover that this rep loses performance, we can decide if we want to keep the API abstraction or drop it altogether. But I feel that we need to at least experiment w/ an alternative representation before we change the API. Those API abstractions hurt the performance in the past - let's not make the same mistake again.

[asfimport]

Michael McCandless (@mikemccand) (migrated from JIRA)

How about if you make up a hierarchical category, e.g. charCount/0-100K/0-10K/0-1K/0-100/0-10?

Oh, right, I forgot I already have this hierarchical dim ... but I ran
PrintFacetStats and it only results in 1086 ords (less than date at
3279 ords).

I tested Gilad's latest patch still using NO_PARENTS (change one thing
at a time):

                    Task    QPS base      StdDev    QPS comp      StdDev                Pct diff
              AndHighLow       60.84      (3.5%)       45.81      (0.9%)  -24.7% ( -28% -  -21%)
               MedPhrase       43.63      (2.9%)       35.16      (1.0%)  -19.4% ( -22% -  -15%)
                 LowTerm       40.50      (2.0%)       33.31      (0.9%)  -17.8% ( -20% -  -15%)
            OrNotHighLow       33.70      (4.9%)       28.34      (2.9%)  -15.9% ( -22% -   -8%)
                  Fuzzy1       30.86      (1.9%)       26.61      (0.8%)  -13.8% ( -16% -  -11%)
         LowSloppyPhrase       24.22      (1.7%)       21.51      (0.6%)  -11.2% ( -13% -   -9%)
                  Fuzzy2       25.05      (1.7%)       22.29      (1.0%)  -11.0% ( -13% -   -8%)
            OrNotHighMed       20.09      (3.9%)       18.07      (2.5%)  -10.1% ( -15% -   -3%)
             MedSpanNear       18.16      (2.7%)       16.49      (1.7%)   -9.2% ( -13% -   -4%)
              AndHighMed       16.39      (1.4%)       15.03      (0.9%)   -8.3% ( -10% -   -6%)
             AndHighHigh       14.05      (1.2%)       13.11      (0.7%)   -6.7% (  -8% -   -4%)
               LowPhrase        9.71      (4.6%)        9.06      (4.8%)   -6.6% ( -15% -    2%)
                 Prefix3       13.39      (1.5%)       12.57      (0.8%)   -6.2% (  -8% -   -3%)
                 MedTerm       12.86      (1.1%)       12.11      (1.3%)   -5.8% (  -8% -   -3%)
             LowSpanNear        7.54      (3.8%)        7.19      (3.3%)   -4.7% ( -11% -    2%)
           OrNotHighHigh        9.94      (2.4%)        9.48      (1.5%)   -4.6% (  -8% -    0%)
                HighTerm        8.65      (1.5%)        8.34      (1.4%)   -3.6% (  -6% -    0%)
              HighPhrase        2.81      (5.1%)        2.72      (5.8%)   -3.3% ( -13% -    8%)
            OrHighNotMed        7.23      (1.6%)        7.01      (1.2%)   -3.1% (  -5% -    0%)
               OrHighMed        5.67      (1.9%)        5.52      (0.8%)   -2.7% (  -5% -    0%)
            HighSpanNear        3.26      (3.1%)        3.18      (2.2%)   -2.5% (  -7% -    2%)
           OrHighNotHigh        4.84      (2.1%)        4.73      (1.3%)   -2.4% (  -5% -    1%)
            OrHighNotLow        4.14      (1.3%)        4.05      (1.0%)   -2.1% (  -4% -    0%)
                Wildcard        4.61      (1.4%)        4.52      (1.1%)   -1.8% (  -4% -    0%)
               OrHighLow        2.82      (1.5%)        2.78      (0.7%)   -1.4% (  -3% -    0%)
         MedSloppyPhrase        3.27      (6.2%)        3.23      (7.2%)   -1.2% ( -13% -   13%)
        HighSloppyPhrase        3.39      (6.9%)        3.36      (8.9%)   -0.9% ( -15% -   15%)
              OrHighHigh        2.10      (1.5%)        2.08      (1.0%)   -0.9% (  -3% -    1%)
                  IntNRQ        1.51      (1.3%)        1.50      (0.4%)   -0.5% (  -2% -    1%)
                 Respell       52.58      (2.8%)       53.34      (1.9%)    1.4% (  -3% -    6%)

Curiously, returning null when there are no children didn't seem to
help?

Then I switched all dims to ALL_BUT_DIM (I haven't added per-dim ord
policy control to luceneutil yet):

                    Task    QPS base      StdDev    QPS comp      StdDev                Pct diff
              AndHighLow      103.19      (4.5%)       83.12      (1.2%)  -19.4% ( -24% -  -14%)
               MedPhrase       60.47      (3.8%)       53.05      (1.7%)  -12.3% ( -17% -   -7%)
                 LowTerm       54.28      (3.0%)       48.32      (1.2%)  -11.0% ( -14% -   -7%)
            OrNotHighLow       42.72      (5.3%)       38.99      (4.0%)   -8.7% ( -17% -    0%)
                  Fuzzy1       38.65      (1.9%)       35.70      (1.0%)   -7.6% ( -10% -   -4%)
         LowSloppyPhrase       28.79      (1.8%)       27.02      (1.0%)   -6.2% (  -8% -   -3%)
                  Fuzzy2       29.02      (1.6%)       27.31      (1.2%)   -5.9% (  -8% -   -3%)
             MedSpanNear       20.48      (2.2%)       19.55      (2.3%)   -4.5% (  -8% -    0%)
            OrNotHighMed       22.49      (4.0%)       21.52      (3.3%)   -4.3% ( -11% -    3%)
              AndHighMed       17.94      (1.2%)       17.24      (0.7%)   -3.9% (  -5% -   -2%)
             AndHighHigh       15.04      (1.0%)       14.55      (0.5%)   -3.2% (  -4% -   -1%)
                 Prefix3       14.02      (1.2%)       13.64      (1.0%)   -2.7% (  -4% -    0%)
                 MedTerm       13.47      (1.5%)       13.12      (1.0%)   -2.6% (  -5% -    0%)
               LowPhrase       10.15      (5.5%)        9.94      (5.3%)   -2.1% ( -12% -    9%)
             LowSpanNear        7.82      (3.8%)        7.67      (3.7%)   -1.9% (  -9% -    5%)
                HighTerm        8.83      (1.3%)        8.68      (1.1%)   -1.7% (  -3% -    0%)
           OrNotHighHigh        9.79      (2.0%)        9.63      (1.7%)   -1.6% (  -5% -    2%)
            OrHighNotMed        7.30      (1.7%)        7.22      (1.2%)   -1.1% (  -3% -    1%)
            HighSpanNear        3.27      (1.9%)        3.24      (2.8%)   -0.9% (  -5% -    3%)
               OrHighMed        5.64      (1.6%)        5.59      (1.3%)   -0.9% (  -3% -    2%)
           OrHighNotHigh        4.78      (1.9%)        4.75      (1.5%)   -0.6% (  -3% -    2%)
                Wildcard        4.59      (1.5%)        4.57      (1.4%)   -0.6% (  -3% -    2%)
            OrHighNotLow        4.08      (1.6%)        4.07      (1.5%)   -0.3% (  -3% -    2%)
        HighSloppyPhrase        3.42      (8.7%)        3.42      (8.3%)   -0.2% ( -15% -   18%)
               OrHighLow        2.72      (1.7%)        2.72      (1.5%)   -0.1% (  -3% -    3%)
              OrHighHigh        2.03      (1.8%)        2.03      (1.4%)   -0.0% (  -3% -    3%)
         MedSloppyPhrase        3.30      (6.2%)        3.30      (6.1%)   -0.0% ( -11% -   13%)
                  IntNRQ        1.43      (1.4%)        1.43      (1.2%)   -0.0% (  -2% -    2%)
              HighPhrase        2.74      (5.7%)        2.74      (6.1%)    0.1% ( -10% -   12%)
                 Respell       52.73      (2.5%)       53.18      (3.0%)    0.8% (  -4% -    6%)

Cost is definitely less ... but not "trivial".

Then, I did ALL_BUT_DIM, but only facet on the 7 "easy" dims
(i.e. exclude categories and username):

                    Task    QPS base      StdDev    QPS comp      StdDev                Pct diff
               LowPhrase       12.23      (6.4%)       12.07      (6.0%)   -1.4% ( -12% -   11%)
                 Respell       55.11      (3.1%)       54.44      (2.8%)   -1.2% (  -6% -    4%)
                  Fuzzy1       62.58      (1.6%)       61.95      (1.8%)   -1.0% (  -4% -    2%)
                  Fuzzy2       46.58      (1.5%)       46.17      (1.7%)   -0.9% (  -3% -    2%)
              AndHighLow      402.55      (1.9%)      399.72      (3.2%)   -0.7% (  -5% -    4%)
              HighPhrase        4.01      (8.0%)        3.99      (7.9%)   -0.5% ( -15% -   16%)
               MedPhrase      126.62      (4.6%)      126.18      (4.5%)   -0.3% (  -9% -    9%)
                HighTerm       20.11      (1.5%)       20.06      (1.6%)   -0.3% (  -3% -    2%)
         LowSloppyPhrase       39.10      (1.7%)       39.03      (1.7%)   -0.2% (  -3% -    3%)
                 LowTerm      127.98      (1.9%)      127.81      (2.0%)   -0.1% (  -3% -    3%)
                 Prefix3       28.04      (1.1%)       28.02      (1.3%)   -0.1% (  -2% -    2%)
              AndHighMed       27.39      (0.9%)       27.36      (0.7%)   -0.1% (  -1% -    1%)
             AndHighHigh       25.00      (1.0%)       24.98      (0.7%)   -0.1% (  -1% -    1%)
                 MedTerm       26.14      (1.5%)       26.13      (1.6%)   -0.0% (  -3% -    3%)
                  IntNRQ        2.39      (1.4%)        2.39      (1.5%)    0.0% (  -2% -    2%)
                Wildcard        8.90      (1.7%)        8.90      (1.1%)    0.1% (  -2% -    2%)
            OrHighNotLow        8.52      (1.5%)        8.57      (2.5%)    0.5% (  -3% -    4%)
        HighSloppyPhrase        3.95      (8.5%)        3.98     (12.7%)    0.8% ( -18% -   24%)
              OrHighHigh        3.48      (1.6%)        3.51      (1.6%)    0.8% (  -2% -    4%)
            OrHighNotMed       14.44      (1.6%)       14.57      (1.7%)    0.9% (  -2% -    4%)
               OrHighLow        4.85      (1.6%)        4.90      (1.8%)    0.9% (  -2% -    4%)
               OrHighMed       11.37      (1.4%)       11.48      (1.4%)    1.0% (  -1% -    3%)
             MedSpanNear       25.99      (3.5%)       26.25      (2.8%)    1.0% (  -5% -    7%)
             LowSpanNear        8.84      (4.7%)        8.93      (4.4%)    1.1% (  -7% -   10%)
         MedSloppyPhrase        3.62      (7.0%)        3.67      (8.1%)    1.3% ( -12% -   17%)
            HighSpanNear        4.98      (5.2%)        5.05      (2.9%)    1.3% (  -6% -    9%)
           OrNotHighHigh       14.23      (1.9%)       14.42      (2.0%)    1.4% (  -2% -    5%)
           OrHighNotHigh        8.52      (1.9%)        8.65      (2.0%)    1.5% (  -2% -    5%)
            OrNotHighMed       30.98      (3.8%)       32.05      (4.9%)    3.5% (  -5% -   12%)
            OrNotHighLow       60.16      (5.6%)       62.95      (7.0%)    4.6% (  -7% -   18%)

Which looks like basically noise ... so it's only the high-cardinality
dims that are affected.

[asfimport]

Shai Erera (@shaie) (migrated from JIRA)

Thanks for doing this Mike! (it's not trivial to run all these tests)

The high cardinality dims are affected because we cannot tell quickly which of a dim's children have count>0. The big loss in performance worries me some because these dims are not rare. I wonder if we could return an int[] with only the children of a category, if that improves things or not. That means changing the underlying structure from a large int[] to a Map<ord,int[]> as was suggested before. It still exposes implementation details, but I wonder if that will improve things or not. Also, it might be that if we hold only the children of a dim in the int[], the API abstraction will hurt less.

It sucks that we lose so much because we try to abstract things away.