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

High runtime/space complexity for construction with many unique #[venndb(filter)] fields #17

Open
quantatic opened this issue Jul 19, 2024 · 0 comments

Comments

@quantatic
Copy link

The space (and time for construction) complexity for a Db for a type that has many (but not all) unique #[venndb(filter)] fields appears to be O(n^2), which makes constructing (and holding) such a Db quickly infeasible for collection with more than ~100,000 unique fields.

Among other solutions, I wonder if we could use some sort of compressed bitset implementation, like roaring or hi_sparse_bitset to better handle this scenario with minimal to no performance loss in the "large number of total entries, small number of unique filter field values" case.

If we're not interested in adjusting the current implementation, this could also be something gated behind a feature flag or configured by some derive attribute.

I'd be happy to take a look at feasibility if it's something that would be considered 😃

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant