Checking the subset sum set problem with set processing

May 16, 2011

Author

Justin Swanhart

MySQL

Share this Post:

Hi,

Here is an easy way to run the subset sum check from SQL, which you can then distribute with Shard-Query:

<br>CREATE TABLE `the list` (<br>  `id` bigint(20) NOT NULL AUTO_INCREMENT,<br>  `val` bigint(20) NOT NULL DEFAULT '0',<br>  PRIMARY KEY (`id`),<br>  KEY `id` (`id`)<br>) ENGINE=MyISAM;<br><br>SELECT val as `val`, COUNT(DISTINCT (id)) as `cd`<br>FROM  test.data as d  WHERE val in (-2,-3,-10,15,15,16)<br>GROUP BY val;<br>+-----+----------+----------+<br>| val | cd       | CNT      |<br>+-----+----------+----------+<br>| -10 |        1 |        1 |<br>|  -3 |        1 |        1 |<br>|  -2 |        1 |        1 |<br>|  15 | 35417088 | 35417088 |<br>+-----+----------+----------+<br>5 rows in set (40.20 sec)<br>

1

CREATE TABLE `the list` ( `id` bigint(20) NOT NULL AUTO_INCREMENT, `val` bigint(20) NOT NULL DEFAULT '0', PRIMARY KEY (`id`), KEY `id` (`id`) ) ENGINE=MyISAM; SELECT val as `val`, COUNT(DISTINCT (id)) as `cd` FROM test.data as d WHERE val in (-2,-3,-10,15,15,16) GROUP BY val; +-----+----------+----------+ | val | cd | CNT | +-----+----------+----------+ | -10 | 1 | 1 | | -3 | 1 | 1 | | -2 | 1 | 1 | | 15 | 35417088 | 35417088 | +-----+----------+----------+ 5 rows in set (40.20 sec)

Notice there is no 16 in the list. We did not pass the check. There are enough 15s though. The distinct value count for each item in the output set, must at least match the cardinality of each item in the input set).

Notice that I have a lot of numbers in my list:

<br>mysql&gt; select val, count(*) from data group by val;<br>+-----+----------+<br>| val | count(*) |<br>+-----+----------+<br>| -10 |        1 |<br>|  -3 |        1 |<br>|  -2 |        1 |<br>|   0 |   250000 |<br>|   4 |  8000000 |<br>|   7 | 14680064 |<br>|  14 | 14680064 |<br>|  15 | 35417088 |<br>+-----+----------+<br>8 rows in set (20.47 sec)<br>

1

mysql> select val, count(*) from data group by val; +-----+----------+ | val | count(*) | +-----+----------+ | -10 | 1 | | -3 | 1 | | -2 | 1 | | 0 | 250000 | | 4 | 8000000 | | 7 | 14680064 | | 14 | 14680064 | | 15 | 35417088 | +-----+----------+ 8 rows in set (20.47 sec)

Now insert a value which will cause our check to pass:

<br>mysql&gt; insert into data (val) values (16);<br>Query OK, 1 row affected (0.01 sec)<br><br>mysql&gt; SELECT val as `val`, COUNT(DISTINCT (id)) as `cd`<br> FROM  test.data as d<br>WHERE val in (-2,-3,-10,15,15,16)<br>GROUP BY val;<br>+-----+----------+<br>| val | cd       |<br>+-----+----------+<br>| -10 |        1 |<br>|  -3 |        1 |<br>|  -2 |        1 |<br>|  15 | 35417088 |<br>|  16 |        1 | &lt;-- now the check passes<br>+-----+----------+<br>5 rows in set (40.01 sec)<br>

1

mysql> insert into data (val) values (16); Query OK, 1 row affected (0.01 sec) mysql> SELECT val as `val`, COUNT(DISTINCT (id)) as `cd` FROM test.data as d WHERE val in (-2,-3,-10,15,15,16) GROUP BY val; +-----+----------+ | val | cd | +-----+----------+ | -10 | 1 | | -3 | 1 | | -2 | 1 | | 15 | 35417088 | | 16 | 1 | <-- now the check passes +-----+----------+ 5 rows in set (40.01 sec)

Of course, I can use a materialized view and check the expression in subsecond.