Message-ID: <550BCB99.3050901@gmail.com>
Date: Fri, 20 Mar 2015 08:26:17 +0100
From: agharta <agharta82@gmail.com>
User-Agent: Mozilla/5.0 (X11; Linux x86_64;
 rv:31.0) Gecko/20100101 Thunderbird/31.3.0
MIME-Version: 1.0
To: "pgsql-sql@postgresql.org" <pgsql-sql@postgresql.org>
Subject: Re: Detect which sum of cartesian product (+ any combination
 of n records in tables) exceeds a value
References: <550AF9A7.2090404@gmail.com>
 <CAKFQuwY27=A_Y3HjndKhAQzZtg4Y3wAHfDCXvEiHL6fMciq_ng@mail.gmail.com>
In-Reply-To: 
 <CAKFQuwY27=A_Y3HjndKhAQzZtg4Y3wAHfDCXvEiHL6fMciq_ng@mail.gmail.com>
Content-Type: multipart/alternative;
 boundary="------------050004070702070108040007"
Precedence: bulk
Sender: pgsql-sql-owner@postgresql.org

This is a multi-part message in MIME format.
--------------050004070702070108040007
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit


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


--------------050004070702070108040007
Content-Type: text/html; charset=utf-8
Content-Transfer-Encoding: 8bit

<html>
  <head>
    <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
  </head>
  <body text="#000000" bgcolor="#FFFFFF">
    <div class="moz-cite-prefix"><br>
      On 03/19/2015 06:05 PM, David G. Johnston wrote:<br>
    </div>
    <blockquote
cite="mid:CAKFQuwY27=A_Y3HjndKhAQzZtg4Y3wAHfDCXvEiHL6fMciq_ng@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra"><br>
        </div>
        <div class="gmail_extra">
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif">​I likely
            would not be alive if I tried executing it on any
            non-trivial sized database though.</div>
        </div>
      </div>
    </blockquote>
    <br>
    Me too :) !<br>
    <br>
    <blockquote
cite="mid:CAKFQuwY27=A_Y3HjndKhAQzZtg4Y3wAHfDCXvEiHL6fMciq_ng@mail.gmail.com"
      type="cite">
      <div dir="ltr">
        <div class="gmail_extra">
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif"><br>
          </div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif">As an
            algorithm:</div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif"><br>
          </div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif">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</div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif"><br>
          </div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif">For each
            relation, if the sum of the value columns is &gt; 35 then
            every single row from the other table will provide a match. 
            This is your first output.</div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif"><br>
          </div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif">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.</div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif"><br>
          </div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif">Union All the
            two outputs together and you have your result.</div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif"><br>
          </div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif">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.</div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif"><br>
          </div>
          <div class="gmail_default"
            style="font-family:arial,helvetica,sans-serif">David J.</div>
        </div>
      </div>
    </blockquote>
    <br>
    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). <br>
    <br>
    I think that a simple &amp; dynamic (t4/t4/t4/t4... n times)
    solution is not possible, as 9.4 PG version. Correct me if i am
    wrong.<br>
    <br>
    <div id="gt-src-tools">
      <div id="gt-src-tools-l">
        <div style="display: inline-block;" id="gt-input-tool">
          <div id="itamenu"><span class="ita-kd-inputtools-div"></span></div>
        </div>
      </div>
    </div>
    <div id="gt-res-content" class="almost_half_cell">
      <div dir="ltr" style="zoom:1"><span id="result_box"
          class="short_text" lang="en"><span class="hps alt-edited">I
            hoped</span> <span class="hps">that there was</span> <span
            class="hps">a magic-trick-function that would resolve the
            problem. Nope. :(<br>
            <br>
            I need to review &amp; rewrite my db/application to solve
            the problem in another way. <br>
            <br>
          </span></span><br>
        <span id="result_box" class="short_text" lang="en"><span
            class="hps"><span id="result_box" class="short_text"
              lang="en"><span class="hps">I owe you</span> <span
                class="hps">a beer</span></span>, thanks a lot for your
            suggestions.<br>
            <br>
            <br>
            Cheers,<br>
            <br>
            Agharta<br>
            <br>
            <br>
          </span></span></div>
    </div>
    <br>
  </body>
</html>

--------------050004070702070108040007--