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 521989DC847; Thu, 16 Feb 2006 12:33:36 -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 30818-06; Thu, 16 Feb 2006 12:33:24 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- X-Greylist: from auto-whitelisted by SQLgrey- Received: from smtpauth01.mail.atl.earthlink.net (smtpauth01.mail.atl.earthlink.net [209.86.89.61]) by postgresql.org (Postfix) with ESMTP id 993A69DCD12; Thu, 16 Feb 2006 12:33:23 -0400 (AST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=dk20050327; d=earthlink.net; b=fr18u0hmtZS71avPDyLbCdjC/CzsWcC65mrkQXAjnnmefMQDBHc1pB5yyy/7hBU/; h=Received:Message-Id:X-Mailer:Date:To:From:Subject:In-Reply-To:References:Mime-Version:Content-Type:X-ELNK-Trace:X-Originating-IP; Received: from [24.34.169.163] (helo=ron-6d52adff2a6.earthlink.net) by smtpauth01.mail.atl.earthlink.net with asmtp (Exim 4.34) id 1F9m4F-0002dy-Cd; Thu, 16 Feb 2006 11:33:19 -0500 Message-Id: <7.0.1.0.2.20060216110249.0395d2b0@earthlink.net> X-Mailer: QUALCOMM Windows Eudora Version 7.0.1.0 Date: Thu, 16 Feb 2006 11:32:55 -0500 To: Martijn van Oosterhout , pgsql-performance@postgresql.org,pgsql-hackers@postgresql.org From: Ron Subject: Re: qsort again (was Re: [PERFORM] Strange Create In-Reply-To: <7.0.1.0.2.20060216100954.035b5ee0@earthlink.net> 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> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-ELNK-Trace: acd68a6551193be5d780f4a490ca69563f9fea00a6dd62bce0597794fc79c05ed81de0f7c21374cc350badd9bab72f9c350badd9bab72f9c350badd9bab72f9c X-Originating-IP: 24.34.169.163 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.439 required=5 tests=[AWL=-0.040, DNS_FROM_RFC_ABUSE=0.479] X-Spam-Score: 0.439 X-Spam-Level: X-Archive-Number: 200602/630 X-Sequence-Number: 79768 At 10:52 AM 2/16/2006, Ron wrote: >At 09:48 AM 2/16/2006, Martijn van Oosterhout wrote: > >>Where this does become interesting is where we can convert a datum to >>an integer such that if f(A) > f(B) then A > B. Then we can sort on >>f(X) first with just integer comparisons and then do a full tuple >>comparison only if f(A) = f(B). This would be much more cache-coherent >>and make these algorithms much more applicable in my mind. >In fact we can do better. >Using hash codes or what-not to map datums to keys and then sorting >just the keys and the pointers to those datums followed by an >optional final pass where we do the actual data movement is also a >standard technique for handling large data structures. I thought some follow up might be in order here. Let's pretend that we have the typical DB table where rows are ~2-4KB apiece. 1TB of storage will let us have 256M-512M rows in such a table. A 32b hash code can be assigned to each row value such that only exactly equal rows will have the same hash code. A 32b pointer can locate any of the 256M-512M rows. Now instead of sorting 1TB of data we can sort 2^28 to 2^29 32b+32b= 64b*(2^28 to 2^29)= 2-4GB of pointers+keys followed by an optional pass to rearrange the actual rows if we so wish. We get the same result while only examining and manipulating 1/50 to 1/25 as much data during the sort. If we want to spend more CPU time in order to save more space, we can compress the key+pointer representation. That usually reduces the amount of data to be manipulated to ~1/4 the original key+pointer representation, reducing things to ~512M-1GB worth of compressed pointers+keys. Or ~1/200 - ~1/100 the original amount of data we were discussing. Either representation is small enough to fit within RAM rather than requiring HD IO, so we solve the HD IO bottleneck in the best possible way: we avoid ever doing it. Ron