You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@druid.apache.org by GitBox <gi...@apache.org> on 2020/08/24 06:08:43 UTC
[GitHub] [druid] suneet-s opened a new pull request #10313: Make NUMERIC_HASHING_THRESHOLD configurable
suneet-s opened a new pull request #10313:
URL: https://github.com/apache/druid/pull/10313
### Description
Change the default numeric hashing threshold to 1 and make it configurable.
Benchmarks attached to this PR show that binary searches are not more faster
than doing a set contains check. The attached flamegraph shows the amount of
time a query spent in the binary search. Given the benchmarks, we can expect
to see roughly a 2x speed up in this part of the query which works out to
~ a 20% faster query in this instance.
<img width="1668" alt="Screen Shot 2020-08-23 at 10 38 55 PM" src="https://user-images.githubusercontent.com/44787917/91008091-72122880-e592-11ea-9b88-e9d9943201d6.png">
In this flamegraph, a query is taking ~40% of the time doing a binary search on 4 numbers. The query I used
is not very selective, so it has to do the binary search many times.
I see a comment on `NUMERIC_HASHING_THRESHOLD` that talks about benchmarks, but I couldn't find any
in the codebase, so I wrote my own hacky ones, just to get a sense for the breaking points. The benchmarks
probably need a lot of work, and the results should be taken with a grain of salt because I ran most of them
only 10 times to calculate the average time.
I tried 3 algorithms: binary search, set contains and a linear search (using LongArraySet as a proxy)
Here's a summary of the results. The results are in ns / operation with a 20% match rate with the match being chosen at random within the list of filter values.
Algorithm | 16 | 8 | 4 | 2 |
---------- | -- |-- | -- | -- |
BinarySearch | 7.883 | 4.451 | 3.750 | 4.71
LongOpenHashSet | 3.086 | 3.142 | 3.071 | 4.02
LongArraySet | 9.856 | 6.077 | 4.151 | 3.28
I then ran the benchmarks to compare the worst and best case match times for 16 elements in the set
Algorithm | Worst | Best
---------- | -- |--
BinarySearch | 5.401 | 2.991
LongArraySet | 10.985 | 2.908
These numbers seem to indicate that the performance gain of not using a set contains is minimal, even with very small sets and will depend on the number of elements in the dataset that will match the filter.
These numbers seem to indicate that the contains time is relatively consistent at ~ 3.1 ns / op whereas a binary search operation is almost 2ns per op slower.
Based on these numbers, I suspect the query above would see ~ 10% gain by switching to using the LongOpenHashSet instead of a binary search, while queries with in filters closer to 16 values would see a bigger benefit.
<hr>
This PR has:
- [ ] been self-reviewed.
- [ ] using the [concurrency checklist](https://github.com/apache/druid/blob/master/dev/code-review/concurrency.md) (Remove this item if the PR doesn't have any relation to concurrency.)
- [ ] added documentation for new or modified features or behaviors.
- [ ] added Javadocs for most classes and all non-trivial methods. Linked related entities via Javadoc links.
- [ ] added or updated version, license, or notice information in [licenses.yaml](https://github.com/apache/druid/blob/master/licenses.yaml)
- [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader.
- [ ] added unit tests or modified existing tests to cover new code paths, ensuring the threshold for [code coverage](https://github.com/apache/druid/blob/master/dev/code-review/code-coverage.md) is met.
- [ ] added integration tests.
- [ ] been tested in a test Druid cluster.
<!-- Check the items by putting "x" in the brackets for the done things. Not all of these items apply to every PR. Remove the items which are not done or not relevant to the PR. None of the items from the checklist above are strictly necessary, but it would be very helpful if you at least self-review the PR. -->
<hr>
##### Key changed/added classes in this PR
* `MyFoo`
* `OurBar`
* `TheirBaz`
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on pull request #10313: Make NUMERIC_HASHING_THRESHOLD configurable
Posted by GitBox <gi...@apache.org>.
gianm commented on pull request #10313:
URL: https://github.com/apache/druid/pull/10313#issuecomment-679780301
> I see a comment on `NUMERIC_HASHING_THRESHOLD` that talks about benchmarks, but I couldn't find any
> in the codebase
It looks like the code was originally using a `HashSet<Long>`, which would be quite a bit slower than the LongOpenHashSet it uses today.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on a change in pull request #10313: Make NUMERIC_HASHING_THRESHOLD configurable
Posted by GitBox <gi...@apache.org>.
gianm commented on a change in pull request #10313:
URL: https://github.com/apache/druid/pull/10313#discussion_r476609549
##########
File path: processing/src/main/java/org/apache/druid/query/filter/InDimFilter.java
##########
@@ -80,7 +80,8 @@
{
// determined through benchmark that binary search on long[] is faster than HashSet until ~16 elements
// Hashing threshold is not applied to String for now, String still uses ImmutableSortedSet
- public static final int NUMERIC_HASHING_THRESHOLD = 16;
+ public static final int NUMERIC_HASHING_THRESHOLD =
+ Integer.parseInt(System.getProperty("druid.query.filter.inDimFilter.numericHashingThreshold", "1"));
Review comment:
> One of those must be wrong 😅
SelectorDimFilter calls `new InDimFilter(dimension, Collections.singleton(value), extractionFn, filterTuning).optimize()`, so you get another SelectorDimFilter back 🙂
There's no comment about why, but I assume it's because InDimFilter has the `optimizeLookup()` code.
> I put the default in mainly because of my paranoia, just in case this causes a perf degradation for a specific shape of query that isn't covered by my benchmarks.
People generally aren't going to have the patience to research each of these settings, so it's usually better if we do some diligence to find something that should work (relatively) universally. If that involves removing code paths then it also helps us reduce the amount of code that needs to be tested.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] suneet-s commented on a change in pull request #10313: Make NUMERIC_HASHING_THRESHOLD configurable
Posted by GitBox <gi...@apache.org>.
suneet-s commented on a change in pull request #10313:
URL: https://github.com/apache/druid/pull/10313#discussion_r476501925
##########
File path: processing/src/main/java/org/apache/druid/query/filter/InDimFilter.java
##########
@@ -80,7 +80,8 @@
{
// determined through benchmark that binary search on long[] is faster than HashSet until ~16 elements
// Hashing threshold is not applied to String for now, String still uses ImmutableSortedSet
- public static final int NUMERIC_HASHING_THRESHOLD = 16;
+ public static final int NUMERIC_HASHING_THRESHOLD =
+ Integer.parseInt(System.getProperty("druid.query.filter.inDimFilter.numericHashingThreshold", "1"));
Review comment:
ha I didn't look at the optimize code in the `InDimFilter` before.
`SelectorDimFilter.optimize()` produces an `InDimFilter` and `InDimFilter.optimize()` produces a `SelectorDimFilter`. One of those must be wrong 😅
Either way, it probably doesn't make a difference with 1 element.
I put the default in mainly because of my paranoia, just in case this causes a perf degradation for a specific shape of query that isn't covered by my benchmarks. I'll run them a few more times and then just drop this code path.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] fjy merged pull request #10313: Remove NUMERIC_HASHING_THRESHOLD
Posted by GitBox <gi...@apache.org>.
fjy merged pull request #10313:
URL: https://github.com/apache/druid/pull/10313
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm edited a comment on pull request #10313: Make NUMERIC_HASHING_THRESHOLD configurable
Posted by GitBox <gi...@apache.org>.
gianm edited a comment on pull request #10313:
URL: https://github.com/apache/druid/pull/10313#issuecomment-679780301
> I see a comment on `NUMERIC_HASHING_THRESHOLD` that talks about benchmarks, but I couldn't find any
> in the codebase
It looks like the code was originally using a `HashSet<Long>`, which would be quite a bit slower than the LongOpenHashSet it uses today, so the original benchmarks aren't valid anymore.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm edited a comment on pull request #10313: Make NUMERIC_HASHING_THRESHOLD configurable
Posted by GitBox <gi...@apache.org>.
gianm edited a comment on pull request #10313:
URL: https://github.com/apache/druid/pull/10313#issuecomment-679780301
> I see a comment on `NUMERIC_HASHING_THRESHOLD` that talks about benchmarks, but I couldn't find any
> in the codebase
It looks like the code was originally using a `HashSet<Long>`, which would be quite a bit slower than the LongOpenHashSet it uses today. I'd trust your new benchmarks instead.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org
[GitHub] [druid] gianm commented on a change in pull request #10313: Make NUMERIC_HASHING_THRESHOLD configurable
Posted by GitBox <gi...@apache.org>.
gianm commented on a change in pull request #10313:
URL: https://github.com/apache/druid/pull/10313#discussion_r476192895
##########
File path: processing/src/main/java/org/apache/druid/query/filter/InDimFilter.java
##########
@@ -80,7 +80,8 @@
{
// determined through benchmark that binary search on long[] is faster than HashSet until ~16 elements
// Hashing threshold is not applied to String for now, String still uses ImmutableSortedSet
- public static final int NUMERIC_HASHING_THRESHOLD = 16;
+ public static final int NUMERIC_HASHING_THRESHOLD =
+ Integer.parseInt(System.getProperty("druid.query.filter.inDimFilter.numericHashingThreshold", "1"));
Review comment:
I don't think we should have a property for this, but if we did, it should be set through Guice injection rather than through System.getProperty. That way, it'd work in either a runtime props file or a system property.
We won't actually see "1" in practice AFAIK, since `optimize()` will get run, and that'll turn the In filter into a Selector filter.
So if this is the right default, I think it'd be better to remove the code.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@druid.apache.org
For additional commands, e-mail: commits-help@druid.apache.org