MySQL Select 3 random rows where sum of three rows is less than value

Question

I am trying to select three random rows from a table, where their combined item_price column is less than a desired amount.

Imagine you have an <input> for a dollar amount. When you enter the dollar amount, the database returns three random items, where their combined price is less than or equal to the dollar amount you enter.

If I enter $300, you could buy these three items, $150, $100, and $50. I'm having difficulty creating a query that will return three items that meet this criteria.

SELECT t1.item_id, t1.item_price
FROM items t1
INNER JOIN items t2 ON ( t1.item_id = t2.item_id )
GROUP BY t1.item_id, t1.item_name, t1.item_price
HAVING SUM( t2.item_price ) <=300
ORDER BY RAND( )
LIMIT 3 

I thought this would work, but I think it was just a coincidence when it did. It seems to just return any three items whose prices are less than $300, not total less than $300.

I also tried this query:

SELECT t1.item_id, t1.item_price
FROM   items t1
JOIN   items t2 ON t2.item_id <= t1.item_id
WHERE  t2.item_price <= 500
GROUP  BY t1.item_id
HAVING SUM(t2.item_price) <= 500
ORDER  BY RAND()
LIMIT 3

Again, seemed to work at first, but then it started returning items for $2000.

If there's a better (even sacrificing performance) way to do this in PHP, I don't mind. I just didn't think the query would be so difficult.

As always, thanks anyone for the help.

Answer 1

here is another solution:

SELECT t1.item_id as id1, t2.item_id as id2, t3.item_id as i3
FROM items t1, items t2, items t3
WHERE
t1.item_id <> t2.item_id and
t1.item_id <> t3.item_id and
t2.item_id <> t3.item_id and
(t1.item_price + t2.item_price + t3.item_price) <= 300
order by rand()
limit 1

optionally you can filter by minimal sum

Answer 2

You could do it step by step. Say we have $500 ask limit. First get the min price in your DB.

select MIN(item_price) from items

Lets say this is 25.00 so for our first item we want a max from 500 plus 2 times the least value (2 * 25 = 50) so i check for the first item matching less or equal to 450 dollars

select item_id, item_price from items where item_price <= 450 order by rand() limit 1

This item now maybe is 240 dollars, so next query is:

select item_id, item_price from items where item_price <= 140 order by rand() limit 1

The next one could be 50 dollars, so the next query is:

select item_id, item_price from items where item_price <= 90 order by rand() limit 1

And there you go.

I am aware, that this is a quite simple solution and there surely could be better solutions, but using triple joins and random sorting on large tables will swallow lots of performance, and the result of the queries are not better than running these three simple queries, that will run like burst if table is indexed properly.

Doing it this way also would give you fine control on combinations returned (i.e. you could extend items with categories and reduce queries to distinct categories, so for example you could combine technical+kitchen+fun categories).

Since we are all here to learn, and we never stop learning, i believe this solution is a good basis for a flexible extension of the functionality. If you want to use a single query, then i would advise to have the query dump a large set of possible combinations into a table, so you can run your massive query maybe once a day and when you want to pick a combination, you just query your pre-rendered random table.

Answer 3

you can get all triplets of items having sum of price <= 300 with

SELECT a.item_id, a.item_price, b.item_id, b.item_price, c.item_id, c.item_price
  FROM items a 
       JOIN items b ON a.item_id < b.item_id
       JOIN items c ON b.item_id < c.item_id
 WHERE a.item_price + b.item_price + c.item_price <= 300

then you could sort by rand() and pick one.

there are discussions about performance of selecting random rows in mysql that you should check. the triple join will be costly if items table is big.

EDIT

as suggested in other answers, this query can be improved filtering each item by price <= 300, and using an index on items.price.

Answer 4

I was able to get the result with both these queries and a PHP version below

SET @MaxAmount = 5;
SELECT FirstItem.id, SecondItem.id, ThirdItem.id, FirstItem.amount +  SecondItem.amount +  ThirdItem.amount as Total
FROM Items as FirstItem
CROSS JOIN Items as SecondItem  ON SecondItem.id <> FirstItem.id and FirstItem.amount + SecondItem.amount < @MaxAmount 
CROSS JOIN Items as ThirdItem ON ThirdItem.id <> FirstItem.id  and ThirdItem.id <> SecondItem.id and FirstItem.amount + SecondItem.amount + ThirdItem.amount < @MaxAmount
ORDER BY RAND()
LIMIT 3;

And

SET @MaxAmount = 5;
SELECT FirstItem.id as id1, SecondItem.id as id2, ThirdItem.id as i3,  FirstItem.amount +  SecondItem.amount +  ThirdItem.amount as Total 
FROM Items FirstItem, Items SecondItem, Items ThirdItem
WHERE FirstItem.amount + SecondItem.amount < @MaxAmount
AND FirstItem.amount + SecondItem.amount  + ThirdItem.amount < @MaxAmount
AND SecondItem.id != FirstItem.id -- Prevent Same Id from showing up
AND ThirdItem.id != FirstItem.id  and ThirdItem.id != SecondItem.id
ORDER BY RAND()
LIMIT 3;

http://sqlfiddle.com/#!9/0e1c8/3

I would only do this if the Items table is relatively small. You can do this in PHP by selecting all the items with the price less than 300 and generating the k combinations(also named nCr) of 3 and then using a filter function that returns the ones that summed together are less than 300.

$rows = $db->query("Select FirstItem.amount as amount1, SecondItem.amount as amount2, ThirdItem.amount as amount3 (.. and also the ids) from Items where amount < 300");
$ncr = getCombinations($rows, 3);
$filtered = array_filter($ncr, function($row) { return $row['amount1'] + $row['amount2'] + $row['amount3'] < 300; })

Answer 5

Here's a SQL only (MySQL flavour) solution:

SELECT i.*
FROM items i
CROSS JOIN
    (SELECT CONCAT('^(', t1.item_id, '|', t2.item_id, '|', t3.item_id, ')$') AS regex
     FROM items t1
     CROSS JOIN items t2
     CROSS JOIN items t3
     WHERE t1.item_id < t2.item_id
       AND t2.item_id < t3.item_id 
       AND t1.item_price + t2.item_price + t3.item_price <= 300
     ORDER BY RAND()
     LIMIT 1) s
WHERE i.item_id REGEXP s.regex

Not very efficient for large result sets as it creates a subquery of the different permutations of 3 items that fulfill the total criteria and then picks one of these at random. The subquery returns its result as a regular expression to allow the rows to be picked in the outer query.

See SQL Fiddle demo.

Answer 6

Another solution i get by looking Lashane's answer because each of the item's price must not be greater than the total. There should be some improvement by adding this (try EXPLAIN to the query).

SELECT t1.item_id as id1, t2.item_id as id2, t3.item_id as i3
FROM items t1, items t2, items t3
WHERE
t1.item_price <= 300 AND
t2.item_price <= 300 AND
t3.item_price <= 300 AND
t1.item_id <> t2.item_id AND
t1.item_id <> t3.item_id AND
t2.item_id <> t3.item_id AND
(t1.item_price + t2.item_price + t3.item_price) <= 300
ORDER BY RAND()
LIMIT 1