statedb: Allow non-terminated keys #29440
Merged
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
7915ee8 to
c114322
Compare
2d32b2f to
3aa0b4d
Compare
3aa0b4d to
8c4dff4
Compare
bimmlerd
approved these changes
Nov 28, 2023
This is really just a safeguard. We want the termination when possible as that makes the traversal of the index efficient (we won't encounter unmatching nodes). |
|
/test |
Signed-off-by: Jussi Maki <jussi@isovalent.com>
To implement special casing for querying unique indexes we need to know whether the index is unique or not. To avoid extra lookups store the uniqueness information in the index radix tree. Signed-off-by: Jussi Maki <jussi@isovalent.com>
Previously statedb required the indexers to either terminate or return fixed-size keys in order to exactly match with just prefix searching the trees. This is a fairly large footgun. This commit adds checks to the iterators to make sure the key matches exactly and is not a longer key that shares the prefix. For indexers that don't terminate the key, this may result in wasting bit of time by traversing non-matching nodes. This was tested by "breaking" index.String by removing termination and validating that the regression test passes. Signed-off-by: Jussi Maki <jussi@isovalent.com>
Signed-off-by: Jussi Maki <jussi@isovalent.com>
For checking that the extra key length checks in iteration do not add any significant cost. Signed-off-by: Jussi Maki <jussi@isovalent.com>
Add a test case for the database seek and iteration part of the query API handler. Signed-off-by: Jussi Maki <jussi@isovalent.com>
8c4dff4 to
da7bd80
Compare
|
/test |
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.
Allow use of indexers that are not fixed-size or which don't terminate the key by checking that the key
length matches exactly with the used search prefix. For unique indexes this is as simple as checking
the key lengths in the iterator and for multi-index we need to extract the length of the secondary key
and compare against that.
E.g. now
struct{A, B string}with multi-index onBwill be indexed internally with concatenated keyB + A + <len>, where<len>is 16-bit unsigned big endian int (the KeySet limits key sizes to 16-bits). AGetagainst a multi-index willreturn an iterator which will check that the node's key matches with the query, for example
Get("foo")against{"foo", "bar"}and{"foob", "ar"}(assuming no terminating\0) will return an iterator which has beenseeked to key "foobar3". The iterator will extract length (3) and compare against search key length (len("foo"))
and since length matches the object is returned. Next the iterator would advance to "foobar4" which would be
skipped since
4 != len("foo").In effect this allows statedb to work with indexers that do not terminate the keys, but at the performance cost of
potentially traversing over non-matching tree nodes. The actual length extraction and comparison adds no measurable
time to the iteration (the Get benchmark that was added showed no difference).
This PR additionally extends the tests to cover queries against multi-indexes with overlapping prefixes.