pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Markus Schaber <schabi@logix-tt.com>
To: Ron <rjpeace@earthlink.net>
Cc: Scott Lamb <slamb@slamb.org>
Cc: pgsql-performance@postgresql.org
Cc: pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create
Date: Fri, 17 Feb 2006 11:19:45 +0100
Message-ID: <43F5A341.5090808@logix-tt.com> (raw)
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>

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



view thread (56+ messages)  latest in thread

Message-ID: <43F5A341.5090808@logix-tt.com>
Permalink:  ../43F5A341.5090808@logix-tt.com/
Also on:    postgresql.org/message-id/43F5A341.5090808@logix-tt.com

 · 

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: schabi@logix-tt.com, rjpeace@earthlink.net, slamb@slamb.org, pgsql-hackers@postgresql.org
  Subject: Re: qsort again (was Re: [PERFORM] Strange Create
  In-Reply-To: <43F5A341.5090808@logix-tt.com>

* 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