1

TLDR: I need a way to limit my select such that only rows needed to fill my new order are returned.

Hey, I'm looking for a better way to do a query on the simplified toy table below. Right now I do a straightforward select then do some additional logic in Python that processes rows that are fully or partially fillable.

id |name   | category |  price  | quantity
---+-------+----------+---------+---------
1  |Robby  | buy      | 45      | 4
2  |Blane  | buy      | 48      | 5
3  |Shawn  | buy      | 43      | 10
4  |Valva  | sell     | 62      | 9
5  |Chris  | buy      | 42      | 15

If I'm inserting a new sell order at price $40 and quantity = 12

SELECT id, name, price, category
FROM my_table
WHERE price > 40 AND category = 'buy' 
ORDER BY price DESC;

Then in Python my logic looks something like this:

running_total = 0
for order in orders:
    running_total += order.quantity
    fill_order(order, new_sell_order)
    if running_total >= new_sell_order.quantity:  # Values is 12 in my example.
        break

I'd like a way to limit my select such that all rows are returned in order until a row is returned such that the sum of all quantity columns is greater than some value. Additional columns need not be returned (and thus locked in a repeatable read state).

  • Is it important to satisfy the buy orders in the sequence they were submitted e.g. ID sequence? If you want to satisfy as many buy orders as possible without going over your sell order's quantity then this is the knapsack problem. – Michael Green Jul 13 '15 at 3:02
  • I skipped some complexity but yes, there is further sorting going on. For unfilled orders (those that are persisted), price is the most important sort order since new orders have the right to be greedy w/r/t finding the most desirable price. If two order are equally priced, then the oldest one is filled first. I don't have the knapsack problem because orders can be filled fractionally. – user1276560 Jul 13 '15 at 3:30
7

If you don't need the "optimal fill", you could use a window function and something like this:

select *
from (
  select id, name, price, category, 
         sum(price) over (order by price, date_created) as so_far
  from my_table
  where price > 40 
    and category = 'buy' 
) t
where so_far <= 12;

If you are mixing "groups" of orders, you might need a partition by clause as well. Change the order by inside the window function to meet your ordering criteria.

| improve this answer | |
2

The following query is derived from that posted by a_horse_with_no_name. His answer hit's the core of the question (filtering against a sub-query's window function) but missed an important point where I need to select all orders that have any fillable value (hence in my python snippet the loop exit happens after the order processing).

The following query is similar to that posted above and meets my specific logic requirements.

WITH eligible as (
   select id, name, price, category, 
         sum(quantity) over
           (PARTITION BY category ORDER BY price DESC, id) as so_far
   from test
   where price > 40 
   and category = 'buy'
)
(SELECT * FROM eligible WHERE so_far < 12)  // Orders that will be fully filled
UNION
(SELECT * FROM eligible WHERE so_far >= 12 LIMIT 1)  // One order that will be partially or fully filled.
ORDER BY price DESC, id;
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.