Since ordinals are sorted it should be possible to compute the range of ordinals that belongs to a single prefix (field). You can perform a binary search to find the first and last ordinals that contains the field prefix and use this information to remove the need to call lookupOrd on each value.

Nice, will try that out!

I looked into this more closely, and wanted to check I understand your suggestion: when creating a new KeyedJsonAtomicFieldData, we can do a one-time calculation to figure out the relevant range of ordinals. If the set of documents considered during the search is very restricted, this might be slightly more expensive than the current approach, but in general it should cut down a lot on lookups/ bytes comparisons.

That's the idea yes, we'll need to recompute the min/max for each query (since we want to cache the fielddata only once for all fields) but since it's a binary search it shouldn't be too expensive.

This is not related to this pr but KeyedJsonFieldType#existsQuery should also use the _field_names field instead of a prefix query ?

Thanks, I will give this some thought and follow up in a separate issue/ PR.

The SortField will use the original doc values to perform the sort so you'll need to create a custom SortedSetSortField that uses a KeyedJsonDocValues in order to filter the values that should not participate in the sort.

👍

I took a closer look at SortedSetDVOrdinalsIndexFieldData to understand how this should be implemented, and was trying to figure out whether this optimization was relevant: https://github.com/elastic/elasticsearch/blob/master/server/src/main/java/org/elasticsearch/index/fielddata/plain/SortedSetDVOrdinalsIndexFieldData.java#L76-L79. Would you be able to give a little bit of background on this logic (originally introduced in #23827)?

This is not an optimization but a change that was needed to handle index sorting. Index sorting at the index writer level accepts the Lucene's FieldSort only and since we compare index sort with the query sort to activate early termination we needed to make the query sort compatible. This shouldn't be an issue for the json field since this should not be allowed to use it for index sorting.

That makes sense, thanks!

This should be delegated as well

👍

If there is no match for this key (minOrd==-1) you can directly return DocValues#emptySortedSet ?

+1 it might help simplify KeyedJsonDocValues a bit as well

👍 this is certainly cleaner.

WHen -> When

👍

One small optimization that could save some memory in the terms aggregation is to remap the documents ordinals to [0, (maxOrd-minOrd)] during the collection. With global ordinals the terms aggregation allocates one big array based on the size reported by getValueCount so if you have a lot inner fields with lots of different values we'll allocate much more than what we really need. The remapping should happen in lookupOrd (to retrieve the original ordinal) and nextOrd (to remap based on minOrd), getValueCount can return maxOrd-minOrd.

+1 We might need to keep it for a follow-up however because I think it's going to make IndexOrdinalsFieldData#getOrdinalMap a bit hard to implement given that OrdinalMap is not designed for being extended.

+1 it might help simplify KeyedJsonDocValues a bit as well

Doc values already have an optimized way to find the first term that has a prefix via their terms enum, so we could do something like that. In general the underlying implementation does a binary search as well, but often it is a bit more efficient eg. by working directly on the compressed data.

TermsEnum te = sortedSetDocValues.termsEnum();
if (te.seekCeil(prefix) != SeekStatus.END && StringHelper.startsWith(te.term(), prefix)) {
  return te.ord();
} else {
  return -1;
}

For SortedSetDocValues it looks like this will call into SortedDocValues#lookupTerm, which is very similar to the current implementation. I find the current approach cleaner in that findMinOrd and findMaxOrd follow the same template, and that comparisons happen only on the prefixes. Maybe I could keep it as is for now, but see if it makes a difference when I run some benchmarks (on the TODO list)?

Fine with me.

Calls to advanceExact() are often followed by calls to nextOrd(). With such an implementation, we will iterate ords of the underlying doc values twice. Could we somehow cache the first ord that is greater than or equal to minOrd so that we don't have to call advanceExact again on the underlying doc values here and the first call to nextOrd() will return the cached first matching ord?

This is a nice idea, will try it out.

Even though it's impossible here because we are dealing with longs, a good practice when implementing binary search with signed indexes is to use unsigned shifts or unsigned division to avoid issues in case of overflow, ie. (low + high) >>> 1, or Long.divideUnsigned(low + high, 2).

👍

UncheckedIOException would be a better fit.

👍

+1 We might need to keep it for a follow-up however because I think it's going to make IndexOrdinalsFieldData#getOrdinalMap a bit hard to implement given that OrdinalMap is not designed for being extended.

We should fail with out-of-range ords, some features are going to call this method on out-of-range ords, such as if you pass min_doc_count: 0 to a terms agg. For the record, rebasing ordinals would address this issue (but has some challenges as highlighted in another comment).

We should probably document this limitation.

This is good to know, I wasn't aware that we scanned the full ordinals array in some places. I added an explicit check for out-of-range ordinals.

I started to add documentation around the aggregations features that were not supported, but it was hard to justify and came off as unintuitive. I'm going to look into rebasing the global ordinals in a follow-up PR to try to solve the issue (and if that's not possible will brainstorm some compromise/ explanation).

nit: can we add an assert ord >= minOrd?

👍

nit: we could actually break the loop if ord > maxOrd

👍