From: Frank Bax <fbax@sympatico.ca>
To: pgsql-sql@postgresql.org
Subject: Re: SEVEN cross joins?!?!?
Date: Wed, 19 Oct 2005 06:42:33 -0400
Message-ID: <5.2.1.1.0.20051019054006.0455bec0@pop6.sympatico.ca> (raw)
In-Reply-To: <434E5B44.7080204@brandywine.com>
References: <5.2.1.1.0.20051012211223.00a34dd0@pop6.sympatico.ca>
<434CE6B8.5060106@archonet.com>
<5.2.1.1.0.20051011071510.0364d850@pop6.sympatico.ca>
<5.2.1.1.0.20051011071510.0364d850@pop6.sympatico.ca>
<5.2.1.1.0.20051011145705.00a31440@pop6.sympatico.ca>
<434CE6B8.5060106@archonet.com>
<5.2.1.1.0.20051012211223.00a34dd0@pop6.sympatico.ca>
At 09:04 AM 10/13/05, Daryl Richter wrote:
>Frank Bax wrote:
>
>[snip]
>
>>Richard, you've summed it up nicely.
>>Splitting locations into subsets (like 2,2,3) doesn't work because it is
>>possible that low values in one location can be offset by high values in
>>another location, and still result in an excellent combo.
>>The good news is these suggestions got me thinking outside the box. I
>>think I can program a modified brute-force that bypasses large numbers of
>>combos early. It might still be too large/slow, so I'd be interested in
>>finding more info about these "smarter algorithms" in option 2.
>>Where do I look?
>
>If you're mathematically inclined, I would first look at using
>Lagrangian Relexation, it may be appropriate for your problem:
>
>http://www.2112fx.com/lagrange.html
Thanks, but that's a little too complex for me to turn into code!
I did rewrite my code from a simple cross join SQL in PHP to custom
searching in perl. I sucked subselects into arrays and then looked at all
possible combinations.
For those that forgot/missed the background, my table has 514 rows. Using
subselect, this table is split into 7 subtables. These seven subtables are
cross joined with each other to produce 770 billion rows that need to be
searched (to assemble a 'made-to-order' suit of armour).
By using more intelligent code (and not simple brute-force), I was able to
analyse a complete set of 770 billion states in just under 70 hours on a
P4-2.8Ghz system, which is fast enough for today. A faster cpu will help,
since process does no i/o except at beginning and end of script. I realised
that if I am ever able to figure out coding for multi-processor or systems
(even remote like set@home), I can exploit either/both of these for this
problem by slitting problem on items in first subtable into 50-60 subtasks,
then merging results from each of those subtasks. This might become a
requirement if the underlying table grows to be quite large.
Thanks for pointing me in the right direction, it's been an interesting week.
Frank
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-sql@postgresql.org
Cc: fbax@sympatico.ca
Subject: Re: SEVEN cross joins?!?!?
In-Reply-To: <5.2.1.1.0.20051019054006.0455bec0@pop6.sympatico.ca>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox