From: | Markus Schaber <schabi(at)logix-tt(dot)com> |
---|---|
To: | Ron <rjpeace(at)earthlink(dot)net> |
Cc: | Scott Lamb <slamb(at)slamb(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-17 10:19:45 |
Message-ID: | 43F5A341.5090808@logix-tt.com |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers pgsql-performance |
Hi, Ron,
Ron schrieb:
> 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)
>
> Pretend each row is a integer of row size (so a 2KB row becomes a 16Kb
> integer; a 4KB row becomes a 32Kb integer; etc)
> Since even a 1TB table made of such rows can only have 256M - 512M
> possible values even if each row is unique, a 28b or 29b key is large
> enough to represent each row's value and relative rank compared to all
> of the others even if all row values are unique.
>
> 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.
But with a single linear scan, this cannot be accomplished, as the table
contents are neither sorted nor distributed linearly between the minimum
and the maximum.
For this mapping, you need a full table sort.
> 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.
But for every update or insert, you have to resort the keys, which is
_very_ expensive as it basically needs to update a huge part of the table.
Markus
From | Date | Subject | |
---|---|---|---|
Next Message | PFC | 2006-02-17 10:55:34 | Re: [HACKERS] qsort again (was Re: Strange Create |
Previous Message | Markus Schaber | 2006-02-17 10:13:41 | Re: qsort again (was Re: [PERFORM] Strange Create Index |
From | Date | Subject | |
---|---|---|---|
Next Message | PFC | 2006-02-17 10:55:34 | Re: [HACKERS] qsort again (was Re: Strange Create |
Previous Message | Markus Schaber | 2006-02-17 10:13:41 | Re: qsort again (was Re: [PERFORM] Strange Create Index |