elasticsearch/elasticsearch — pull request #4518 by jpountz (2013-12-19 15:02:19+00:00)
Title: Use BINARY doc values instead of SORTED_SET doc values to store numeric data

Although SORTED_SET doc values make things like terms aggregations very fast
thanks to the use of ordinals, ordinals are usually not that useful on numeric
data. We are more interested in the values themselves in order to be able to
compute sums, averages, etc. on these values. However, SORTED_SET is quite slow
at accessing values, so BINARY doc values are better suited at storing numeric
data.

It is only allowed to have a single BINARY doc values field instance per field
name per document, which makes it quite challenging to use for multi-valued
fields since all values need to be buffered in memory and converted to a single
field instance in the end. In order to do so easily, all mappers (not only the
root mappers) now have a preParse and a postParse phase, which are called before
and after all fields have been visited for a single document. In the case of the
numeric field mappers, parse now takes care to buffer values and postParse takes
these values, sorts them and deduplicates them before encoding them into a
BINARY doc values field.

floats and doubles are encoded without compression with little-endian byte order
(so that it may be optimizable through sun.misc.Unsafe in the future given that
most computers nowadays use the little-endian byte order) and byte, short, int,
and long are encoded using vLong encoding: they first encode the minimum value
using zig-zag encoding (so that negative values become positive) and then deltas
between successive values.

I ran `TermsAggregationSearchBenchmark` to get an idea of the impact of this
change and results are promising:

| Task | Before this change | After this change | Difference
| -------------: |-------------:| -----:|-----:|
| terms_agg_l_dv | 235 | 145 | 38% faster |
| terms_agg_lm_dv | 1705 | 714 | 58% faster |

For reference, `terms_agg_l_dv` is an aggregation on a single-valued long field
stored in doc values while `terms_agg_lm_dv` is an aggregation on a multi-valued
long field (10 values per document) stored in doc values.

Close #3993