using lookahead in zkd #14745
Merged
using lookahead in zkd #14745
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
… feature/zkd-index
* Added support for strict comparsion. * Allow unsupported conditions. Correctly display conditions that are strict in explainer. * Fixed some now broken tests. * Apply suggestions from code review Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com>
* Added support for cluster. * Fixing unit tests namespace using.
* Added support for nested fields - excluding expansions. * Added tests for nested attributes.
* Added support for unique constraint. * Added tests for unique constraints.
…zkd-index-lookahead
maierlars
suggested changes
Oct 6, 2021
…ngodb into feature/zkd-index-lookahead
Added testing with loolkahead 32. |
maierlars
approved these changes
Nov 8, 2021
added 4 commits
January 4, 2022 10:04
…zkd-index-lookahead
…zkd-index-lookahead
mpoeter
approved these changes
Jan 4, 2022
dothebart
pushed a commit
that referenced
this pull request
Jan 5, 2022
* Bootstrap zkd indexes. Now fill in the details. * Added prototype for condition finder. * Added helper for Range. * Fixed double conversion. * Added wrong but working nextImpl * Extract bounds for iterator. * Fixed extraction logic with reversed operator usage. * Detect equal operator correctly. * Implemented nextImpl * Removed log devel for hot path. * Cleanup * Added support for partially unbounded queries. * Do not use index for full collection scans. * Added tests for ZkdHelper. * Added functional test suite skeleton for zkd index * Some fixes to double conversions * Fixed bug in double to byte_string conversion. * Added support for denormalized doubles and infinity. * Test all interesting double values. * Disallow Nan. * Added more js tests. * Added a lot of tests. * Cleaned up test. * [zkd] Strict comparsion (#13673) * Added support for strict comparsion. * Allow unsupported conditions. Correctly display conditions that are strict in explainer. * Fixed some now broken tests. * Apply suggestions from code review Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> * [zkd] Cluster support (#13677) * Added support for cluster. * Fixing unit tests namespace using. * Added support for nested fields - excluding expansions. (#13681) * Added support for nested fields - excluding expansions. * Added tests for nested attributes. * [zkd] Unique Constraints (#13691) * Added support for unique constraint. * Added tests for unique constraints. * [zkd] Forward Compat (#13694) * Added required field fieldValueTypes: double. * Refactored index attribute validation. Disallowed attribute expansions. * Added tests for restrictions. * Fixing normalization of zkd index definition. * [zkd] Column Family (#13692) * Added a new column family for the zkd index. * Changed write buffer number to 8 + 2. * Added zkd index docu block. (#13698) * Fixed bug in RocksDBKeyBounds and using default cost estimation * [zkd] testInBox speedup (#13798) * Performance optimized testInBox. * Optimized performance of compareWithBox. * Now actually use the optimized version. * Resize vector before usage. * Clear vector before reusing CompareResults. * Eliminate div operation. * Another div in testInBox. * Count finished dimensions. * Removed unused functions. * Use small vector. * Fixed goto bug and resize short vector properly. * Apply suggestions from code review Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> * Feature/zkd index speedup getnextzvalue (#13799) * Avoid interleave&transpose in getNextZValue() * Change order of actual/expected in test assertion * Minor improvements * Removed superfluous transpose calls * Updated CHANGELOG. * Fixing iterator. * Added review suggestions. * using lookahead in zkd * added forgotten declaration * added forgotten condering of the new option * Applied suggestions from review. * removed tryNewIndex option, now decided by lookahead==0 * unified default lookaheads for zkd to 1, made one of them const * added testing with lookahead 32 in aql-optimizer-zkdindex-multi.js * Applied clang-format Co-authored-by: maierlars <lars@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Michael Hackstein <michael@arangodb.com>
maierlars
pushed a commit
that referenced
this pull request
Jan 7, 2022
* Bootstrap zkd indexes. Now fill in the details. * Added prototype for condition finder. * Added helper for Range. * Fixed double conversion. * Added wrong but working nextImpl * Extract bounds for iterator. * Fixed extraction logic with reversed operator usage. * Detect equal operator correctly. * Implemented nextImpl * Removed log devel for hot path. * Cleanup * Added support for partially unbounded queries. * Do not use index for full collection scans. * Added tests for ZkdHelper. * Added functional test suite skeleton for zkd index * Some fixes to double conversions * Fixed bug in double to byte_string conversion. * Added support for denormalized doubles and infinity. * Test all interesting double values. * Disallow Nan. * Added more js tests. * Added a lot of tests. * Cleaned up test. * [zkd] Strict comparsion (#13673) * Added support for strict comparsion. * Allow unsupported conditions. Correctly display conditions that are strict in explainer. * Fixed some now broken tests. * Apply suggestions from code review Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> * [zkd] Cluster support (#13677) * Added support for cluster. * Fixing unit tests namespace using. * Added support for nested fields - excluding expansions. (#13681) * Added support for nested fields - excluding expansions. * Added tests for nested attributes. * [zkd] Unique Constraints (#13691) * Added support for unique constraint. * Added tests for unique constraints. * [zkd] Forward Compat (#13694) * Added required field fieldValueTypes: double. * Refactored index attribute validation. Disallowed attribute expansions. * Added tests for restrictions. * Fixing normalization of zkd index definition. * [zkd] Column Family (#13692) * Added a new column family for the zkd index. * Changed write buffer number to 8 + 2. * Added zkd index docu block. (#13698) * Fixed bug in RocksDBKeyBounds and using default cost estimation * [zkd] testInBox speedup (#13798) * Performance optimized testInBox. * Optimized performance of compareWithBox. * Now actually use the optimized version. * Resize vector before usage. * Clear vector before reusing CompareResults. * Eliminate div operation. * Another div in testInBox. * Count finished dimensions. * Removed unused functions. * Use small vector. * Fixed goto bug and resize short vector properly. * Apply suggestions from code review Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> * Feature/zkd index speedup getnextzvalue (#13799) * Avoid interleave&transpose in getNextZValue() * Change order of actual/expected in test assertion * Minor improvements * Removed superfluous transpose calls * Updated CHANGELOG. * Fixing iterator. * Added review suggestions. * using lookahead in zkd * added forgotten declaration * added forgotten condering of the new option * Applied suggestions from review. * removed tryNewIndex option, now decided by lookahead==0 * unified default lookaheads for zkd to 1, made one of them const * added testing with lookahead 32 in aql-optimizer-zkdindex-multi.js * Applied clang-format Co-authored-by: maierlars <lars@arangodb.com> Co-authored-by: Tobias Gödderz <tobias@arangodb.com> Co-authored-by: Michael Hackstein <michael@arangodb.com>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
Scope & Purpose
This is an experimental improvement of the ZKD based index iterator. While querying a multidimensional range of values one can now choose (instead of computing the next intersection point of the Z-curve with the range) to try first several documents that are immediately after the current document. If one of them is in the range, the computation of the next intersection point is not necessary, otherwise the point is computed.
A new parameter can be passed from the query:
lookahead(a non-negative number). It tells how many documents after the current one should be checked for being in the search range before looking for the next point where the Z-curve intersects the search range. The lookahead is passed from the query to, finally,RocksDBZkdIndexIterator. However, it possibly should depend on the dimension of the index and on the limits of the query (see functionnumNextTries). The main change is in the functionRocksDBZkdIndexIterator::nextImpl().Backports:
Related Information
(Please reference tickets / specification / other PRs etc)
Testing & Verification
(Please pick either of the following options)
Link to Jenkins PR run:
Documentation