asfimport
commented
6 years ago Nick Knize (@nknize) (migrated from JIRA)
Initial patch provided:
The lionshare of the changes are made to FieldType, BKDWriter, and BKDReader.
-
FieldType- splitpointDimensionCountinto two new integers that definepointDataDimensionCountandpointIndexDimensionCount.pointIndexDimensionCountmust be <=pointDataDimensionCountand defines the firstndimensions that will be used to build the index. The remainingpointDataDimensionCount-pointIndexDimensionCountdimensions are ignored while building (e.g., split/merge) the index. Getter and Setter utility methods are added. -
BKDWriter- changewriteIndexto encode and writenumIndexDimsin the 2 most significant bytes of the integer that formerly storednumDimsthis provides simple backwards compatability without requiring a change toFieldInfoFormat. Indexing methods are updated to only use the firstnumIndexDimswhile building the tree. Leaf nodes still usenumDataDimsfor efficiently packing and compressing the leaf level data (data nodes). -
BKDReader- add version checking in the constructor to decodenumIndexDimsandnumDataDimsfrom the packed dimension integer. Update index reading methods to only look at the firstnumIndexDimswhile traversing the tree.numDataDimsare still used for decoding leaf level data. -
API Changes - all instances of
pointDimensionCounthave been updated topointDataDimensionCountandpointIndexDimensionCountto reflect total number of dimensions, and number of dimensions used for creating the index, respectively. -
All POINT Tests and POINT based Fields have been updated to use the API changes.
Benchmarking —
To benchmark the changes I update LatLonShape (not included in this patch) and ran benchmark tests both with and without selective indexing. The results are below:
6 dimension encoded LatLonShape w/o selective indexing
INDEX SIZE: 1.2795778876170516 GB READER MB: 1.7928361892700195 BEST M hits/sec: 11.67378231920028 BEST QPS: 6.8635445274291715 for 225 queries, totHits=382688713
7 dimension LatLonShape encoding w/ 4 dimension selective indexing
INDEX SIZE: 2.1509012933820486 GB READER MB: 1.8154268264770508 BEST M hits/sec: 17.018094815004627 BEST QPS: 10.005707519719927 for 225 queries, totHits=382688713
The gains are a little better than the differences between searching a 4d range vs a 6d range. The index size increased due to using 7 dimensions instead of 6, but I also switched over to a bit bigger encoding size.
This issue explores adding a new feature to BKDReader/Writer that enables users to select a fewer number of dimensions to be used for creating the BKD index than the total number of dimensions specified for field encoding. This is useful for encoding dimensional data that is used for interpreting the encoded field data but unnecessary (or not efficient) for creating the index structure. One such example is
LatLonShapeencoding. The first 4 dimensions may be used to to efficiently search/index the triangle using its precomputed bounding box as a 4D point, and the remaining dimensions can be used to encode the vertices of the tessellated triangle. This causes BKD to act much like an R-Tree for shape data where search is distilled into a 4D point (instead of a more expensive 6D point) and the triangle is encoded using a portion of the remaining (non-indexed) dimensions. Fields that use the full data range for indexing are not impacted and behave as they normally would.Migrated from LUCENE-8496 by Nick Knize (@nknize), resolved Oct 18 2018 Attachments: LatLonShape_SelectiveEncoding.patch, LUCENE-8496.patch (versions: 5) Pull requests: https://github.com/apache/lucene-solr/pull/451