Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tuple Key implementation doesn't order properly #240

Closed
ecton opened this issue Apr 3, 2022 · 0 comments
Closed

Tuple Key implementation doesn't order properly #240

ecton opened this issue Apr 3, 2022 · 0 comments
Labels
bug Something isn't working collections Issues impacting collections or views
Milestone

Comments

@ecton
Copy link
Member

ecton commented Apr 3, 2022

While working on #238, I was doing some more intensive testing on tuple keys/composite keys. I tried to use encode_composite_key directly to manually create a prefix range for a composite key, and I didn't receive the results I was looking for.

In the end, I realized that my original implementation is flawed. It doesn't sort correctly. Take these cases:

Tuple Encoded
("a", 2_u8) 0197 02
("aa", 1_u8) 0297 9701
("b", 2_u8) 0198 02

The left column is ordered as they should be, but if you notice, the bytes aren't ordered the same way. The current implementation uses variable integer encoding to encode the length at the start of a variable field. For some reason, my brain back then thought that this worked correctly, and I even thought I unit tested this properly.

I discovered part of the problem of bad testing in 7f780a7, but it wasn't until I tried to implement recursive file listing using a prefix key that I realized the issue here.

I've come up with a new encoding format already, but I wanted to document this more thoroughly in an issue rather than solely burying the details in a commit message. I will be providing a way to continue using the old encoding through a wrapper type, allowing users who have collections with primary keys that are tuples to maintain compatibility.

@ecton ecton added bug Something isn't working collections Issues impacting collections or views labels Apr 3, 2022
@ecton ecton added this to the vNext milestone Apr 3, 2022
@ecton ecton added this to To do in Khonsu Labs Roadmap via automation Apr 3, 2022
@ecton ecton closed this as completed in 7875668 Apr 3, 2022
Khonsu Labs Roadmap automation moved this from To do to Done Apr 3, 2022
@ecton ecton mentioned this issue Apr 3, 2022
ecton added a commit to ecton/bonsaidb that referenced this issue Apr 3, 2022
Recursive file listing now works correctly as well -- the original
reason I discovered khonsulabs#240.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
bug Something isn't working collections Issues impacting collections or views
Projects
Archived in project
Development

No branches or pull requests

1 participant