optimizing a huge but simple mysql query of sums

Question

how would one go about finding solutions to all possible combinations of a,b,c,d,e,f where

a+b+c+d+e+f = x

given a,b,c,d,e,f are integers between 0-999 and x is a fixed integer

and the solution

a,b,c,d,e,f < y

(where each comma is a thousand separator)

ex. the huge number 304,153,525,784,175,764 is a solution to x=2705

since: 304+153+525+784+175+764 = 2705

here's a query i am trying for x=2705 and y=304153525784175764

SELECT 
    a.id,
    b.id,
    c.id,
    d.id,
    e.id,
    f.id,
    a.id+b.id+c.id+d.id+e.id+f.id AS sum
    a.id*1000*1000*1000*1000*1000+
    b.id*1000*1000*1000*1000+
    c.id*1000*1000*1000+
    d.id*1000*1000+
    e.id*1000+
    f.id AS solution
FROM a JOIN b JOIN c JOIN d JOIN e JOIN f
WHERE sum = 2705
AND solution <= 304153525784175764
ORDER BY solution DESC

how can one simplify this query which is currently far too big

is there perhaps a simpler way to get the solutions?

Other considerations.. Do you have any negative numbers? You are getting a Cartesian product of every combination. If tables are same structure, or same Actual table, just implied with different aliases to support Cartesian combination? If same table, is it valid for each table to join for ID = 1? ie: a.ID = 1, b.id = 1, c.id = 1... — DRapp, Dec 16 '19 at 22:38
@DRapp no negative numbers. if id=1 for all then how would this get any solutions? — user813801, Dec 17 '19 at 06:30
Perhaps we should instead reject the premise of the question. An RDBMS is for the storage and retrieval of data, and not much else. Problems concerning combinatorial/permutational mathematics would be best resolved in application code. — Strawberry, Dec 17 '19 at 09:17
@Strawberry good point. i thought maybe there was some sort of advantage in using sql over application code — user813801, Dec 17 '19 at 11:30

Rick James · Answer 1 · 2019-12-22T16:54:17.563

If a=000, then the problem degenerates to finding b..f such that b+c+d+e+f =2705. There will be an awfully large number of solutions (with 3-digit values). My point is that the resultset is too big; so no query can be 'reasonably sized'.

Anyway, I would approach it from a programming language, then think about moving to SQL:

for a in (000..304)   -- this is the main use for "y"
    for b in (000..999)
        if a + b > 2705 then break
        for c in (000..999)
            if a + b + c > 2705 then break
            for d in (000..999)
                if a + b + c + d > 2705 then break
                for e in (max(000, 2705-1000-(a+b+c+d))..999)
                    if a + b + c + d + e > 2705 then break
                    f = 2705 - (a + b + c + d + e);
                    if f between 000 and 999 then
                        print a,b,c,d,e,f

(Perhaps I would handle 304 separately. Or maybe stop b at 153 only when a==304.)

I cringe to think how long this would take to run in a well-optimized compiler. And cringe even more at the size of the temp tables needed to do the task in SQL.

thanks. brute force does seem to explode quickly. would be nice if there was an easier way — user813801, Dec 22 '19 at 07:06
I suspect there are billions of "answers" for the values of a..f. So, "brute force" is not to far from optimal. Actually, my answer here is possible close to optimal even though it smacks of brute force. I will add one line to help a little. — Rick James, Dec 22 '19 at 16:50
https://stackoverflow.com/a/59348491/813801 through a little script. gets it in seconds — user813801, Dec 24 '19 at 16:28

optimizing a huge but simple mysql query of sums

1 Answers1