[ENH] Implement `SignedRoaringBitmap` and update where/where_document AST

[Sicheng-Pan]

Description of changes

Summarize the changes made by this PR.

• Improvements & Bug fixes

  • Updates MetadataValue so that the floating type is f64 and the integer type is i64, which is consistent with proto definitions.
  • Updates WhereComparison so that it can be handled with less code (in the subsequent PRs).
  • Convert DirectWhereDocumentComparison as a variant of Where enum. This unifies the Where and WhereDocument, which facilitates a shared evaluation pipeline (in the subsequent PRs).

• New functionality

  • Introduce SignedRoaringBitmap which captures the idea of performing conjunction and disjunction on bitmaps without the knowledge of the whole domain. This is useful because in our case the domain is decided by the entries in the database that is not yet deleted, and currently it is costly to scan over the entire collection to determine existing entries. Since we would like to support $ne and $nin, whose results depend on the domain, we hope to delay the evaluation of the negation unless it is necessary to do so, and do it only once.

Test plan

How are these changes tested?

This is guaranteed to break existing tests. Only the last PR in the stack addresses the breaking changes, and should pass the existing tests. In particular, any test involving the query node should fail because of compilation errors.

• [ ] Tests pass locally with pytest for python, yarn test for js, cargo test for rust

Documentation Changes

Are all docstrings for user-facing APIs updated if required? Do we need to make documentation changes in the docs repository?

N/A

[github-actions[bot]]

Reviewer Checklist

Please leverage this checklist to ensure your code review is thorough before approving

Testing, Bugs, Errors, Logs, Documentation

• [ ] Can you think of any use case in which the code does not behave as intended? Have they been tested?
• [ ] Can you think of any inputs or external events that could break the code? Is user input validated and safe? Have they been tested?
• [ ] If appropriate, are there adequate property based tests?
• [ ] If appropriate, are there adequate unit tests?
• [ ] Should any logging, debugging, tracing information be added or removed?
• [ ] Are error messages user-friendly?
• [ ] Have all documentation changes needed been made?
• [ ] Have all non-obvious changes been commented?

  System Compatibility

• [ ] Are there any potential impacts on other parts of the system or backward compatibility?
• [ ] Does this change intersect with any items on our roadmap, and if so, is there a plan for fitting them together?

  Quality

• [ ] Is this code of a unexpectedly high quality (Readability, Modularity, Intuitiveness)

[Sicheng-Pan]

• #2849
• #2848
• #2847
• #2846 👈
• main

This stack of pull requests is managed by Graphite. Learn more about stacking.

Join @Sicheng-Pan and the rest of your teammates on Graphite

[HammadB]

Makes sense to me. Just nits, defer to @sanketkedia on logic

[Sicheng-Pan]

Urge you to add more comments for SignedRoaringBitmap as it is not obvious as to what is its purpose. Otherwise LGTM!

I've moved it to a separate file and added a block comment with example to show its usage. Hopefully that would clarify its usage a bit for anyone reading the code in the future.

[Sicheng-Pan]

Merge activity

• Sep 30, 7:32 PM EDT: @Sicheng-Pan started a stack merge that includes this pull request via Graphite.
• Sep 30, 7:32 PM EDT: @Sicheng-Pan merged this pull request with Graphite.