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 350D69DC891; Fri, 17 Feb 2006 09:01:41 -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 27669-09; Fri, 17 Feb 2006 09:01:43 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- X-Greylist: from auto-whitelisted by SQLgrey- Received: from elasmtp-junco.atl.sa.earthlink.net (elasmtp-junco.atl.sa.earthlink.net [209.86.89.63]) by postgresql.org (Postfix) with ESMTP id 6A96D9DC868; Fri, 17 Feb 2006 09:01:38 -0400 (AST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=dk20050327; d=earthlink.net; b=MPZNWZ8XkErpCssaHtA7I+SvjGnLokKEF5Z8SAzU1DKAh5rORh5NDMcgMqAR+wzl; h=Received:Message-Id:X-Mailer:Date:To:From:Subject:In-Reply-To:References:Mime-Version:Content-Type:Content-Transfer-Encoding:X-ELNK-Trace:X-Originating-IP; Received: from [71.243.43.186] (helo=ron-6d52adff2a6.earthlink.net) by elasmtp-junco.atl.sa.earthlink.net with asmtp (Exim 4.34) id 1FA5Ez-000756-92; Fri, 17 Feb 2006 08:01:41 -0500 Message-Id: <7.0.1.0.2.20060217072626.039c5f20@earthlink.net> X-Mailer: QUALCOMM Windows Eudora Version 7.0.1.0 Date: Fri, 17 Feb 2006 08:01:34 -0500 To: Ragnar ,pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org From: Ron Subject: Re: qsort again (was Re: [PERFORM] Strange Create In-Reply-To: <1140168261.32324.70.camel@localhost.localdomain> 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> <20060216144833.GG26127@svana.org> <7.0.1.0.2.20060216100954.035b5ee0@earthlink.net> <7.0.1.0.2.20060216110249.0395d2b0@earthlink.net> <87FA36B4-CD97-4CF5-B9B3-02FEEA25CC95@slamb.org> <7.0.1.0.2.20060216133801.03a7ab50@earthlink.net> <7.0.1.0.2.20060217004822.039d46a8@earthlink.net> <1140168261.32324.70.camel@localhost.localdomain> Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1"; format=flowed Content-Transfer-Encoding: quoted-printable X-ELNK-Trace: acd68a6551193be5d780f4a490ca69563f9fea00a6dd62bc98a3719bad45c719a78c5732130994cf350badd9bab72f9c350badd9bab72f9c350badd9bab72f9c X-Originating-IP: 71.243.43.186 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.469 required=5 tests=[AWL=-0.010, DNS_FROM_RFC_ABUSE=0.479] X-Spam-Score: 0.469 X-Spam-Level: X-Archive-Number: 200602/657 X-Sequence-Number: 79795 At 04:24 AM 2/17/2006, Ragnar wrote: >On f=F6s, 2006-02-17 at 01:20 -0500, Ron wrote: > > > > OK, so here's _a_ way (there are others) to obtain a mapping such that > > if a < b then f(a) < f (b) and > > if a =3D=3D b then f(a) =3D=3D f(b) > > > By scanning the table once, we can map say 0000001h (Hex used to ease > > typing) to the row with the minimum value and 1111111h to the row > > with the maximum value as well as mapping everything in between to > > their appropriate keys. That same scan can be used to assign a > > pointer to each record's location. > >This step is just as expensive as the original=20 >sort you want to replace/improve. Why do you think that? External sorts involve=20 the equivalent of multiple scans of the table to=20 be sorted, sometimes more than lgN (where N is=20 the number of items in the table to be=20 sorted). Since this is physical IO we are=20 talking about, each scan is very expensive, and=20 therefore 1 scan is going to take considerably=20 less time than >=3D lgN scans will be. >If you want to keep this mapping saved as a sort=20 >of an index, or as part ot each row data, this=20 >will make the cost of inserts and updates enormous. Not sure you've got this right either. Looks to=20 me like we are adding a <=3D 32b quantity to each=20 row. Once we know the mapping, incrementally=20 updating it upon insert or update would seem to=20 be simple matter of a fast search for the correct=20 ranking [Interpolation search, which we have all=20 the needed data for, is O(lglgN). Hash based=20 search is O(1)]; plus an increment/decrement of=20 the key values greater/less than the key value of=20 the row being inserted / updated. Given than we=20 are updating all the keys in a specific range=20 within a tree structure, that update can be done=20 in O(lgm) (where m is the number of records affected). > > We can now sort the key+pointer pairs instead of the actual data and > > use an optional final pass to rearrange the actual rows if we wish. > >How are you suggesting this mapping be accessed?=20 >If the mapping is kept separate from the tuple=20 >data, as in an index, then how will you look up the key? ??? We've effectively created a data set where=20 each record is a pointer to a DB row plus its=20 key. We can now sort the data set by key and=20 then do an optional final pass to rearrange the=20 actual DB rows if we so wish. Since that final=20 pass is very expensive, it is good that not all=20 use scenarios will need that final pass. The amount of storage required to sort this=20 representation of the table rather than the=20 actual table is so much less that it turns an=20 external sorting problem into a internal sorting=20 problem with an optional final pass that is =3D1=3D=20 scan (albeit one scan with a lot of seeks and=20 data movement). This is a big win. It is a=20 variation of a well known technique. See Sedgewick, Knuth, etc. > > That initial scan to set up the keys is expensive, but if we wish > > that cost can be amortized over the life of the table so we don't > > have to pay it all at once. In addition, once we have created those > > keys, then can be saved for later searches and sorts. > >What is the use case where this would work better than a >regular btree index ? Again, ??? btree indexes address different=20 issues. They do not in any way help create a=20 compact data representation of the original data=20 that saves enough space so as to turn an external=20 ranking or sorting problem into an internal one. Ron=20