How do I make the following interaction with mySQL more efficient?

Question

I've got an array that contains combinations of unique MySql IDs:

For example:

[
 [1,10,11],
 [2,10],
 [3,10,12],
 [3,12,13,20],
 [4,12]
]

In total there are a couple hundred different combinations of IDs.

Some of these combinations are "valid" and some are not. For example, [1,10,11] may be a valid combination, whereas [3,10,12] may be invalid.

Combinations are valid or invalid depending on how the data is arranged in the database.

Currently I am using a SELECT statement to determine whether or not a specific combination of IDs is valid. It looks something like this:

SELECT id1 
FROM table
WHERE id2 IN ($combination)
GROUP BY id1
HAVING COUNT(distinct id2) = $number

...where $combination is one possible combination of IDs (eg 1,10,11) and $number is the number of IDs in that combination (in this case, 3). An invalid combination will return 0 rows. A valid combination will return 1 or more rows.

However, to solve the entire set of possible combinations means looping a couple hundred SELECT statements, which I would rather not be doing.

I am wondering: Are there any tricks for making this more efficient? Is it possible to submit the entire dataset to mySQL in one go, and have mySQL iterate through it? Any suggestions would be much appreciated.

Thanks in advance!

Answer 1

If I'm following your exaplantaion correctly, then....

Using the data you described earlier:

CREATE TABLE valid_combinations (
   combination_id INT NOT NULL,
   record_id INT NOT NULL
   PRIMARY KEY (record_id, combination_id),
   KEY (record_id)
)

Then...

INSERT INTO valid_combinations (combination_id, record_id)
VALUES (1, 1);
INSERT INTO valid_combinations (combination_id, record_id)
VALUES (1, 10);
INSERT INTO valid_combinations (combination_id, record_id)
VALUES (1, 11);

INSERT INTO valid_combinations (combination_id, record_id)
VALUES (2, 2);
INSERT INTO valid_combinations (combination_id, record_id)
VALUES (2,10);

... VALUES (5,12);

Then....

SELECT 1
FROM valid_combinations a
WHERE a.record_id IN ($combination)
AND NOT EXISTS (SELECT 1 FROM valid_combinations b
   WHERE b.record_id NOT IN ($combination)
   AND b.combination_id=a.combination_id);

However I don't really understand why you need to work out every possible combination.

My solution will probably be faster, however the order of the algorithm is no better than yours - just that the loop is moved to the database.

C.