elasticsearch/elasticsearch — pull request #3450 by jpountz (2013-08-06 11:22:42+00:00)
Title: Configurable sort order for missing string values

This commit allows for configuring the sort order of missing values in BytesRef
comparators (used for strings) with the following options:
- _first: missing values will appear in the first positions,
- _last: missing values will appear in the last positions (default),
- : documents with missing sort value will use the given value when
sorting.

Since the default is _last, sorting by string value will have a different
behavior than in previous versions of elasticsearch which used to insert missing
value in the first positions when sorting in ascending order.

Implementation notes:
- Specialized BytesRefOrdValComparators have been removed now that the ordinals
rely on packed arrays instead of raw arrays,
- Field data tests hierarchy has been changed so that the numeric tests don't
inherit from the string tests anymore,
- When _first or _last is used, internally the comparators are told to use
null or UnicodeUtil.BIG_TERM to replace missing values (depending on the sort
order),
- BytesRefValComparator just replaces missing values with the provided value
and uses them for comparisons,
- BytesRefOrdValComparator multiplies ordinals by 4 so that it can find
ordinals for the missing value and the bottom value which are directly
comparable with the segment ordinals. For example, if the segment values and
ordinals are (a,1) and (b,2), they will be stored internally as (a,4) and
(b,8) and if the missing value is 'ab', it will be assigned 6 as an ordinal,
since it is between 'a' and 'b'. Then if the bottom value is 'abc', it will
be assigned 7 as an ordinal since if it between 'ab' and 'b'.

Closes #896