Fastest way to generate combinations of rows

Question

We have a table of plans and each plan has many services. We would like a fast way of finding the combinations of plans that do not contain duplicate services but as a combinations contain certain services.

e.g. table of plans

id | service_1 | service_2 | ...
---------------------------------
1  |   true    |  true     | ...
2  |   true    |  false    | ...
3  |   false   |  true     | ...

e.g. valid combinations containing service_1 and service_2

UPDATE

If there were 2 services and I required both of them we would combine up to 2 rows (or plans) as they could contain at minimum 1 service in each.

id | service_1 | service_2 | id | service_1 | service_2 |
---------------------------------------------------------
1  |   true    |  true     |NULL|    NULL   |    NULL   |
2  |   true    |  false    | 3  |    false  |    true   |

UPDATE

It currently works by self left joining itself with aggressive pruning or rows. The query is dynamically generated based on the number of services. It creates the permutations of valid join conditions making it not practical to post.

Currently the cost is in the order of number of plans ^ number of services.

I'm mostly interested in other ways of solving this not necessarily improvements to the current way.

Answer 1

This seems to work ok

Setup data

DROP TABLE IF EXISTS plan;
CREATE TABLE plan (id int, service1 bool, service2 bool, service3 bool);
INSERT INTO `plan` (`id`, `service1`, `service2`, `service3`) VALUES (1, 1, 0, 0);
INSERT INTO `plan` (`id`, `service1`, `service2`, `service3`) VALUES (2, 0, 1, 0);
INSERT INTO `plan` (`id`, `service1`, `service2`, `service3`) VALUES (3, 1, 1, 1);
INSERT INTO `plan` (`id`, `service1`, `service2`, `service3`) VALUES (4, 1, 0, 1);
INSERT INTO `plan` (`id`, `service1`, `service2`, `service3`) VALUES (5, 0, 0, 1);

The query

select *
from plan A
left join (
    select id, service1, service2, service3 from plan
    union all
    select null, null, null, null) B on B.id > A.id or B.id is null
left join (
    select id, service1, service2, service3 from plan
    union all
    select null, null, null, null) C on C.id > B.id or C.id is null
WHERE (A.service1 + A.service2 + A.service3)
  AND (A.service1 + ifnull(B.service1,0) + ifnull(C.service1,0)) = 1
  AND (A.service2 + ifnull(B.service2,0) + ifnull(C.service2,0)) = 1
  AND (A.service3 + ifnull(B.service3,0) + ifnull(C.service3,0)) = 1

Result

id | service1 | service2 | service3 | id | service1 | service2 | service3 | id | service1 | service2 | service3
1 | 1 | 0 | 0 | 2 | 0 | 1 | 0 | 5 | 0 | 0 | 1
1 | 1 | 0 | 0 | 5 | 0 | 0 | 1 | 2 | 0 | 1 | 0
2 | 0 | 1 | 0 | 4 | 1 | 0 | 1 | NULL | NULL | NULL | NULL
2 | 0 | 1 | 0 | NULL | NULL | NULL | NULL | 4 | 1 | 0 | 1
3 | 1 | 1 | 1 | NULL | NULL | NULL | NULL | NULL | NULL | NULL | NULL