How to create Combination of records (Order does not matter, no repetition allowed) in mySQL tables

Question

I've got a table that has hundreds of rows, each row is a recipe with nutritional information, for example:

recipe_table:

id  | calories | protein| carbs | fat

recipe1, 100,    20g,     10g,     2g
recipe2, 110,    10g,     12g,     12g
recipe3, 240,    20g,     1g,      23g
....

I needed to create a new table (recipe_index) that would show every possible combination of every recipe in recipe_table as a set of 3, so it would look something like:

recipe_index:

id1     | id2    | id3    |calories| protein | carbs | fat
recipe1, recipe2, recipe3,   450,     50g,      23g,   37g
....

Basically it allows me to query recipe_index and say "what 3 recipe combinations come to a total value that's between 440 calories and 460 calories"

My current code for doing this works at 3 meals, however I end up with about 450,000 records in recipe_index, I need to do this same thing for 4,5 and 6 meals as well, so I'm calculating billions of records at the end of this. Is there a more efficient way of doing this? Perhaps I need to look into partitioning a table for each range?

My current SQL code:

INSERT INTO recipe_index
SELECT distinct '3' as nummeals, t1.id as id1, t2.id as id2, t3.id as id3, 0 as id4,   
t1.calories_ps+t2.calories_ps+t3.calories_ps as calories,    
t1.protein_ps+t2.protein_ps+t3.protein_ps as  
protein, t1.carbohydrate_ps+t2.carbohydrate_ps+t3.carbohydrate_ps as carbohydrate, 
t1.fat_ps+t2.fat_ps+t3.fat_ps as fat from recipes t1 inner join  recipes t2  on t1.Id <      
t2.Id inner join  recipes t3  on t2.Id < t3.Id WHERE t1.image <> '' AND t2.image <> ''   
AND t3.image <> ''

Answer 1

Like Mike says, this is not something that you should be doing with the database. This is more of an algorithm question.

Your problem looks very similar to the knapsack problem, which is NP-Complete. Fortunately, you are not looking for the set that adds up to exactly some amount of calories, but a range, so it's not NP-Complete. Luckily for you, a few hundred recipes will easily fit in memory, so you can easily write an algorithm for it.

Here's a simple algorithm. I'm sure there's a better way to do it:

orderedRecipes = recipes sorted by calorie asc

def combinations(recipes, lowerBound, upperBound, recipeCount):
    first = recipes[0]
    if first.calorie < upperBound:
        for c in combinations(recipes[1:], lowerBound - first.calorie, upperBound - first.calorie, recipeCount - 1):
            if sum(r.calorie for r in [first] + c) > lowerBound:
                yield [first] + c
        for c in combinations(recipes[1:], lowerBound, upperBound, recipeCount):
            if sum(r.calorie for r in c) > lowerBound:
                yield c

combinationsOf3Between440and460 = list(combinations(orderedRecipes, 440, 460, 3))

The first loop takes the first item in the rest of the list, and the second loop does not. You don't want it to always take the first item, you want both take and no-take.

Answer 2

Since I think this is a pretty different answer, I'm making another one.

On one hand, having application code do this computation is more easily scalable (you can just plop in another server to scale), but this seems like something the database is very good at (iterating and merging data).

Instead of creating a table of every single combination, write a query that only returns exactly what you need. Sure your database will have to do the combinations every single time, but writing all this stuff onto the disk is a lot of data that you may never need.

So maybe something like this:

SELECT * from (
    SELECT '3' as nummeals, t1.id as id1, t2.id as id2, t3.id as id3, 0 as id4,   
    t1.calories_ps+t2.calories_ps+t3.calories_ps as calories,    
    t1.protein_ps+t2.protein_ps+t3.protein_ps as  
    protein, t1.carbohydrate_ps+t2.carbohydrate_ps+t3.carbohydrate_ps as carbohydrate, 
    t1.fat_ps+t2.fat_ps+t3.fat_ps as fat from recipes t1 inner join  recipes t2  on t1.Id <      
    t2.Id inner join  recipes t3  on t2.Id < t3.Id WHERE t1.image <> '' AND t2.image <> ''   
    AND t3.image <> ''
) t
where 440 <= t.calories
and t.calories <= 460

BTW, you don't need DISTINCT since your join criteria already does not equal.