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 C08A39DCBA3; Thu, 16 Feb 2006 14:47:22 -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 56890-03; Thu, 16 Feb 2006 14:47:22 -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 AEE519DCB63; Thu, 16 Feb 2006 14:47:19 -0400 (AST) DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=dk20050327; d=earthlink.net; b=bALduVVYWIvQ5B+fiXuva5UlYKZn2mNUDAjxtvrkCkn7ZIlN8Az6wZilSO5WayJG; 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 1F9o9v-0004Mf-63; Thu, 16 Feb 2006 13:47:19 -0500 Message-Id: <7.0.1.0.2.20060216133801.03a7ab50@earthlink.net> X-Mailer: QUALCOMM Windows Eudora Version 7.0.1.0 Date: Thu, 16 Feb 2006 13:47:14 -0500 To: Scott Lamb ,pgsql-performance@postgresql.org, pgsql-hackers@postgresql.org From: Ron Subject: Re: qsort again (was Re: [PERFORM] Strange Create In-Reply-To: <87FA36B4-CD97-4CF5-B9B3-02FEEA25CC95@slamb.org> 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> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-ELNK-Trace: acd68a6551193be5d780f4a490ca69563f9fea00a6dd62bc16fc814c666dc5d7a546f17257a8d2de350badd9bab72f9c350badd9bab72f9c350badd9bab72f9c X-Originating-IP: 24.34.169.163 X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.452 required=5 tests=[AWL=-0.027, DNS_FROM_RFC_ABUSE=0.479] X-Spam-Score: 0.452 X-Spam-Level: X-Archive-Number: 200602/635 X-Sequence-Number: 79773 At 12:19 PM 2/16/2006, Scott Lamb wrote: >On Feb 16, 2006, at 8:32 AM, Ron wrote: >>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. > >I don't understand this. > >This is a true statement: (H(x) != H(y)) => (x != y) >This is not: (H(x) < H(y)) => (x < y) > >Hash keys can tell you there's an inequality, but they can't tell you >how the values compare. If you want 32-bit keys that compare in the >same order as the original values, here's how you have to get them: For most hash codes, you are correct. There is a class of hash or hash-like codes that maintains the mapping to support that second statement. More later when I can get more time. Ron