X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id E50F3D90C1; Fri, 23 Sep 2005 14:17:29 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 24366-10; Fri, 23 Sep 2005 17:17:27 +0000 (GMT) Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by svr1.postgresql.org (Postfix) with ESMTP id C2CB5D8F98; Fri, 23 Sep 2005 14:17:26 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.13.1/8.13.1) with ESMTP id j8NHHOoW005022; Fri, 23 Sep 2005 13:17:24 -0400 (EDT) To: Ron Peacetree Cc: Simon Riggs , pgsql-hackers@postgresql.org, pgsql-performance@postgresql.org Subject: Re: [PERFORM] Releasing memory during External sorting? In-reply-to: <2559192.1127494115558.JavaMail.root@elwamui-huard.atl.sa.earthlink.net> References: <2559192.1127494115558.JavaMail.root@elwamui-huard.atl.sa.earthlink.net> Comments: In-reply-to Ron Peacetree message dated "Fri, 23 Sep 2005 12:48:35 -0400" Date: Fri, 23 Sep 2005 13:17:24 -0400 Message-ID: <5021.1127495844@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.006 required=5 tests=[AWL=0.006] X-Spam-Level: X-Archive-Number: 200509/1020 X-Sequence-Number: 73417 Ron Peacetree writes: > 2= No optimal external sorting algorithm should use more than 2 passes. > 3= Optimal external sorting algorithms should use 1 pass if at all possible. A comparison-based sort must use at least N log N operations, so it would appear to me that if you haven't got approximately log N passes then your algorithm doesn't work. regards, tom lane