You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@pinot.apache.org by "Jackie-Jiang (via GitHub)" <gi...@apache.org> on 2023/09/11 04:24:45 UTC
[GitHub] [pinot] Jackie-Jiang opened a new pull request, #11557: Optimize in clause evaluation
Jackie-Jiang opened a new pull request, #11557:
URL: https://github.com/apache/pinot/pull/11557
#10254 introduced the sort then merge sort algorithm to handle large in clause. It has time complexity of `O(m + n)` with `m` in clause values and `n` dictionary size. If we do not count the fixed sorting cost (amortized because it is done only once), comparing to binary search with complexity of `O(mlogn)`, it can perform much worse when `n >> m`.
This PR optimizes the algorithm to do divide and concur: we binary search the middle value of the in clause, then divide the search into 2 parts, each with half of the in values and dictionary range. Overall the time complexity should be within `O(m)` (when m is large) to `O(mlogn)` (when m is small), but always better than binary search, and at least on par with the merge sort.
Removed the old query option: `inPredicateSortThreshold`
Added 2 query options:
- `inPredicatePreSorted`: indicate that the given in clause is already sorted
- `skipInPredicateSort`: do not sort the in clause values and use vanilla binary search
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] jasperjiaguo commented on pull request #11557: Optimize in clause evaluation
Posted by "jasperjiaguo (via GitHub)" <gi...@apache.org>.
jasperjiaguo commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1718176487
> > can we comment on the performance of this depending on the number of hits
> > for example sorted values length (m) = 1000 dictionary length (n) = 1M
> > What is the performance for each of the following strategy when we vary the hits from 0% match to 100% match.
> >
> > * linear search (mlogn)
> > * merge sort o(m+n)
> > * this PR's divide and conquer o(m) to o(mlogn)
>
> In this specific scenario:
>
> * Regular binary search: O(1000log1M)
> * Merge sort: ~= O(1M)
> * Divide and conquer: O(log1M + 2 * log500k + 4 * log250k + ... + 512 * log2k) ~= O(1000log4k)
So the complexity of divide and conquer is O(log(n) + 2 log(n/2) + ... + m/2 log(n/(m/2))) ~ O(m logn - m logm), so my guess is when m is at the order of sqrt(n), the user would see some benefits if they have pre-sorted entries in the in clause? If the entries are not pre-sorted then sorting it on user side (O(m logm)) is probably not necessary
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on pull request #11557: Optimize in clause evaluation
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1718853082
Added a benchmark and here are the results:
Cardinality | Percentage | DivideBS | PlainBS | Scan | Divide vs Plain | Divide vs Scan
-- | -- | -- | -- | -- | -- | --
100 | 1 | 7659947.834 | 7193881.873 | 2590606.363 | 1.064786435 | 2.956816575
100 | 2 | 4527399.93 | 3702032.137 | 2297514.754 | 1.222949927 | 1.970564029
100 | 4 | 2298448.048 | 2219638.52 | 884871.898 | 1.035505569 | 2.59749242
100 | 8 | 1624385.705 | 1188408.158 | 730888.462 | 1.366858427 | 2.22248098
100 | 16 | 789605.698 | 561158.422 | 466697.802 | 1.407099434 | 1.691899329
100 | 32 | 451038.526 | 270074.742 | 414345.056 | 1.670050752 | 1.08855776
100 | 64 | 249953.379 | 145491.186 | 306353.403 | 1.717996711 | 0.8158988167
100 | 100 | 193388.569 | 81558.625 | 252231.273 | 2.371160242 | 0.766711307
1000 | 1 | 673035.271 | 604210.035 | 53069.877 | 1.113909455 | 12.68205824
1000 | 2 | 331272.455 | 296964.057 | 56142.286 | 1.115530473 | 5.900587215
1000 | 4 | 192433.934 | 154232.986 | 53796.693 | 1.247683385 | 3.577058798
1000 | 8 | 120568.939 | 67105.009 | 46336.664 | 1.796720406 | 2.602020271
1000 | 16 | 71785.317 | 33548.834 | 41131.107 | 2.139726138 | 1.745280452
1000 | 32 | 42476.434 | 13445.678 | 33515.651 | 3.159114327 | 1.26736115
1000 | 64 | 22895.909 | 7281.486 | 26235.134 | 3.144400607 | 0.8727193465
1000 | 100 | 16424.202 | 4369.1 | 25628.041 | 3.759172827 | 0.6408684144
10000 | 1 | 56327.402 | 36695.237 | 5402.282 | 1.53500581 | 10.42659417
10000 | 2 | 34808.144 | 19821.462 | 5119.112 | 1.756083583 | 6.799644938
10000 | 4 | 17176.683 | 8525.903 | 4878.576 | 2.014646777 | 3.520839483
10000 | 8 | 7889.65 | 4484.064 | 4283.167 | 1.759486484 | 1.842013165
10000 | 16 | 4291.993 | 2175.905 | 3454.031 | 1.97250937 | 1.242604076
10000 | 32 | 2414.918 | 1111.743 | 2897.232 | 2.172190875 | 0.833525931
10000 | 64 | 1514.006 | 569.737 | 1955.941 | 2.657377 | 0.7740550456
10000 | 100 | 1319.788 | 380.992 | 2126.729 | 3.464083235 | 0.6205717795
100000 | 1 | 3995.728 | 2898.882 | 500.751 | 1.378368626 | 7.979470835
100000 | 2 | 2205.853 | 1299.111 | 496.293 | 1.697971151 | 4.4446587
100000 | 4 | 1309.562 | 752.165 | 453.279 | 1.741056816 | 2.889085971
100000 | 8 | 759.235 | 355.94 | 416.158 | 2.133042086 | 1.824391217
100000 | 16 | 413.461 | 168.189 | 338.497 | 2.45831178 | 1.221461342
100000 | 32 | 210.711 | 74.033 | 234.106 | 2.846176705 | 0.9000666365
100000 | 64 | 103.367 | 38.865 | 134.722 | 2.659642352 | 0.7672614718
100000 | 100 | 70.296 | 24.18 | 96.128 | 2.90719603 | 0.7312749667
1000000 | 1 | 330.142 | 184.781 | 47.947 | 1.786666378 | 6.88556114
1000000 | 2 | 147.552 | 89.482 | 48.158 | 1.648957332 | 3.063914614
1000000 | 4 | 75.214 | 48.161 | 38.61 | 1.561720064 | 1.948044548
1000000 | 8 | 39.693 | 23.755 | 30.018 | 1.670932435 | 1.322306616
1000000 | 16 | 23.65 | 12.317 | 23.324 | 1.920110416 | 1.013977019
1000000 | 32 | 12.367 | 5.821 | 13.327 | 2.124549047 | 0.9279657837
1000000 | 64 | 6.577 | 2.959 | 7.576 | 2.222710375 | 0.8681362196
1000000 | 100 | 4.734 | 1.932 | 5.345 | 2.450310559 | 0.8856875585
As shown above, divide binary search always outperforms plain binary search. When the lookup value percentage is very high (over half of the dictionary), scan start outperforming divide binary search, but not by much.
Based on this, I've decided to keep all 3 algorithms and use divide binary search as the default
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] kishoreg commented on pull request #11557: Optimize in clause evaluation
Posted by "kishoreg (via GitHub)" <gi...@apache.org>.
kishoreg commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1713175842
> @kishoreg All the existing tests will use the new algorithm (it is on by default because it always outperform binary search)
Thats amazing. may be some numbers will help for future references.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] ankitsultana commented on pull request #11557: Optimize in clause evaluation
Posted by "ankitsultana (via GitHub)" <gi...@apache.org>.
ankitsultana commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1714451494
@Jackie-Jiang : are there any latency numbers for comparison? (this PR's approach vs no optimization vs sort then merge-sort)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on pull request #11557: Optimize in clause evaluation
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1714284092
> can we comment on the performance of this depending on the number of hits
>
> for example sorted values length (m) = 1000 dictionary length (n) = 1M
>
> What is the performance for each of the following strategy when we vary the hits from 0% match to 100% match.
>
> * linear search (mlogn)
> * merge sort o(m+n)
> * this PR's divide and conquer o(m) to o(mlogn)
In this specific scenario:
- Regular binary search: O(1000log1M)
- Merge sort: ~= O(1M)
- Divide and conquer: O(log1M + 2 * log500k + 4 * log250k + ... + 512 * log2k) ~= O(1000log4k)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] codecov-commenter commented on pull request #11557: Optimize in clause evaluation
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1713181765
## [Codecov](https://app.codecov.io/gh/apache/pinot/pull/11557?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
> Merging [#11557](https://app.codecov.io/gh/apache/pinot/pull/11557?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) (c7a35ea) into [master](https://app.codecov.io/gh/apache/pinot/commit/f6b29aa0a250fa96a066d568dfbb22900db8b58d?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) (f6b29aa) will **decrease** coverage by `63.07%`.
> The diff coverage is `0.00%`.
```diff
@@ Coverage Diff @@
## master #11557 +/- ##
=============================================
- Coverage 63.07% 0.00% -63.07%
+ Complexity 1109 6 -1103
=============================================
Files 2325 2249 -76
Lines 124772 121048 -3724
Branches 19052 18498 -554
=============================================
- Hits 78696 6 -78690
- Misses 40475 121042 +80567
+ Partials 5601 0 -5601
```
| [Flag](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flags&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [integration](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `<0.01% <0.00%> (ø)` | |
| [integration1](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `<0.01% <0.00%> (ø)` | |
| [integration2](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [java-11](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [java-17](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `<0.01% <0.00%> (-62.94%)` | :arrow_down: |
| [java-20](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [temurin](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `<0.01% <0.00%> (-63.07%)` | :arrow_down: |
| [unittests](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [unittests1](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
| [unittests2](https://app.codecov.io/gh/apache/pinot/pull/11557/flags?src=pr&el=flag&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | `?` | |
Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#carryforward-flags-in-the-pull-request-comment) to find out more.
| [Files Changed](https://app.codecov.io/gh/apache/pinot/pull/11557?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Coverage Δ | |
|---|---|---|
| [...core/operator/filter/predicate/PredicateUtils.java](https://app.codecov.io/gh/apache/pinot/pull/11557?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3QtY29yZS9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3QvY29yZS9vcGVyYXRvci9maWx0ZXIvcHJlZGljYXRlL1ByZWRpY2F0ZVV0aWxzLmphdmE=) | `0.00% <0.00%> (-41.90%)` | :arrow_down: |
| [...segment/index/readers/BaseImmutableDictionary.java](https://app.codecov.io/gh/apache/pinot/pull/11557?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3Qtc2VnbWVudC1sb2NhbC9zcmMvbWFpbi9qYXZhL29yZy9hcGFjaGUvcGlub3Qvc2VnbWVudC9sb2NhbC9zZWdtZW50L2luZGV4L3JlYWRlcnMvQmFzZUltbXV0YWJsZURpY3Rpb25hcnkuamF2YQ==) | `0.00% <0.00%> (-82.44%)` | :arrow_down: |
| [...va/org/apache/pinot/spi/utils/CommonConstants.java](https://app.codecov.io/gh/apache/pinot/pull/11557?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-cGlub3Qtc3BpL3NyYy9tYWluL2phdmEvb3JnL2FwYWNoZS9waW5vdC9zcGkvdXRpbHMvQ29tbW9uQ29uc3RhbnRzLmphdmE=) | `0.00% <ø> (-21.12%)` | :arrow_down: |
... and [1976 files with indirect coverage changes](https://app.codecov.io/gh/apache/pinot/pull/11557/indirect-changes?src=pr&el=tree-more&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)
:mega: We’re building smart automated test selection to slash your CI/CD build times. [Learn more](https://about.codecov.io/iterative-testing/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] xiangfu0 commented on a diff in pull request #11557: Optimize in clause evaluation
Posted by "xiangfu0 (via GitHub)" <gi...@apache.org>.
xiangfu0 commented on code in PR #11557:
URL: https://github.com/apache/pinot/pull/11557#discussion_r1321664612
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/predicate/PredicateUtils.java:
##########
@@ -145,23 +145,26 @@ public static IntSet getDictIdSet(BaseInPredicate inPredicate, Dictionary dictio
}
break;
case STRING:
- if (queryContext == null || values.size() <= Integer.parseInt(queryContext.getQueryOptions()
- .getOrDefault(CommonConstants.Broker.Request.QueryOptionKey.IN_PREDICATE_SORT_THRESHOLD,
- CommonConstants.Broker.Request.QueryOptionValue.DEFAULT_IN_PREDICATE_SORT_THRESHOLD))) {
+ if (queryContext == null || Boolean.parseBoolean(
Review Comment:
If else block is always better, then we can remove this?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] jasperjiaguo commented on pull request #11557: Optimize in clause evaluation
Posted by "jasperjiaguo (via GitHub)" <gi...@apache.org>.
jasperjiaguo commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1718177293
> > can we comment on the performance of this depending on the number of hits
> > for example sorted values length (m) = 1000 dictionary length (n) = 1M
> > What is the performance for each of the following strategy when we vary the hits from 0% match to 100% match.
> >
> > * linear search (mlogn)
> > * merge sort o(m+n)
> > * this PR's divide and conquer o(m) to o(mlogn)
>
> In this specific scenario:
>
> * Regular binary search: O(1000log1M)
> * Merge sort: ~= O(1M)
> * Divide and conquer: O(log1M + 2 * log500k + 4 * log250k + ... + 512 * log2k) ~= O(1000log4k)
@Jackie-Jiang So the complexity of divide and conquer is O(log(n) + 2 log(n/2) + ... + m/2 log(n/(m/2))) ~ O(m logn - m logm), so my guess is when m is at the order of sqrt(n), the user would see some benefits if they have pre-sorted entries in the in clause? If the entries are not pre-sorted then sorting it on user side (O(m logm)) is probably not necessary?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on pull request #11557: Optimize in clause evaluation
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1713156303
@kishoreg All the existing tests will use the new algorithm (it is on by default because it always outperform binary search)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang merged pull request #11557: Optimize in clause evaluation
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang merged PR #11557:
URL: https://github.com/apache/pinot/pull/11557
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] kishoreg commented on pull request #11557: Optimize in clause evaluation
Posted by "kishoreg (via GitHub)" <gi...@apache.org>.
kishoreg commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1713149785
Thanks Jackie. lets add some test case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] kishoreg commented on pull request #11557: Optimize in clause evaluation
Posted by "kishoreg (via GitHub)" <gi...@apache.org>.
kishoreg commented on PR #11557:
URL: https://github.com/apache/pinot/pull/11557#issuecomment-1713175259
can we comment on the performance of this depending on the number of hits
for example sorted values length (m) = 1000
dictionary length (n) = 1M
What is the performance for each of the following strategy when we vary the hits from 0% match to 100% match.
- linear search (mlogn)
- merge sort o(m+n)
- this PR's divide and conquer o(m) to o(mlogn)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org
[GitHub] [pinot] Jackie-Jiang commented on a diff in pull request #11557: Optimize in clause evaluation
Posted by "Jackie-Jiang (via GitHub)" <gi...@apache.org>.
Jackie-Jiang commented on code in PR #11557:
URL: https://github.com/apache/pinot/pull/11557#discussion_r1321836605
##########
pinot-core/src/main/java/org/apache/pinot/core/operator/filter/predicate/PredicateUtils.java:
##########
@@ -145,23 +145,26 @@ public static IntSet getDictIdSet(BaseInPredicate inPredicate, Dictionary dictio
}
break;
case STRING:
- if (queryContext == null || values.size() <= Integer.parseInt(queryContext.getQueryOptions()
- .getOrDefault(CommonConstants.Broker.Request.QueryOptionKey.IN_PREDICATE_SORT_THRESHOLD,
- CommonConstants.Broker.Request.QueryOptionValue.DEFAULT_IN_PREDICATE_SORT_THRESHOLD))) {
+ if (queryContext == null || Boolean.parseBoolean(
Review Comment:
Just want to give it an option to turn it off in case sorting is dominating the latency (very unlikely though, but who knows)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org