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

Optimize deletion by taking a transaction of the previous version of the database #95

Open
irevoire opened this issue Sep 24, 2024 · 0 comments
Labels
breaking Something that will break in the next release enhancement New feature or request performance

Comments

@irevoire
Copy link
Member

Currently, the deletion in arroy runs in O(n) on the number of three nodes which is super slow.
The reason is that when we delete or replace an item, we cannot access the previous version of it, so we don't know where we'll find it, and we have to go through the whole tree.

We could maybe try to implement a slightly better version with #88, but it doesn't seem trivial and won't fix the issue for the updates of item.
Technically, even though it’ll be way faster, it's still O(n) on all the tree nodes, which won't scale forever.

The solution

By taking a read transaction of the previous version of the database, we would be able to read the previous version of the vector under the specified item ID and find it directly in the tree in O(log2(n)).

@irevoire irevoire added enhancement New feature or request breaking Something that will break in the next release performance labels Sep 24, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
breaking Something that will break in the next release enhancement New feature or request performance
Projects
None yet
Development

No branches or pull requests

1 participant