From: Ron <rjpeace@earthlink.net>
To: Ragnar <gnari@hive.is>
To: pgsql-performance@postgresql.org
To: pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create
Date: Fri, 17 Feb 2006 08:01:34 -0500
Message-ID: <7.0.1.0.2.20060217072626.039c5f20@earthlink.net> (raw)
In-Reply-To: <1140168261.32324.70.camel@localhost.localdomain>
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>
<1140168261.32324.70.camel@localhost.localdomain>
At 04:24 AM 2/17/2006, Ragnar wrote:
>On fös, 2006-02-17 at 01:20 -0500, Ron wrote:
> >
> > 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.
Why do you think that? External sorts involve
the equivalent of multiple scans of the table to
be sorted, sometimes more than lgN (where N is
the number of items in the table to be
sorted). Since this is physical IO we are
talking about, each scan is very expensive, and
therefore 1 scan is going to take considerably
less time than >= lgN scans will be.
>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.
Not sure you've got this right either. Looks to
me like we are adding a <= 32b quantity to each
row. Once we know the mapping, incrementally
updating it upon insert or update would seem to
be simple matter of a fast search for the correct
ranking [Interpolation search, which we have all
the needed data for, is O(lglgN). Hash based
search is O(1)]; plus an increment/decrement of
the key values greater/less than the key value of
the row being inserted / updated. Given than we
are updating all the keys in a specific range
within a tree structure, that update can be done
in O(lgm) (where m is the number of records affected).
> > 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?
??? We've effectively created a data set where
each record is a pointer to a DB row plus its
key. We can now sort the data set by key and
then do an optional final pass to rearrange the
actual DB rows if we so wish. Since that final
pass is very expensive, it is good that not all
use scenarios will need that final pass.
The amount of storage required to sort this
representation of the table rather than the
actual table is so much less that it turns an
external sorting problem into a internal sorting
problem with an optional final pass that is =1=
scan (albeit one scan with a lot of seeks and
data movement). This is a big win. It is a
variation of a well known technique. See Sedgewick, Knuth, etc.
> > 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 ?
Again, ??? btree indexes address different
issues. They do not in any way help create a
compact data representation of the original data
that saves enough space so as to turn an external
ranking or sorting problem into an internal one.
Ron
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 from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-performance@postgresql.org
Cc: rjpeace@earthlink.net, gnari@hive.is, pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create
In-Reply-To: <7.0.1.0.2.20060217072626.039c5f20@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> <1140168261.32324.70.camel@localhost.localdomain> <7.0.1.0.2.20060217072626.039c5f20@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