elasticsearch/elasticsearch — pull request #7353 by areek (2014-08-20 15:35:03+00:00)
Title: NRTSuggester: Support near real-time deleted document filtering for suggestions

**Idea:**
- encode lucene docids to corresponding FST outputs
- make sure no surface form is lost even though there may be exact duplicates
- use encoded docids to perform near real-time deleted doc filtering

**Implementation & Considerations:**
- Currently the FST BytesRef Output is in the format:
`surface_form` + `PAYLOAD_SEP` + `payload` + `PAYLOAD_SEP` + `docID`
- Duplicate surface forms are stored uniquely with dedup bytes. (uses the `END_BYTE` before the dedup bytes, maybe we can support `exact_first` in the future)
- `maxAnalyzedPathsForOneInput` is now dynamically set by taking into account the # of surfaces per analyzed form at build time (to deepen the `TopNSearcher` queue for deduplication of same output form)
- `TopNSearcher` queue size is dynamically changed using a heuristic based on the cardinality of deleted docs
- Minor refactoring

**Benchmarks:**
```
-- Build time
AnalyzingSuggester input: 3472, time[ms]: 253 [+- 5.99]
XAnalyzingSuggester input: 3472, time[ms]: 400 [+- 9.18]
XNRTSuggester input: 3472, time[ms]: 397 [+- 7.05]

-- RAM consumption
AnalyzingSuggester size[B]: 807,840
XAnalyzingSuggester size[B]: 758,480
XNRTSuggester size[B]: 770,448

-- Lookup performance (prefixes: 100-200, num: 7)
AnalyzingSuggester queries: 3472, time[ms]: 127 [+- 13.23], ~kQPS: 27
XAnalyzingSuggester queries: 3472, time[ms]: 163 [+- 3.81], ~kQPS: 21
XNRTSuggester queries: 3472, time[ms]: 174 [+- 14.04], ~kQPS: 20

-- Lookup performance (prefixes: 6-9, num: 7)
AnalyzingSuggester queries: 3472, time[ms]: 106 [+- 3.88], ~kQPS: 33
XAnalyzingSuggester queries: 3472, time[ms]: 92 [+- 3.12], ~kQPS: 38
XNRTSuggester queries: 3472, time[ms]: 104 [+- 3.42], ~kQPS: 33

-- Lookup performance (prefixes: 2-4, num: 7)
AnalyzingSuggester queries: 3472, time[ms]: 169 [+- 3.15], ~kQPS: 21
XAnalyzingSuggester queries: 3472, time[ms]: 146 [+- 2.76], ~kQPS: 24
XNRTSuggester queries: 3472, time[ms]: 171 [+- 5.68], ~kQPS: 20

-- NRT Lookup performance with deleted doc filtering

-- prefixes: 100-200, num: 7
[ 0% deleted docs] XNRTSuggester queries: 3472, time[ms]: 165 [+- 3.81], ~kQPS: 21
[20% deleted docs] XNRTSuggester queries: 3472, time[ms]: 203 [+- 3.82], ~kQPS: 17
[40% deleted docs] XNRTSuggester queries: 3472, time[ms]: 249 [+- 5.23], ~kQPS: 14
[60% deleted docs] XNRTSuggester queries: 3472, time[ms]: 279 [+- 5.79], ~kQPS: 12
[80% deleted docs] XNRTSuggester queries: 3472, time[ms]: 493 [+- 6.99], ~kQPS: 7

-- prefixes: 6-9, num: 7
[ 0% deleted docs] XNRTSuggester queries: 3472, time[ms]: 168 [+- 5.16], ~kQPS: 21
[20% deleted docs] XNRTSuggester queries: 3472, time[ms]: 199 [+- 5.90], ~kQPS: 17
[40% deleted docs] XNRTSuggester queries: 3472, time[ms]: 234 [+- 6.21], ~kQPS: 15
[60% deleted docs] XNRTSuggester queries: 3472, time[ms]: 327 [+- 5.40], ~kQPS: 11
[80% deleted docs] XNRTSuggester queries: 3472, time[ms]: 550 [+- 5.92], ~kQPS: 6

-- prefixes: 2-4, num: 7
[ 0% deleted docs] XNRTSuggester queries: 3472, time[ms]: 168 [+- 4.35], ~kQPS: 21
[20% deleted docs] XNRTSuggester queries: 3472, time[ms]: 199 [+- 3.85], ~kQPS: 17
[40% deleted docs] XNRTSuggester queries: 3472, time[ms]: 228 [+- 4.50], ~kQPS: 15
[60% deleted docs] XNRTSuggester queries: 3472, time[ms]: 247 [+- 6.18], ~kQPS: 14
[80% deleted docs] XNRTSuggester queries: 3472, time[ms]: 367 [+- 7.24], ~kQPS: 9
```
closes #7133