Planner can choose suboptimal plans for reverse sorts with some values bound in equality predicates

[alecgrieser]

The planner currently doesn't match reverse sorts correctly if there are some values bound with equality predicates. For example, if there is a query like:

RecordQuery.newBuilder()
    .setFilter(Query.field("a").equalsValue("foo"))
    .setSort(Key.Expressions.concatenateFields("a", "b"), /* reverse = */ true)
    .build()

Then if there's an index ab on [a, b], the query should be able to execute a reverse scan on that one index, with the a field bound to foo. Something like:

Index(ab [[foo],[foo]] REVERSE)

However, the Cascades planner instead chooses a different plan:

Index(ab <,> REVERSE) | [a EQUALS "foo"]

That is, it scans the entire ab index and then executes the a filter as a residual predicate.

Note that if the sort order is not reversed, then the better plan is selected. The error appears to be in the way RemoveSortRule determines if the ordering has been satisfied. It will eventually produce the current ordering, which includes logic to try and handle that equality-bound predicates can appear in any place and it's okay, from an ordering perspective:

https://github.com/FoundationDB/fdb-record-layer/blob/380534fa0995790763cfefb612dd6f6e2eb995b1/fdb-record-layer-core/src/main/java/com/apple/foundationdb/record/query/plan/cascades/Ordering.java#L384-L396

But it uses the default constructor for an OrderingPart, which assumes an ascending order. This then causes problems when trying to match the ordering parts, which will be descending for reverse sorts. (This is why it works for forward order, but not for reverse order.)