pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Ron <rjpeace@earthlink.net>
To: Scott Lamb <slamb@slamb.org>
To: pgsql-performance@postgresql.org
To: pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create
Date: Thu, 16 Feb 2006 13:47:14 -0500
Message-ID: <7.0.1.0.2.20060216133801.03a7ab50@earthlink.net> (raw)
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>

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 





view thread (56+ messages)  latest in thread

Message-ID: <7.0.1.0.2.20060216133801.03a7ab50@earthlink.net>
Permalink:  ../7.0.1.0.2.20060216133801.03a7ab50@earthlink.net/
Also on:    postgresql.org/message-id/7.0.1.0.2.20060216133801.03a7ab50@earthlink.net

 · 

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: pgsql-performance@postgresql.org
  Cc: rjpeace@earthlink.net, slamb@slamb.org, pgsql-hackers@postgresql.org
  Subject: Re: qsort again (was Re: [PERFORM] Strange Create
  In-Reply-To: <7.0.1.0.2.20060216133801.03a7ab50@earthlink.net>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox