X-Original-To: pgsql-hackers-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by postgresql.org (Postfix) with ESMTP id 46E8D9DC831; Thu, 16 Feb 2006 13:15:14 -0400 (AST) Received: from postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 37805-05; Thu, 16 Feb 2006 13:15:13 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- X-Greylist: from auto-whitelisted by SQLgrey- Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by postgresql.org (Postfix) with ESMTP id E08159DC83D; Thu, 16 Feb 2006 13:15:11 -0400 (AST) 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 k1GHF8cO029278; Thu, 16 Feb 2006 12:15:08 -0500 (EST) To: "Craig A. James" cc: Markus Schaber , pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index In-reply-to: <43F4A7D8.4050907@modgraph-usa.com> References: <43F38867.6010701@gpdnet.co.uk> <19510.1140036968@sss.pgh.pa.us> <19779.1140038874@sss.pgh.pa.us> <43F39E53.1020009@gpdnet.co.uk> <20781.1140046109@sss.pgh.pa.us> <7.0.1.0.2.20060215194635.03b55da0@earthlink.net> <21615.1140052893@sss.pgh.pa.us> <7.0.1.0.2.20060215223710.03a7c618@earthlink.net> <20060216113522.GA3461@uio.no> <7.0.1.0.2.20060216071053.0385a1a8@earthlink.net> <43F481CD.2010509@logix-tt.com> <43F4A7D8.4050907@modgraph-usa.com> Comments: In-reply-to "Craig A. James" message dated "Thu, 16 Feb 2006 08:27:04 -0800" Date: Thu, 16 Feb 2006 12:15:08 -0500 Message-ID: <29277.1140110108@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.11 required=5 tests=[AWL=0.110] X-Spam-Score: 0.11 X-Spam-Level: X-Archive-Number: 200602/632 X-Sequence-Number: 79770 "Craig A. James" writes: > You can also use this trick when the optimizer is asked for "fastest first result." Say you have a cursor on a column of numbers with good distribution. If you do a bucket sort on the first two or three digits only, you know the first "page" of results will be in the first bucket. So you only need to apply qsort to that first bucket (which is very fast, since it's small), and you can deliver the first page of data to the application. This can be particularly effective in interactive situations, where the user typically looks at a few pages of data and then abandons the search. > I doubt this is very relevant to Postgres. A relational database has to be general purpose, and it's hard to give it "hints" that would tell it when to use this particular optimization. Actually, LIMIT does nicely for that hint; the PG planner has definitely got a concept of preferring fast-start plans for limited queries. The real problem in applying bucket-sort ideas is the lack of any datatype-independent way of setting up the buckets. Once or twice we've kicked around the idea of having some datatype-specific sorting code paths alongside the general-purpose one, but I can't honestly see this as being workable from a code maintenance standpoint. regards, tom lane