apache / apache/lucene

Provide alternative sorting utility from SortField other than FieldComparator [LUCENE-8878]

Open
#9,921 11 comments 0 reactions 0 assignees View on GitHub
affects-version:8.1.1 legacy-jira-priority:Major module:core/search type:enhancement
Dominant language
Java
Stars
3.6k
Forks
1.4k
Avg merge
2d 11h
Merged PRs (30d)
88

Description

The `FieldComparator` has many responsibilities and users get all of them at once. At high level the main functionalities of `FieldComparator` are
- Provide LeafFieldComparator
- Allocate storage for requested number of hits
- Read the values from DocValues/Custom source etc.
- Compare two values

There are two major areas for improvement
1. The logic of reading values and storing them are coupled.
1. User need to specify the size in order to create a `FieldComparator` but sometimes the size is unknown upfront.
1. From `FieldComparator`'s API, one can't reason about thread-safety so it is not suitable for concurrent search.
E.g. Can two concurrent thread use the same `FieldComparator` to call `getLeafComparator` for two different segments they are working on? In fact, almost all existing implementations of `FieldComparator` are not thread-safe.

The proposal is to enhance `SortField` with two APIs
1. int compare(Object v1, Object v2) – this is to compare two values from different docs for this field
1. ValueAccessor newValueAccessor(LeafReaderContext leaf) – This encapsulate the logic for obtaining the right implementation in order to read the field values.
`ValueAccessor` should be accessed in a similar way as `DocValues` to provide the sort value for a document in an advance & read fashion.

With this API, hopefully we can reduce the memory usage when using `FieldComparator` because the users either store the sort values or at least the slot number besides the storage allocated by `FieldComparator` itself. Ideally, only once copy of the values should be stored.

The proposed API is also more friendly to concurrent search since it provides the `ValueAccessor` per leaf. Although same `ValueAccessor` can't be shared if there are more than one thread working on the same leaf, at least they can initialize their own `ValueAccessor`.

---
Migrated from [LUCENE-8878](https://issues.apache.org/jira/browse/LUCENE-8878) by Tony Xu (@Tony-X), updated Jul 07 2019

Contributor guide

Open the contributing guide

Research direction

Start by reading the existing SortField and FieldComparator APIs, then trace how LeafReaderContext and DocValues are used to obtain and compare sort values. Done requires an agreed alternative API that separates value access from storage and comparison while supporting concurrent search; the issue does not identify specific files or tests.

Written by the indexing model from the issue text.

Assessment

Tech stack
java
Domain
search
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.