Subject: Re: [HACKERS] qsort again (was Re: Strange Create
From: Ragnar <gnari@hive.is>
To: Ron <rjpeace@earthlink.net>
Cc: pgsql-performance@postgresql.org
In-Reply-To: <7.0.1.0.2.20060217004822.039d46a8@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>
	<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>
Content-Type: text/plain; charset=ISO-8859-1
Date: Fri, 17 Feb 2006 09:24:21 +0000
Message-Id: <1140168261.32324.70.camel@localhost.localdomain>
Mime-Version: 1.0
Content-Transfer-Encoding: 8bit

On fös, 2006-02-17 at 01:20 -0500, Ron wrote:
> At 01:47 PM 2/16/2006, Ron wrote:
> >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
> 
> 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 == b then f(a) == 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 sort you
want to replace/improve. If you want to keep this mapping
saved as a sort of an index, or as part ot each row data, this will make
the cost of inserts and updates enormous.

> 
> 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? If the 
mapping is kept separate from the tuple data, as in an index, then how
will you look up the key?

> 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 ?

gnari