Star-tree Optimizations

[Jackie-Jiang]

Problems:

1. Certain predicates (e.g. NOT_EQUAL) can select too many branches, limiting the performance of star-tree
2. Star-tree does not support filters with OR

Potential solutions for 1:

• During aggregation, negate the aggregation result of the non-selected branches from the star node branch. This solution could become complicated for multiple predicates.
• Create a derived column for the predicate result, and apply star-tree on top of it. This solution can only work on the fixed predicate.
• First use inverted index to do the filtering, then use pre-aggregated docs to cover the contiguous selected docs

Potential solution for 2:

• Use bitmap to store the selected docs for each predicate under OR, then union the bitmaps

[atris]

I am working on 2.

[jpohanka]

@atris @Jackie-Jiang Hello, has there been any progress on this ticket ?

[atris]

2 was committed and released a couple of versions back

[jpohanka]

@atris Thank you for the fast response, could you pls point to the release ? I am checking the release notes, but I cannot find the announcement. Thank you.

[Jackie-Jiang]

@jpohanka #7184 contains the OR support on single dimension predicates. Do you need OR support on multiple dimensions for your use case?

[jpohanka]

@Jackie-Jiang Yes, in our use case, we use complex predicates, and the support for multiple dimensions would help greatly.

[atris]

@jpohanka Actually, that would require fundamental changes to the structure of the star tree index, since the current structure would lead to a double counting of certain values for multiple dimensions.

Let me talk to @Jackie-Jiang and get back

[jpohanka]

@atris @Jackie-Jiang Thank you both. Can you share any design docs on how is the star-tree currently implemented in Pinot ?

[Jackie-Jiang]

You may read the star-tree doc to get a high level idea of how star-tree works: https://docs.pinot.apache.org/basics/indexing/star-tree-index?q=star+tree+index

[jpohanka]

Thank you @Jackie-Jiang for the link. What I had in mind was a more low-level design/implementation proposal for the star-tree index. I will try to examine the PRs and the code for a better understanding.