Avoid evaluating later ORDER BY keys when earlier keys are enough

[yashrb24]

Is your feature request related to a problem or challenge?

Today we evaluate all sort expressions before sorting. Some of this work may be unnecessary when earlier keys already determine the order.

For example:

SELECT id
FROM events
ORDER BY score DESC, md5(payload)
LIMIT 10;

If score is enough to order two rows, comparing them does not require md5(payload). For TopK, rows whose score cannot reach the result do not need the second key either.

Describe the solution you'd like

Evaluate sort keys in stages, possibly a group of keys at a time:

• Sort by the first group of keys.
• Evaluate the next keys only for rows tied on the earlier keys.
• Repeat until the order is resolved.

This could help general sorting. With LIMIT, we could also skip later keys for rows already excluded from the result.

The problem here is that the extra sorting and filtering steps could outweigh the savings for cheap keys or many ties so grouping/chunking the evaluation of keys should be helpful.

Since it would involve some considerable change to the sort mechanics, wanted some inputs before I draft out changes for this, in case it has been considered before. I could not find any previous issue/PR for this

Describe alternatives you've considered

No response

Additional context

#22603 had explored skipping sort-key work for fully rejected TopK batches. My proposed change here is broader in scope.

Inspiration is from Spark, where it evaluates expressions inside its sort comparator and stops when an earlier key differs.