ES|QL: pushdown LOOKUP JOIN past SORT

[luigidellaquila]

(and potentially other commands)

Some queries cannot be executed due to unbounded sort.

Eg.

languages mapping:

{
  "mappings": {        
        "properties": {"language_code": {"type": "integer"}, "name": {"type": "keyword"}}}, "settings": {"index": {"mode": "lookup"}}
}

row language_code = 1, name = "foo" 
| sort name 
| lookup join languages on language_code 
| where name == "English"

will result in a verification_exception.

Some cases though, could be fixed by pushing LOOKUP JOIN past SORT.

When there is attribute masking it's particularly challenging, as we'll have to keep a copy of the original column with a different name and then discard it, eg. the above query could be translated to

row language_code = 1, name = "foo" 
| RENAME name AS $$name 
| lookup join languages on language_code 
| sort $$name 
| DROP $$name
| where name == "English"

[elasticsearchmachine]

Pinging @elastic/es-analytical-engine (Team:Analytics)

[alex-spies]

Oh no, I realized there's a problem with this approach.

That is: Currently, after the JOIN/MV_EXPAND, the rows that come from multiple matches/expanding a multivalue are consecutive. Is this part of the contract for JOIN/MV_EXPAND?

If it is, then the approach of pushing down past a sort cannot be correct, as sorting after will break up consecutive rows that belonged to the same match/MV.

Otherwise, this approach is correct but has another problem - in addition to requiring to be well documented: Some users already remarked that with LOOKUP JOIN there's currently no way to get the behavior that ENRICH has, where multiple matches create a multivalue. And for some use cases that could be important. Which could be solved by a MV_COLLAPSE BY field1, field2 command, that would collapse multiple consecutive rows with the same field1, field2 values into a single row.

If we wanted this MV_COLLAPSE, then the proposed optimization would break it:

...
| SORT x
| MV_EXPAND y
| MV_COLLAPSE BY y // together with the MV_EXPAND before, this will be (mostly) a no-op.

not equivalent to

...
| MV_EXPAND y
| SORT x
| MV_COLLAPSE BY y

Similarly:

...
| SORT x
| LOOKUP JOIN idx ON y
| MV_COLLAPSE BY y // together with the LOOKUP JOIN before, this would achieve nearly ENRICH-like behavior

Not equivalent, though:

...
| LOOKUP JOIN idx ON y
| SORT x
| MV_COLLAPSE BY y

[luigidellaquila]

Good catch

Is this part of the contract for JOIN/MV_EXPAND?

I don't think we have a documented behavior about this, but yeah, it seems a natural implicit behavior. IMHO we should not break it, unless there is a real reason

[alex-spies]

I think we need to decide on this contract before LOOKUP JOIN goes GA. I'll take note of it.

[luigidellaquila]

Thinking more about this, while for MV_EXPAND it seems natural (one record in, N records out, as they flow), for JOIN this constraint could be a big limitation, especially if we implement generalized JOIN between indexes.
Guaranteeing this order in a distributed join is not trivial. And expensive.

[alex-spies]

@nik9000 pointed out that another solution would be if our TopN implementation was stable. Then, I think pushing down LOOKUP JOIN past a SORT would be correct.

[costin]

For the record, for the near future there will be NO ordering guarantees for a various reasons (many already stated in this thread):

a. it’s a two-way door, meaning we can add ordering guarantees later if we want to. the reverse is not possible
b. sorting in a distributed system is expensive for questionable gains (e.g. how to disable it if not needed)
c. multi-values semantics are not guarantees in ES and while in practice there is ordering, enforcing a loose implementation has no immediate upside.