agora inbox for pgsql-sql@postgresql.org
help / color / mirror / Atom feedDetect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
4+ messages / 2 participants
[nested] [flat]
* Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
@ 2015-03-19 16:30 agharta <agharta82@gmail.com>
0 siblings, 1 reply; 4+ messages in thread
From: agharta @ 2015-03-19 16:30 UTC (permalink / raw)
To: pgsql-sql
Hi all,
I hope someone can helps me....
I have a problem detecting a sum of cartesian product of tables.
----------------------------
Test case:
//CREATE TABLES
create table t1 (
id serial,
field_1 integer);
create table t2 (
id serial,
field_1 integer);
create table t3 (
id serial,
field_1 integer);
create table t4 (
id serial,
field_1 integer);
//FILL TABLES
insert into t1 (field_1) select cast(random()*10 as integer) from
generate_series(1,10);
insert into t2 (field_1) select cast(random()*10 as integer) from
generate_series(1,10);
insert into t3 (field_1) select cast(random()*10 as integer) from
generate_series(1,10);
insert into t4 (field_1) select cast(random()*10 as integer) from
generate_series(1,10);
--------------------
Example: i have 4 tables with fields, i would detect which combination
of field_1 in any table exceed a value (eg. 35).
Simple, ugly & slow but simple:
select * from t1, t2,t3,t4 where t1.field_1 + t2.field_1 + t3.field_1 +
t4.field_1 >35
It works.
Now my question: i would determine which combination on field_1 of
t1,t2,t3 plus a combination(any) of 2 records on field_1 of t4,
exceeds a value (eg. 35)
It should be something like t1.field_1 + t2.field_1 + t3.field_1 + (
any combination of 2 records of t4.field_1) > 35
Suppose i have these records in tables (field_1), for simple explain of
my problem:
t1 = 1
t2 = 5
t3 = 4
t4 = 1,3,4
the combination of 2 record on t4.field_1 should be:
1+5+4 + ( 1+3)
1+5+4 + ( 1+4)
1+5+4 + ( 3+1)
1+5+4 + ( 3+4)
1+5+4 + ( 4+1)
1+5+4 + ( 4+3)
How to do it???
This is a static test case with a static (2 records) problem, in my
production db it could be any combination (2,3,4,5+ records ) of field_1
of any table.
Hope I was clear,
Best regards and thanks in advance,
Agharta
--
Sent via pgsql-sql mailing list (pgsql-sql@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-sql
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
@ 2015-03-19 17:05 David G. Johnston <david.g.johnston@gmail.com>
parent: agharta <agharta82@gmail.com>
0 siblings, 2 replies; 4+ messages in thread
From: David G. Johnston @ 2015-03-19 17:05 UTC (permalink / raw)
To: agharta <agharta82@gmail.com>; +Cc: 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.
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
@ 2015-03-20 07:26 agharta <agharta82@gmail.com>
parent: David G. Johnston <david.g.johnston@gmail.com>
1 sibling, 0 replies; 4+ messages in thread
From: agharta @ 2015-03-20 07:26 UTC (permalink / raw)
To: pgsql-sql
On 03/19/2015 06:05 PM, David G. Johnston wrote:
>
> I likely would not be alive if I tried executing it on any
> non-trivial sized database though.
Me too :) !
>
> 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.
You're right, this should be the fastest implementation possible, but
cross/cartesian matching is very slow with a huge amount of data (it is
natural).
I think that a simple & dynamic (t4/t4/t4/t4... n times) solution is not
possible, as 9.4 PG version. Correct me if i am wrong.
I hoped that there was a magic-trick-function that would resolve the
problem. Nope. :(
I need to review & rewrite my db/application to solve the problem in
another way.
I owe you a beer, thanks a lot for your suggestions.
Cheers,
Agharta
^ permalink raw reply [nested|flat] 4+ messages in thread
* Re: Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value
@ 2015-03-20 07:31 agharta <agharta82@gmail.com>
parent: David G. Johnston <david.g.johnston@gmail.com>
1 sibling, 0 replies; 4+ messages in thread
From: agharta @ 2015-03-20 07:31 UTC (permalink / raw)
To: David G. Johnston <david.g.johnston@gmail.com>; +Cc: pgsql-sql
On 03/19/2015 06:05 PM, David G. Johnston wrote:
>
> I likely would not be alive if I tried executing it on any
> non-trivial sized database though.
Me too :) !
>
> 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.
You're right, this should be the fastest implementation possible, but
cross/cartesian matching is very slow with a huge amount of data (it is
natural).
I think that a simple & dynamic (t4/t4/t4/t4... n times) solution is not
possible, as 9.4 PG version. Correct me if i am wrong.
I hoped that there was a magic-trick-function that would resolve the
problem. Nope. :(
I need to review & rewrite my db/application to solve the problem in
another way.
I owe you a beer, thanks a lot for your suggestions.
Cheers,
Agharta
^ permalink raw reply [nested|flat] 4+ messages in thread
end of thread, other threads:[~2015-03-20 07:31 UTC | newest]
Thread overview: 4+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2015-03-19 16:30 Detect which sum of cartesian product (+ any combination of n records in tables) exceeds a value agharta <agharta82@gmail.com>
2015-03-19 17:05 ` David G. Johnston <david.g.johnston@gmail.com>
2015-03-20 07:26 ` agharta <agharta82@gmail.com>
2015-03-20 07:31 ` agharta <agharta82@gmail.com>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox