Could you A/B at random, use that to collect data and eventually feed that back in to prefer A or B depending on the shape of the query?
Customers love it when their queries sometimes run a lot longer.
Customers love it when their queries sometimes run a lot longer.