Avoid sorts for descending ORDER BY on lookup join index columns

[msirek]

Is your feature request related to a problem? Please describe. #84689 improves the number of cases a sort is avoided for lookup join queries with ORDER BY on the lookup index columns, but does not handle descending index columns

Example:

CREATE TABLE xyz (x INT, y INT, z INT, PRIMARY KEY(x, y, z));
CREATE TABLE uvw (u INT, v INT, w INT, PRIMARY KEY(u, v, w));

The following avoids a sort:

SELECT * FROM xyz INNER LOOKUP JOIN uvw ON x = u AND y = v ORDER BY x, y, z, u, v, w;

But if the PK of table uvw is (u, v, w DESC) and we have ORDER BY x, y, z, u, v, w DESC; This should avoid a sort. A reverse scan is not required so I believe lookup join should be able to support it.

Describe alternatives you've considered None

Jira issue: CRDB-19769

[DrewKimball]

For the first case, the problem is that the input ordering prefix (x, y) isn't unique over the input. The join can only return results in index order for a given input row - the input rows are not rearranged. Consider a case like this:

x   y   z    u   v   w
---------    ---------
1   1   1    1   1   1
1   1   2    1   1   2
1   2   3    1   2   3

If joining on (x, y) = (u, v), the result would be:

x   y   z   u   v   w
---------------------
1   1   1   1   1   1
1   1   1   1   1   2
1   1   2   1   1   1
1   1   2   1   1   2
1   2   3   1   2   3

Notice how the ordering on w is preserved for each x,y,z combination, but not for each x,y combo. I guess it's probably a good idea to add this example to the comments... I think it should be possible to avoid the sort in that example by either projecting away the z column, or by making (x, y) unique.

For the second case, while we should in theory be able to maintain index order for an index with DESC columns, the current execution logic doesn't respect the ordering in that case. Here's yahor's comment about it.

[DrewKimball]

For the second case, while we should in theory be able to maintain index order for an index with DESC columns, the current execution logic doesn't respect the ordering in that case. https://github.com/cockroachdb/cockroach/pull/84689#pullrequestreview-1044362109 yahor's comment about it.

So I guess this is a possible action item - if we can ensure the streamer performs lookups in index order in a way that respects DESC columns, we could avoid sorts in more cases.

[msirek]

@DrewKimball Thanks, didn't think this through enough. I've removed the first part of this issue.

[DrewKimball]

@DrewKimball Thanks, didn't think this through enough.

No worries. Lookup join orderings ended up being much more complicated than I expected...

[DrewKimball]

In order to make this happen, the joinreader will need to be able to issue reverse scan requests. We'll also have to change the streamer codepath to make sure the scan iteration in Enqueue respects the index ordering, at least when the ordering has to be preserved. Assuming the non-streamer codepath is still around whenever we get around to this, that will have to be changed as well.