Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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 <> ''
share|improve this question
2  
500 recipes taken 3 at a time is about 20 million combinations. 500 recipes taken 4 at a time is about 2.5 billion. 500 taken 5 at a time is about 255 billion. 500 taken 6 at a time is about 2.1E13. You don't need to do this more efficiently; you need to do something completely different. –  Mike Sherrill 'Cat Recall' Aug 13 '13 at 2:12
    
Are you saying it's not possible to do what I want to do, or I need to go about it differently? –  Neostim Aug 13 '13 at 2:38
    
"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..." (and 4, and 5, and 6) For all practical purposes, 2.1E13 rows is not possible. –  Mike Sherrill 'Cat Recall' Aug 13 '13 at 3:05
add comment

2 Answers 2

up vote 0 down vote accepted

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))
share|improve this answer
    
That's exactly what I was looking for, another way of looking at this. In the end I need the check for calories, protein, carbs and fat ranges. I assume I can still use this logic, however it will be more processor intense with 3 additional bound checks, I still think it would beat out the way I was doing it. I think I understand all of the code, I'm going to give it a try in PHP and see how I make out, I'll be back with my findings! –  Neostim Aug 13 '13 at 3:01
    
One more question if I may, what's the purpose of the first loop vs the second loop? Thanks again –  Neostim Aug 13 '13 at 3:50
    
@Neostim 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. –  John Tseng Aug 13 '13 at 4:19
add comment

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.

share|improve this answer
    
I gave this query a try, but it's still running (4 minutes in), I am on a shared mySQL server, perhaps that's limiting it, I can always look at a standalone server if it would make a drastic difference. –  Neostim Aug 13 '13 at 3:21
    
@Neostim Probably won't help too much. Even with a shared server, with only a few hundred rows, it probably takes only a few dozen seconds to load all the rows. The rest of the time is probably iterating all possible results. Probably the only optimization you can do is indexing the ID column. –  John Tseng Aug 13 '13 at 3:25
    
It's sounding like your other solution might be a better bet for me? I'm having trouble understanding the logic in it (I really only know PHP), I'm a bit embarrassed I don't understand it yet, but I keep re-reading it and slowly seem to be getting there. –  Neostim Aug 13 '13 at 3:27
    
@Neostim Probably a better bet. You may also have the same performance issues, however. Unfortunately, I can't think of a way off the top of my head to drastically reduce the solution space. Maybe come to the solution by restricting the list from both ends. –  John Tseng Aug 13 '13 at 3:46
    
Thanks a lot for the help John! I'll keep trying with your algorithm, I'm confident it will at least be faster or move me in the right direction vs messing with the DB. –  Neostim Aug 13 '13 at 3:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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