quickwit-oss / quickwit-oss/quickwit

Reduce the variance of the split size produced by the merge operations.

Open
#713 0 comments 0 reactions 1 assignee View on GitHub

@fulmicoton is already working on this.

Since Nov 8, 2022.

enhancement
Dominant language
Rust
Stars
11.7k
Forks
597
Avg merge
2d 22h
Merged PRs (30d)
37

Description

Right now, the merge policy attempts always mergeFactor splits together, until the last merge.

For the last merge, the worst case scenario happens when we have two splits of size
max_doc - 1, in which case we end up with one gigantic split of size 2max_doc - 2.

Mature splits end up with any size between [max_doc .. 2max_doc - 2).

Having such a variation (from simple to double) in the split size can hurt indexing, search, and demux
operations...

One easy and robust way to reduce this variance is to avoid the situation where we have two splits of size max_doc - 1.
In fact, as much as possible, if we avoid producing splits with the [max_doc * 2 / (mergeFactor), max_doc) band, we are certain to keep our amplitude max_mature_split - max_doc = max_doc * 2 / mergeFactor - mergeFactor / 2 - 1.

For instance

  • for mergeFactor = 10, the max amplitude is 20% max_docs.
  • for mergeFactor = 8, the max amplitude is 25% max_docs.

Of course this assumes that the young splits have a size that is smaller than max_doc * 2 / mergeFactor.
While this is a reasonable assumption, we need to ensure that the code still behaves properly if this condition
is not observed.

The trick retained here is to stop adding splits to a merge candidates that already exceeds max_doc / mergeFactor.

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.