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

SSTableIndex could be a multi layer SSTable #1948

Open
fulmicoton opened this issue Mar 21, 2023 · 3 comments
Open

SSTableIndex could be a multi layer SSTable #1948

fulmicoton opened this issue Mar 21, 2023 · 3 comments

Comments

@fulmicoton
Copy link
Collaborator

fulmicoton commented Mar 21, 2023

Right now we use the SSTable format to store block "checkpoints" in a Vec and do binary search on those.

An alternative could be to store several layers of SSTable:

  • Layer 1 one like current SSTableIndex. Checkpoint every N / B docs.
  • Layer 2 Checkpoint in layer 1. N / B^2
  • Layer 3 Checkpoint in layer 1. N / B^3
  • ...

Thanks to geometric series, the overhead of having that stack of layers is minor for B = 16 for instance.
We would have transformed the binary search into a coarse to scale linear search, with good strong locality.

The main benefit would be to make opening a term dictionary very cheap, regardless of number of blocks.

@trinity-1686a @PSeitz let me know if I make sense? To know if this is useful, we need to know
how expensive it is to open a sstable with 10 millions terms today.
To accept such a change, we will need also a bench on ord_to_term (if it does not exist already)

@fulmicoton
Copy link
Collaborator Author

Assigned to @trinity-1686a for the moment, but we don't even know if we want this.

@trinity-1686a
Copy link
Contributor

In the flamegraph PSeitz linked here #1946 (comment), Dictionary::open is very fast (0.42% of samples), whereas Dictionary::ord_to_term is 9.94% of samples. A naive approach could cause ord_to_term to be N time slower (with N the number of layers).
On some other workload (a simple TermQuery), the Dictionary::open is probably most of the cost and it could then make sens to do that kind of change (or maybe it doesn't).
When querying the index, the block being opened should probably be cached to amortize that cost on workload which may query the index a lot (columnar case)

@trinity-1686a
Copy link
Contributor

unassigning myself for now, while there is possibly something to gain for large segments, I believe there are probably more impactful changes to explore

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

Successfully merging a pull request may close this issue.

2 participants