Date: Thu, 29 Sep 2005 18:10:29 +0200
To: rjpeace@earthlink.net
Subject: Re: [PERFORM] A Better External Sort?
Cc: "Pg Hackers" <pgsql-hackers@postgresql.org>,
	pgsql-performance@postgresql.org
References: 
 <11604324.1127974870565.JavaMail.root@elwamui-polski.atl.sa.earthlink.net>
	<5A8CC216-2E25-4B8C-910A-69224D0A66CE@rilk.com>
From: PFC <lists@boutiquenumerique.com>
Organization: =?iso-8859-15?Q?La_Boutique_Num=E9rique?=
Content-Type: text/plain; format=flowed; delsp=yes; charset=iso-8859-15
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Message-ID: <op.sxvgjrceth1vuj@localhost>
In-Reply-To: <5A8CC216-2E25-4B8C-910A-69224D0A66CE@rilk.com>
User-Agent: Opera M2/8.0 (Linux, build 1095)


	Just to add a little anarchy in your nice debate...

	Who really needs all the results of a sort on your terabyte table ?

	I guess not many people do a SELECT from such a table and want all the  
results. So, this leaves :
	- Really wanting all the results, to fetch using a cursor,
	- CLUSTER type things, where you really want everything in order,
	- Aggregates (Sort->GroupAggregate), which might really need to sort the  
whole table.
	- Complex queries where the whole dataset needs to be examined, in order  
to return a few values
	- Joins (again, the whole table is probably not going to be selected)
	- And the ones I forgot.

	However,

	Most likely you only want to SELECT N rows, in some ordering :
	- the first N (ORDER BY x LIMIT N)
	- last N (ORDER BY x DESC LIMIT N)
	- WHERE x>value ORDER BY x LIMIT N
	- WHERE x<value ORDER BY x DESC LIMIT N
	- and other variants

	Or, you are doing a Merge JOIN against some other table ; in that case,  
yes, you might need the whole sorted terabyte table, but most likely there  
are WHERE clauses in the query that restrict the set, and thus, maybe we  
can get some conditions or limit values on the column to sort.

	Also the new, optimized hash join, which is more memory efficient, might  
cover this case.

	Point is, sometimes, you only need part of the results of your sort. And  
the bigger the sort, the most likely it becomes that you only want part of  
the results. So, while we're in the fun hand-waving, new algorithm trying  
mode, why not consider this right from the start ? (I know I'm totally in  
hand-waving mode right now, so slap me if needed).

	I'd say your new, fancy sort algorithm needs a few more input values :

	- Range of values that must appear in the final result of the sort :
		none, minimum, maximum, both, or even a set of values from the other  
side of the join, hashed, or sorted.
	- LIMIT information (first N, last N, none)
	- Enhanced Limit information (first/last N values of the second column to  
sort, for each value of the first column) (the infamous "top10 by  
category" query)
	- etc.

	With this, the amount of data that needs to be kept in memory is  
dramatically reduced, from the whole table (even using your compressed  
keys, that's big) to something more manageable which will be closer to the  
size of the final result set which will be returned to the client, and  
avoid a lot of effort.

	So, this would not be useful in all cases, but when it applies, it would  
be really useful.

	Regards !