Select all from A and join all non-repeating combinations from B so that : ab, ac, ad, abc, abd... in MySQL?

I have a table A with food products.

I have a table B with food addons.

Table B has the fields:

• price
• added_calories
• name
• products

I want to make such query that will get the top 10 (or more) combinations of product and addons that will result the best calories / price ratio . I need to keep the names of the addons and product to display to the user.

I should be able to have several addons on 1 product so that I should try and run through all combinations.

If we have addons a, b, c, d then I have to try the combinations:

• Product + a
• Product + b
• Product + ab
• Product + ac
• Product + ad
• Product + bc
• Product + bd
• ...

Not every addon can开发者_StackOverflow中文版 be selected for each product. There's an additional 'connector' table which indicates supported addons for a product.

Assuming that you want to maximize calories / price, I think this is doable. The trick is that, given a specific product, you'll maximize calories / price by piling on add-ons, in descending order by calories / price ratio, until the total ratio starts to decrease.

The following query is probably ridiculously inefficient and in need of serious optimization, but at least it shows that a solution exists:

SELECT
  p.name AS product,
  GROUP_CONCAT(a.name) AS additives,
  p.price + COALESCE(SUM(a.price), 0) AS price,
  p.calories + COALESCE(SUM(a.added_calories), 0) AS calories,
  (p.calories + COALESCE(SUM(a.added_calories), 0)) /
    (p.price + COALESCE(SUM(a.price), 0)) AS calories_per_price
FROM
  products AS p
  LEFT JOIN connector AS c ON c.product = p.id
  LEFT JOIN additives AS a
    ON a.id = c.additive
    AND (a.added_calories / a.price) > (
      (p.calories + COALESCE((
        SELECT SUM(b.added_calories) FROM connector AS d, additives AS b
        WHERE d.product = p.id AND b.id = d.additive
          AND (b.added_calories / b.price) > (a.added_calories / a.price)
      ), 0)) /
      (p.price + COALESCE((
        SELECT SUM(b.price) FROM connector AS d, additives AS b
        WHERE d.product = p.id AND b.id = d.additive
          AND (b.added_calories / b.price) > (a.added_calories / a.price)
      ), 0))
    )
GROUP BY p.id
ORDER BY calories_per_price DESC
LIMIT 10;

Edit: OK, I debugged it, now it actually works(!). Here's some test data:

INSERT INTO products (id, name, calories, price) VALUES
  (1, 'Cardboard', 0, 1),
  (2, 'Lard', 1000, 100),
  (3, 'Spaghetti', 10, 50);
INSERT INTO additives (id, name, added_calories, price) VALUES
  (1, 'Salt', 0, 2),
  (2, 'Butter', 500, 100),
  (3, 'Cheese', 300, 70),
  (4, 'Pepper', 0, 3),
  (5, 'Ketchup', 50, 10),
  (6, 'Milk', 20, 10);
INSERT INTO connector (product, additive) VALUES
  (1,1), (1,2), (1,3), (1,4), (1,5), (1,6),
  (2,1), (2,3), (2,4), (2,5),
  (3,1), (3,2), (3,3), (3,4), (3,5);

And results:

+-----------+-----------------------+-------+----------+--------------------+
| product   | additives             | price | calories | calories_per_price |
+-----------+-----------------------+-------+----------+--------------------+
| Lard      | NULL                  |   100 |     1000 |                 10 | 
| Cardboard | Butter,Ketchup        |   111 |      550 |   4.95495495495495 | 
| Spaghetti | Butter,Cheese,Ketchup |   230 |      860 |   3.73913043478261 | 
+-----------+-----------------------+-------+----------+--------------------+

Edit 2: Oops, I had it maximizing price per calories instead of calories per price. Fixed.

Edit 3: The subqueries were ignoring the connector table. I've (hopefully) fixed that bug, but I haven't been able to test it yet.