Re: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value - Mailing list pgsql-sql

From David G. Johnston
Subject Re: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
Date
Msg-id CAKFQuwY27=A_Y3HjndKhAQzZtg4Y3wAHfDCXvEiHL6fMciq_ng@mail.gmail.com
Whole thread
In response to Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value  (agharta <agharta82@gmail.com>)
Responses Re: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
Re: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
List pgsql-sql
On Thu, Mar 19, 2015 at 9:30 AM, agharta <agharta82@gmail.com> wrote:

It should be something like  t1.field_1 + t2.field_1 + t3.field_1 + ( any combination of  2 records of t4.field_1) > 35


​I could probably brute-force write such a query in maybe a half-hour.  I likely would not be alive if I tried executing it on any non-trivial sized database though.

As an algorithm:

Create two relations (temp tables/views/materialized views), one for t1/t2/t3 and one for t4/t4 each having a single row for every potential combination of rows.  Each table would contribute two values, the content of "field_1" and the primary key of the corresponding table.  The new PK would be a composite of all the contributing PKs

For each relation, if the sum of the value columns is > 35 then every single row from the other table will provide a match.  This is your first output.

Cross Join the two relations, after removing those in each that were matched above, and sum together all 5 fields.  This is your second output.

Union All the two outputs together and you have your result.

It can be done in one step but this at least gives you a prayer of executing in reasonable time for meaningfully sized datasets.  You can just write the second part and avoid the union until your data warrants the more complex, but likely faster, setup.

David J.

pgsql-sql by date:

Previous
From: agharta
Date:
Subject: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
Next
From: agharta
Date:
Subject: Re: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value