apache / apache/lucene

Make FST BytesStore grow smoothly

Open
#12,619 2 comments 0 reactions 0 assignees View on GitHub
type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

### Description

> Too bad we don't have a writer that uses tiny (like 8 bytes) block at first, but doubles size for each new block (16 bytes, 32 bytes next, etc.). Then we would naturally use log(size) number of blocks without over-allocating.
>
> But then reading bytes is a bit tricky because we'd need to take discrete log (base 2) of the address. Maybe it wouldn't be so bad -- we could do this with Long.numberOfLeadingZeros maybe? But that's a bigger change ... we can do this separately/later.

From https://github.com/apache/lucene/pull/12604#discussion_r1344639608

Contributor guide

Open the contributing guide

Research direction

Start by locating the FST BytesStore implementation and reading the linked discussion in PR 12604, including the note about Long.numberOfLeadingZeros. Define how blocks should grow from tiny initial sizes while preserving correct byte addressing. Done means the BytesStore grows smoothly without over-allocation and its existing read behavior remains correct.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.