From: Richard Huxton <dev@archonet.com>
To: Frank Bax <fbax@sympatico.ca>
Cc: pgsql-sql@postgresql.org
Subject: Re: SEVEN cross joins?!?!?
Date: Wed, 12 Oct 2005 11:34:32 +0100
Message-ID: <434CE6B8.5060106@archonet.com> (raw)
In-Reply-To: <5.2.1.1.0.20051011145705.00a31440@pop6.sympatico.ca>
References: <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>
Frank Bax wrote:
>> Are you saying that you WANT to generate a cross-join, score the
>> millions of results and then pick the best 10? It's doing what you
>> want, but you'd like it to be faster.
>>
>> Or are you saying that you'd like to avoid the explosion in rows
>> altogether?
>>
>> In either case - I don't suppose you could provide a real example of
>> the query, so we can see exactly what you're trying to do.
>
>
> There is no "best 10". I currently limit each subselect to 10 items so
> that query will actually run without crashing. I would like to remove
> the "ORDER BY itemid LIMIT 10" mentioned above. At the end of the query
> I have a "LIMIT 100" clause which will stay and produces a list of "best
> 100" combos.
>
> Either of your solutions would be acceptable; since avoiding the
> "explosion" would also make the query faster. Current calculations
> indicate that running the query without "LIMIT 10" in subselect would
> take years to process.
OK - so at the heart of the problem is the fact that you want to search
a space with 100 billion possible states. There are three main options
1. Brute force and patience - simple and is guaranteed to produce the
"best" answers. You can use cursors/multiple queries to manage the
workload. The disadvantage is that it's probably slower than you'd like.
2. Smarter algorithms - possibly something genetic to work towards local
maxima. Or, if you'd like to keep it simple, just split your 7 locations
into 2,2,3 and solve for each separately.
3. Statistical - examine a subset of possible states and accept you'll
only be able to say "almost best" to 99% confidence or similar.
I'd be tempted by #2 - there are probably some combinations you can rule
out, which combined with a split/recombine should reduce the number of
states to query.
That any help?
--
Richard Huxton
Archonet Ltd
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: dev@archonet.com, fbax@sympatico.ca
Subject: Re: SEVEN cross joins?!?!?
In-Reply-To: <434CE6B8.5060106@archonet.com>
* 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