apache / apache/lucene

Taxonomy tree traversing improvement [LUCENE-5316]

Open
#6,380 31 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Minor module:facet type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

The taxonomy traversing is done today utilizing the `ParallelTaxonomyArrays`. In particular, two taxonomy-size `int` arrays which hold for each ordinal it's (array #1) youngest child and (array #2) older sibling.

This is a compact way of holding the tree information in memory, but it's not perfect:
- Large (8 bytes per ordinal in memory)
- Exposes internal implementation
- Utilizing these arrays for tree traversing is not straight forward
- Lose reference locality while traversing (the array is accessed in increasing only entries, but they may be distant from one another)
- In NRT, a reopen is always (not worst case) done at O(Taxonomy-size)

This issue is about making the traversing more easy, the code more readable, and open it for future improvements (i.e memory footprint and NRT cost) - without changing any of the internals.
A later issue(s?) could be opened to address the gaps once this one is done.

---
Migrated from [LUCENE-5316](https://issues.apache.org/jira/browse/LUCENE-5316) by Gilad Barkai, updated Nov 24 2013
Attachments: [LUCENE-5316.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-5316/LUCENE-5316.patch) (versions: 5)

Contributor guide

Open the contributing guide

Research direction

Review the attached LUCENE-5316.patch and locate the taxonomy traversal implementation it targets; the issue names no repository files or tests. Preserve the existing taxonomy internals while making traversal easier to follow, then run the relevant taxonomy tests after locating them.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Refactor
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.