Message-ID: <434D08DB.6090409@brandywine.com>
Date: Wed, 12 Oct 2005 09:00:11 -0400
From: Daryl Richter <daryl@brandywine.com>
Reply-To: daryl@brandywine.com
Organization: Brandywine Asset Management
User-Agent: Mozilla Thunderbird 1.0.6 (Windows/20050716)
MIME-Version: 1.0
Cc: pgsql-sql@postgresql.org
Subject: Re: SEVEN cross joins?!?!?
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>
	<434CE6B8.5060106@archonet.com>
In-Reply-To: <434CE6B8.5060106@archonet.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Richard Huxton wrote:
> 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.
> 

I'll second this recommendation.  The OP is trying to drive a nail with 
a screwdriver.  He needs a program, not a query.

> That any help?
> -- 
>   Richard Huxton
>   Archonet Ltd
> 
> ---------------------------(end of broadcast)---------------------------
> TIP 5: don't forget to increase your free space map settings


-- 
Daryl Richter
(daryl (at)(brandywine dot com))