Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtp (Exim 4.80) (envelope-from ) id 1YYrNw-0002FP-1n for pgsql-sql@arkaria.postgresql.org; Fri, 20 Mar 2015 07:30:24 +0000 Received: from localhost ([127.0.0.1] helo=postgresql.org) by malur.postgresql.org with smtp (Exim 4.80) (envelope-from ) id 1YYrNv-0005we-DG for pgsql-sql@arkaria.postgresql.org; Fri, 20 Mar 2015 07:30:23 +0000 Received: from makus.postgresql.org ([2001:4800:1501:1::229]) by malur.postgresql.org with esmtps (TLS1.2:DHE_RSA_AES_256_CBC_SHA256:256) (Exim 4.80) (envelope-from ) id 1YYrNu-0005wX-3O for pgsql-sql@postgresql.org; Fri, 20 Mar 2015 07:30:22 +0000 Received: from mail-wg0-x232.google.com ([2a00:1450:400c:c00::232]) by makus.postgresql.org with esmtps (TLS1.2:RSA_AES_256_CBC_SHA1:256) (Exim 4.80) (envelope-from ) id 1YYrNm-0000BZ-Mz for pgsql-sql@postgresql.org; Fri, 20 Mar 2015 07:30:20 +0000 Received: by wgbcc7 with SMTP id cc7so81915674wgb.0 for ; Fri, 20 Mar 2015 00:30:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=message-id:disposition-notification-to:date:from:user-agent :mime-version:to:cc:subject:references:in-reply-to:content-type; bh=R8znEIRvfM6AFm3VU2oBUjklSfG0hV795lowyiKR76g=; b=fsipmlRZ8ex/shLKXZydsulzuHTH7U7S1tATaTyNVzXeVQ8UD2nn5hdLJdysZ/2Ehf iwQ0sdLA0zIpfti/j7bRb6VVYVsY0eCIUoVk4boeoKCqHpLCHVs2wcE/7xBnXlF9iFFw mvMkWB46WOblmnbhcbRZjBolORU+Z3PNWGf/5enxARmpIgUq59i2X0nOCpc0MCjw6Vls 47UEetKRnc64Fo6qLeX09h/t+RR5ablJDwu1Jjwnqdlywm10G/Eq5gtj1ujVdBb6lNzX cLKoy5cTKq9ipc+LjzHjhAvvm2DoXRw4Ui8Do/DonSa17dPXENhQI0KNQRqwnV6xiOWB pOYw== X-Received: by 10.194.75.168 with SMTP id d8mr161277184wjw.87.1426836612928; Fri, 20 Mar 2015 00:30:12 -0700 (PDT) Received: from [192.168.1.221] (hf5.z1.infracom.it. [82.193.17.245]) by mx.google.com with ESMTPSA id kr5sm5137446wjc.1.2015.03.20.00.30.11 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 20 Mar 2015 00:30:12 -0700 (PDT) Message-ID: <550BCCBB.7070109@gmail.com> Date: Fri, 20 Mar 2015 08:31:07 +0100 From: agharta User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:31.0) Gecko/20100101 Thunderbird/31.3.0 MIME-Version: 1.0 To: "David G. Johnston" CC: "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> In-Reply-To: Content-Type: multipart/alternative; boundary="------------090008080700060609010804" X-Pg-Spam-Score: -2.4 (--) List-Archive: List-Help: List-ID: List-Owner: List-Post: List-Subscribe: List-Unsubscribe: X-Mailing-List: pgsql-sql Precedence: bulk Sender: pgsql-sql-owner@postgresql.org This is a multi-part message in MIME format. --------------090008080700060609010804 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 --------------090008080700060609010804 Content-Type: text/html; charset=utf-8 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



--------------090008080700060609010804--