richardstartin edited a comment on pull request #7454:
URL: https://github.com/apache/pinot/pull/7454#issuecomment-926172562
Here are some numbers for this change (run with JDK11 coretto). The
benchmark creates data of a given type and a given distribution, computes the
deciles of the data, and the queries for a range corresponding to the nth
decile. So `_decile=0` means querying for a range from the minimum value in the
segment to the largest value smaller than 90% of the segment. `_decile=5` means
start at the median and match 10% of rows.
For `INT`, `FLOAT`, and `LONG` query time is consistently faster, as is
index build time. Because of the lossless encoding used, `DOUBLE` is slower and
is comparable to the existing range index. Several things could be done about
this
1. Consider a lossy conversion, I don't like this approach and the decision
would need to be made before releasing this, otherwise lossy conversion would
require a new range index version for double columns
2. The data structure in `RoaringBitmap` could be made roughly 2x faster by
evaluating both ranges at once. Currently we pass over the `RangeBitmap` twice,
once for the upper bound, once for the lower bound, and then intersect them.
This could all be done in one pass in the future.
3. The data structure could be evolved to use another base for faster
queries for `DOUBLE` columns, at the expense of using more space. This would be
an easy migration if necessary since the serialisation format in
`RoaringBitmap` is forward compatible.
I recommend not doing anything about `DOUBLE` for now, and adopt this
format, on the basis that option 2 is available.
```
Benchmark (_dataType) (_decile) (_numDocs)
(_scenario) (_seed) Mode Cnt Score Error Units
BenchmarkRangeIndex.queryV1 INT 5 1000000
NORMAL(0,1) 42 avgt 5 6724.390 ± 341.587 us/op
BenchmarkRangeIndex.queryV1 INT 5 1000000
NORMAL(10000000,1000) 42 avgt 5 1679.114 ± 58.021 us/op
BenchmarkRangeIndex.queryV1 INT 5 1000000
EXP(0.0001) 42 avgt 5 1656.115 ± 92.468 us/op
BenchmarkRangeIndex.queryV1 INT 5 1000000
EXP(0.5) 42 avgt 5 2755.567 ± 178.396 us/op
BenchmarkRangeIndex.queryV1 INT 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1664.481 ± 25.965 us/op
BenchmarkRangeIndex.queryV1 INT 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 1833.423 ±
65.662 us/op
BenchmarkRangeIndex.queryV1 INT 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1604.613 ± 36.730 us/op
BenchmarkRangeIndex.queryV1 INT 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 1693.864 ±
11.346 us/op
BenchmarkRangeIndex.queryV1 LONG 5 1000000
NORMAL(0,1) 42 avgt 5 7325.071 ± 326.691 us/op
BenchmarkRangeIndex.queryV1 LONG 5 1000000
NORMAL(10000000,1000) 42 avgt 5 1638.851 ± 13.261 us/op
BenchmarkRangeIndex.queryV1 LONG 5 1000000
EXP(0.0001) 42 avgt 5 1655.873 ± 71.568 us/op
BenchmarkRangeIndex.queryV1 LONG 5 1000000
EXP(0.5) 42 avgt 5 2751.560 ± 264.398 us/op
BenchmarkRangeIndex.queryV1 LONG 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1729.673 ± 42.050 us/op
BenchmarkRangeIndex.queryV1 LONG 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 1832.178 ±
25.334 us/op
BenchmarkRangeIndex.queryV1 LONG 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1630.938 ± 19.844 us/op
BenchmarkRangeIndex.queryV1 LONG 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 1838.097 ±
22.097 us/op
BenchmarkRangeIndex.queryV1 FLOAT 5 1000000
NORMAL(0,1) 42 avgt 5 1671.051 ± 34.408 us/op
BenchmarkRangeIndex.queryV1 FLOAT 5 1000000
NORMAL(10000000,1000) 42 avgt 5 1660.597 ± 39.827 us/op
BenchmarkRangeIndex.queryV1 FLOAT 5 1000000
EXP(0.0001) 42 avgt 5 1748.752 ± 104.994 us/op
BenchmarkRangeIndex.queryV1 FLOAT 5 1000000
EXP(0.5) 42 avgt 5 1653.907 ± 32.989 us/op
BenchmarkRangeIndex.queryV1 FLOAT 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1742.404 ± 153.677 us/op
BenchmarkRangeIndex.queryV1 FLOAT 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 8941.210 ±
362.685 us/op
BenchmarkRangeIndex.queryV1 FLOAT 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1694.232 ± 52.786 us/op
BenchmarkRangeIndex.queryV1 FLOAT 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 8708.284 ±
203.975 us/op
BenchmarkRangeIndex.queryV1 DOUBLE 5 1000000
NORMAL(0,1) 42 avgt 5 1741.052 ± 31.400 us/op
BenchmarkRangeIndex.queryV1 DOUBLE 5 1000000
NORMAL(10000000,1000) 42 avgt 5 1806.929 ± 107.558 us/op
BenchmarkRangeIndex.queryV1 DOUBLE 5 1000000
EXP(0.0001) 42 avgt 5 1777.536 ± 72.958 us/op
BenchmarkRangeIndex.queryV1 DOUBLE 5 1000000
EXP(0.5) 42 avgt 5 1781.936 ± 16.409 us/op
BenchmarkRangeIndex.queryV1 DOUBLE 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1717.138 ± 21.024 us/op
BenchmarkRangeIndex.queryV1 DOUBLE 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 1826.421 ±
113.665 us/op
BenchmarkRangeIndex.queryV1 DOUBLE 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1776.522 ± 46.617 us/op
BenchmarkRangeIndex.queryV1 DOUBLE 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 1733.831 ±
22.657 us/op
BenchmarkRangeIndex.queryV2 INT 5 1000000
NORMAL(0,1) 42 avgt 5 167.473 ± 6.449 us/op
BenchmarkRangeIndex.queryV2 INT 5 1000000
NORMAL(10000000,1000) 42 avgt 5 607.574 ± 2.534 us/op
BenchmarkRangeIndex.queryV2 INT 5 1000000
EXP(0.0001) 42 avgt 5 761.198 ± 9.089 us/op
BenchmarkRangeIndex.queryV2 INT 5 1000000
EXP(0.5) 42 avgt 5 357.203 ± 2.710 us/op
BenchmarkRangeIndex.queryV2 INT 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 832.929 ± 17.764 us/op
BenchmarkRangeIndex.queryV2 INT 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 309.349 ±
2.834 us/op
BenchmarkRangeIndex.queryV2 INT 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 835.358 ± 16.465 us/op
BenchmarkRangeIndex.queryV2 INT 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 308.966 ±
3.106 us/op
BenchmarkRangeIndex.queryV2 LONG 5 1000000
NORMAL(0,1) 42 avgt 5 160.306 ± 9.662 us/op
BenchmarkRangeIndex.queryV2 LONG 5 1000000
NORMAL(10000000,1000) 42 avgt 5 607.199 ± 11.274 us/op
BenchmarkRangeIndex.queryV2 LONG 5 1000000
EXP(0.0001) 42 avgt 5 761.519 ± 7.005 us/op
BenchmarkRangeIndex.queryV2 LONG 5 1000000
EXP(0.5) 42 avgt 5 339.800 ± 3.553 us/op
BenchmarkRangeIndex.queryV2 LONG 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1686.816 ± 112.211 us/op
BenchmarkRangeIndex.queryV2 LONG 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 309.759 ±
3.846 us/op
BenchmarkRangeIndex.queryV2 LONG 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1627.157 ± 37.182 us/op
BenchmarkRangeIndex.queryV2 LONG 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 310.557 ±
8.902 us/op
BenchmarkRangeIndex.queryV2 FLOAT 5 1000000
NORMAL(0,1) 42 avgt 5 926.658 ± 35.276 us/op
BenchmarkRangeIndex.queryV2 FLOAT 5 1000000
NORMAL(10000000,1000) 42 avgt 5 820.031 ± 33.360 us/op
BenchmarkRangeIndex.queryV2 FLOAT 5 1000000
EXP(0.0001) 42 avgt 5 1362.855 ± 22.333 us/op
BenchmarkRangeIndex.queryV2 FLOAT 5 1000000
EXP(0.5) 42 avgt 5 738.290 ± 18.907 us/op
BenchmarkRangeIndex.queryV2 FLOAT 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1331.245 ± 40.306 us/op
BenchmarkRangeIndex.queryV2 FLOAT 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 24.028 ±
0.687 us/op
BenchmarkRangeIndex.queryV2 FLOAT 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 1328.662 ± 29.253 us/op
BenchmarkRangeIndex.queryV2 FLOAT 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 24.437 ±
0.335 us/op
BenchmarkRangeIndex.queryV2 DOUBLE 5 1000000
NORMAL(0,1) 42 avgt 5 1811.274 ± 47.818 us/op
BenchmarkRangeIndex.queryV2 DOUBLE 5 1000000
NORMAL(10000000,1000) 42 avgt 5 2006.414 ± 43.702 us/op
BenchmarkRangeIndex.queryV2 DOUBLE 5 1000000
EXP(0.0001) 42 avgt 5 2635.751 ± 61.159 us/op
BenchmarkRangeIndex.queryV2 DOUBLE 5 1000000
EXP(0.5) 42 avgt 5 1797.613 ± 99.108 us/op
BenchmarkRangeIndex.queryV2 DOUBLE 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 2491.316 ± 106.713 us/op
BenchmarkRangeIndex.queryV2 DOUBLE 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 1049.657 ±
26.725 us/op
BenchmarkRangeIndex.queryV2 DOUBLE 5 1000000
UNIFORM(0,100000000000) 42 avgt 5 2616.917 ± 258.422 us/op
BenchmarkRangeIndex.queryV2 DOUBLE 5 1000000
UNIFORM(100000000000, 100000000100) 42 avgt 5 1049.279 ±
13.951 us/op
BenchmarkRangeIndex.createV1 INT N/A 1000000
NORMAL(0,1) 42 ss 5 113182.901 ± 67834.528 us/op
BenchmarkRangeIndex.createV1 INT N/A 1000000
NORMAL(10000000,1000) 42 ss 5 375338.881 ± 6212.163 us/op
BenchmarkRangeIndex.createV1 INT N/A 1000000
EXP(0.0001) 42 ss 5 436650.473 ± 7519.528 us/op
BenchmarkRangeIndex.createV1 INT N/A 1000000
EXP(0.5) 42 ss 5 137547.093 ± 4648.473 us/op
BenchmarkRangeIndex.createV1 INT N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 546988.945 ± 22817.827 us/op
BenchmarkRangeIndex.createV1 INT N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 287844.486 ±
104651.014 us/op
BenchmarkRangeIndex.createV1 INT N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 538891.335 ± 64592.288 us/op
BenchmarkRangeIndex.createV1 INT N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 292665.860 ±
39843.334 us/op
BenchmarkRangeIndex.createV1 LONG N/A 1000000
NORMAL(0,1) 42 ss 5 113853.468 ± 10754.627 us/op
BenchmarkRangeIndex.createV1 LONG N/A 1000000
NORMAL(10000000,1000) 42 ss 5 386002.879 ± 13724.519 us/op
BenchmarkRangeIndex.createV1 LONG N/A 1000000
EXP(0.0001) 42 ss 5 442085.193 ± 14979.299 us/op
BenchmarkRangeIndex.createV1 LONG N/A 1000000
EXP(0.5) 42 ss 5 146690.531 ± 9511.060 us/op
BenchmarkRangeIndex.createV1 LONG N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 574195.880 ± 7166.069 us/op
BenchmarkRangeIndex.createV1 LONG N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 283517.626 ±
5951.661 us/op
BenchmarkRangeIndex.createV1 LONG N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 554756.767 ± 12630.176 us/op
BenchmarkRangeIndex.createV1 LONG N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 285294.799 ±
7490.806 us/op
BenchmarkRangeIndex.createV1 FLOAT N/A 1000000
NORMAL(0,1) 42 ss 5 475590.610 ± 17834.880 us/op
BenchmarkRangeIndex.createV1 FLOAT N/A 1000000
NORMAL(10000000,1000) 42 ss 5 350757.276 ± 28081.516 us/op
BenchmarkRangeIndex.createV1 FLOAT N/A 1000000
EXP(0.0001) 42 ss 5 482675.137 ± 52474.766 us/op
BenchmarkRangeIndex.createV1 FLOAT N/A 1000000
EXP(0.5) 42 ss 5 477357.549 ± 25480.646 us/op
BenchmarkRangeIndex.createV1 FLOAT N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 476962.173 ± 20946.250 us/op
BenchmarkRangeIndex.createV1 FLOAT N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 66718.894 ±
12363.014 us/op
BenchmarkRangeIndex.createV1 FLOAT N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 483928.163 ± 46663.945 us/op
BenchmarkRangeIndex.createV1 FLOAT N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 69877.679 ±
17961.117 us/op
BenchmarkRangeIndex.createV1 DOUBLE N/A 1000000
NORMAL(0,1) 42 ss 5 478620.142 ± 23063.686 us/op
BenchmarkRangeIndex.createV1 DOUBLE N/A 1000000
NORMAL(10000000,1000) 42 ss 5 489118.331 ± 23570.345 us/op
BenchmarkRangeIndex.createV1 DOUBLE N/A 1000000
EXP(0.0001) 42 ss 5 494501.923 ± 49732.437 us/op
BenchmarkRangeIndex.createV1 DOUBLE N/A 1000000
EXP(0.5) 42 ss 5 503061.507 ± 103399.593 us/op
BenchmarkRangeIndex.createV1 DOUBLE N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 489518.989 ± 29034.824 us/op
BenchmarkRangeIndex.createV1 DOUBLE N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 488868.489 ±
25696.651 us/op
BenchmarkRangeIndex.createV1 DOUBLE N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 495284.426 ± 26534.459 us/op
BenchmarkRangeIndex.createV1 DOUBLE N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 493155.289 ±
41312.905 us/op
BenchmarkRangeIndex.createV2 INT N/A 1000000
NORMAL(0,1) 42 ss 5 31557.939 ± 1621.705 us/op
BenchmarkRangeIndex.createV2 INT N/A 1000000
NORMAL(10000000,1000) 42 ss 5 153848.542 ± 21056.818 us/op
BenchmarkRangeIndex.createV2 INT N/A 1000000
EXP(0.0001) 42 ss 5 251817.559 ± 9385.519 us/op
BenchmarkRangeIndex.createV2 INT N/A 1000000
EXP(0.5) 42 ss 5 37842.500 ± 2152.924 us/op
BenchmarkRangeIndex.createV2 INT N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 476068.705 ± 8204.144 us/op
BenchmarkRangeIndex.createV2 INT N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 59718.807 ±
3406.474 us/op
BenchmarkRangeIndex.createV2 INT N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 409972.865 ± 10681.709 us/op
BenchmarkRangeIndex.createV2 INT N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 65081.968 ±
2253.144 us/op
BenchmarkRangeIndex.createV2 LONG N/A 1000000
NORMAL(0,1) 42 ss 5 31451.596 ± 2165.520 us/op
BenchmarkRangeIndex.createV2 LONG N/A 1000000
NORMAL(10000000,1000) 42 ss 5 151057.040 ± 13465.482 us/op
BenchmarkRangeIndex.createV2 LONG N/A 1000000
EXP(0.0001) 42 ss 5 250432.339 ± 11397.610 us/op
BenchmarkRangeIndex.createV2 LONG N/A 1000000
EXP(0.5) 42 ss 5 37703.155 ± 1805.054 us/op
BenchmarkRangeIndex.createV2 LONG N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 600135.713 ± 50377.187 us/op
BenchmarkRangeIndex.createV2 LONG N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 67510.670 ±
20257.985 us/op
BenchmarkRangeIndex.createV2 LONG N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 592899.314 ± 10187.439 us/op
BenchmarkRangeIndex.createV2 LONG N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 66523.598 ±
19555.141 us/op
BenchmarkRangeIndex.createV2 FLOAT N/A 1000000
NORMAL(0,1) 42 ss 5 407109.354 ± 5819.103 us/op
BenchmarkRangeIndex.createV2 FLOAT N/A 1000000
NORMAL(10000000,1000) 42 ss 5 232501.197 ± 20092.900 us/op
BenchmarkRangeIndex.createV2 FLOAT N/A 1000000
EXP(0.0001) 42 ss 5 385567.492 ± 5394.826 us/op
BenchmarkRangeIndex.createV2 FLOAT N/A 1000000
EXP(0.5) 42 ss 5 454067.172 ± 5904.919 us/op
BenchmarkRangeIndex.createV2 FLOAT N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 421185.434 ± 9261.012 us/op
BenchmarkRangeIndex.createV2 FLOAT N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 76458.581 ±
3884.131 us/op
BenchmarkRangeIndex.createV2 FLOAT N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 419558.409 ± 7258.182 us/op
BenchmarkRangeIndex.createV2 FLOAT N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 76546.710 ±
1750.497 us/op
BenchmarkRangeIndex.createV2 DOUBLE N/A 1000000
NORMAL(0,1) 42 ss 5 972463.978 ± 26785.075 us/op
BenchmarkRangeIndex.createV2 DOUBLE N/A 1000000
NORMAL(10000000,1000) 42 ss 5 674071.565 ± 36243.218 us/op
BenchmarkRangeIndex.createV2 DOUBLE N/A 1000000
EXP(0.0001) 42 ss 5 861501.424 ± 4628.596 us/op
BenchmarkRangeIndex.createV2 DOUBLE N/A 1000000
EXP(0.5) 42 ss 5 915558.381 ± 16495.181 us/op
BenchmarkRangeIndex.createV2 DOUBLE N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 871729.294 ± 10802.879 us/op
BenchmarkRangeIndex.createV2 DOUBLE N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 458504.991 ±
7541.249 us/op
BenchmarkRangeIndex.createV2 DOUBLE N/A 1000000
UNIFORM(0,100000000000) 42 ss 5 860718.749 ± 24117.249 us/op
BenchmarkRangeIndex.createV2 DOUBLE N/A 1000000
UNIFORM(100000000000, 100000000100) 42 ss 5 466381.706 ±
56695.081 us/op
```
--
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: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
