Sort orders by limit price and type when filtering based on remaining balance

[fleupold]

We currently don't sort orders before applying deducting their sellAmounts to user balances (until the balance reaches 0), meaning that less likely to be filled orders (based on limit price) could take precedence and shadow more realistic orders in the instances being sent to solvers.

https://github.com/cowprotocol/services/blob/6eb392fa1c3445ccef96e7db23b404dc320ffa72/crates/solver/src/order_balance_filter.rs#L64-L77

If the order is on the same token pair, it would be good to prioritise by limit price (using the more relaxed one first) and otherwise prioritise market orders over limit/liquidity orders.

If we get access to the price estimation vector we could even sort orders by limit price "likelyhood" if the buy tokens are different.

[fleupold]

I actually missed line 69 above, where we already sort by creation timestamp. This can however be problematic for limit orders (where users probably want the most price-likely rather than the last placed order to enter the auction) and for ERC1271 orders where anyone can place orders on behalf of the beneficiary at overly optimistic prices.

I’d therefore suggest to change the logic in line with what @nlordell suggested on slack to first sort on order class (market over limit & liquidity). For the second group, we should sort by “expected surplus” (using the external price vector for reference). For market orders, we can keep the arrival time logic as it has been working well or for unification reasons also sort by limit external price.

Any preferences (cc @vkgnosis as I believe you implemented the original arrival time logic)?

[nlordell]

Closing #1627 as it is a duplicate of this issue, and this one has more context.

[vkgnosis]

I'd like to it consistently so also change arrival time to price for market.

[fleupold]

I also like the consistency argument, just pointing out that the last in first out logic would allow the user to work around potential issues with our external price vector (in case some token's price is quite off) - it just doesn't work well with limit orders.

I implemented both version in separate commits in #1635