Here's a simplified version of the problem. You have a marketplace where users can publish how many items they have for sale and the price. You would like to buy 1 000 000 items, and you want to purchase the cheapest listings first.

Example of getting all rows:

SELECT id, price, count FROM for_sale ORDER BY price ASC

In a worst-case scenario, you might need to fetch 1 000 000 rows if each user is selling one item each, but usually, users would publish more than a single item.

Is there a performant way to get only the rows needed to fulfil the purchase? E.g., for each row, a counter named total_items is incremented with count, and when total_items covers the wanted purchase amount, no more rows are returned.

Using LIMIT reduces the number of rows returned, but I can't be sure how many rows are needed as it depends on each row's count.

What I've tried so far

SET @total := 0;
SELECT id, count, price, @total := @total + count AS total
FROM for_sale
WHERE @total < 1000000 ORDER BY `price` ASC;

This query somewhat works, but the user variable check seems to be done client-side resulting in up to seven additional rows where the total is over 1 000 000. The performance is also terrible compared to just a LIMIT(more than 300x execution time).

I've also tried to use a window function, but I'm not sure if that's possible without reading the whole table.

Is there a way to only select rows that covers the purchase amount instead of every row? I've searched a lot, and the only examples I've found is user variable ones that suffer from performance issues.

  • that is a misconception the user variable is only run in the server never the client. as long as the session is open you can access this variable
    – nbk
    Jun 30, 2021 at 12:51
  • I think you wanted ORDER BY price ASC.
    – Rick James
    Jun 30, 2021 at 15:53
  • What's the reason why total might be larger than X when using total < X and the batch like behaviour where rows seem to be received in groups of eight then? I'd love to know what's going on.
    – Alex
    Jun 30, 2021 at 15:53
  • See if any of the [running-totals] links helps. You do have "windowing functions" that were introduced in 10.2 -- one of them should be handy.
    – Rick James
    Jun 30, 2021 at 15:55
  • @RickJames I've already searched a lot without finding anything. I know about and tried window functions but found no solution that limited the rows used to the needed ones. Is there any way to stop a window function early? Isn't it just one big step? I could run a basic(but fast) query to fetch X rows, check the total sum and fetch more if needed from code. But that seems like a really hacky solution and would also result in terrible performance due to round trip latency. It would be really great to do it serverside, but I can't find any good examples online.
    – Alex
    Jun 30, 2021 at 16:46


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.