November 26, 2014

Checking the subset sum set problem with set processing

Hi,

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

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:

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

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

About Justin Swanhart

Justin is a Principal Support Engineer on the support team. In the past, he was a trainer at Percona and a consultant. Justin also created and maintains Shard-Query, a middleware tool for sharding and parallel query execution and Flexviews, a tool for materialized views for MySQL. Prior to working at Percona Justin consulted for Proven Scaling, was a backend engineer at Yahoo! and a database administrator at Smule and Gazillion games.

Speak Your Mind

*