clintropolis opened a new pull request #8822: optimize numeric column null value checking for low filter selectivity (more rows) URL: https://github.com/apache/incubator-druid/pull/8822 ### Description I would like to add documentation for Druid SQL compatible null handling added in #4349 to the website, in part because it has been merged for quite a while now, but also so that we can feel better about the changes #8566 causes in SQL behavior in Druids native mode (tl;dr some calcite optimizations lead to some query incompatibilities specifically around our treatment of `''` and `null` as equivalent). Part of like.. being responsible and stuff, before adding this documentation I first wanted to collect some data to determine if it _was a good idea to in fact document it at this time_. The place I was specifically worried about was the `isNull` check, so I added a benchmark, `NullHandlingBitmapGetVsIteratorBenchmark`, and ran some experiments to see what to expect as well as if we could do better. The nature of selectors lends itself to using a bitmap iterator as an alternative to calling bitmap.get for every `isNull` check, so I first tested `get` vs `iterator` with various null bitmap densities and filter selectivities to simulate the overhead of having null value handling selector with each approach. I have so far only collected information on roaring, because with `concise` the `get` method would not complete at low selectivity, so I'm assuming it's numbers are quite bad (and more on this later). To help make sense of the numbers collected from this, I created heatmaps to compare the differences between the approaches. With the raw output, these looked something like this which isn't so telling:  Interpolating the data to fill in the gaps yields something a bit prettier, but still not incredibly telling on it's own:  But does start to offer that the iterator is better at dealing with a larger number of rows, diminishing as the density of the bitmap increases. Scaling the data points to estimate the _cost per row_ in nanoseconds provides a much more useful picture, and shows the abysmal performance of using the iterator at super high selectivity (e.g. 0.1% of rows match and are selected) with really dense bitmaps:  However if we truncate the results and compare areas where the `iterator` is better:  to where `get` is better  it does look like the iterator does perform up to 15 `ns per row` better than using `get` when processing a lot of rows. Searching for a way around the limitation, I was unaware that the `IntIterator` for roaring was actually a `PeekableIntIterator` which is an iterator that offers an `advanceIfNeeded` method that allows skipping the iterator ahead to an index. `ConciseSet` actually has a similar method on it's iterator, `skipAllBefore`, which _is used by_ the `contains` method that the `get` of concise uses! This is likely why concise just flat out wouldn't complete the benchmarks when processing a higher number of rows, because every `get` is creating an iterator, skipping to the position, loop checking to see if the iterator contains the index or passes it, and then throwing it away. Adding the 'peekable' iterator to the benchmark had a similar outcome to using the plain iterator,  but without nearly the overhead at high selectivity on dense bitmaps.  It's still worse, but not nearly as bad, no more than 60ns slower per row when processing a small number of rows than get, compared to over 2 microseconds for using the plain iterator. Peekable iterator better:  Get better than peekable iterator:  Finally, to get a handle on the per row cost in nanoseconds of checking for nulls at all, I threw together these animations: get:  iterator:  peekable iterator:  <hr> This PR has: - [x] been self-reviewed. - [x] added unit tests or modified existing tests to cover new code paths. <hr> ##### Key changed/added classes in this PR * `ImmutableBitmap` * `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: us...@infra.apache.org With regards, Apache Git Services --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@druid.apache.org For additional commands, e-mail: commits-h...@druid.apache.org
