Skip site navigation (1) Skip section navigation (2)

Re: qsort again (was Re: [PERFORM] Strange Create

From: Scott Lamb <slamb(at)slamb(dot)org>
To: Ron <rjpeace(at)earthlink(dot)net>
Cc: Martijn van Oosterhout <kleptog(at)svana(dot)org>,pgsql-performance(at)postgresql(dot)org, pgsql-hackers(at)postgresql(dot)org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create
Date: 2006-02-16 17:19:24
Message-ID: 87FA36B4-CD97-4CF5-B9B3-02FEEA25CC95@slamb.org (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-performance
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:

(1) sort the values into an array
(2) use each value's array index as its key

It reduces to the problem you're trying to use it to solve.


-- 
Scott Lamb <http://www.slamb.org/>



In response to

Responses

pgsql-performance by date

Next:From: Tom LaneDate: 2006-02-16 17:27:36
Subject: Re: Why does not perform index combination
Previous:From: Tom LaneDate: 2006-02-16 17:15:08
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index

pgsql-hackers by date

Next:From: Dann CorbitDate: 2006-02-16 18:39:45
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Previous:From: Tom LaneDate: 2006-02-16 17:15:08
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group