From: Jim C. Nasby <jnasby@pervasive.com>
To: Zeugswetter Andreas DAZ SD <ZeugswetterA@spardat.at>
Cc: Ron Peacetree <rjpeace@earthlink.net>
Cc: Jeffrey W. Baker <jwbaker@acm.org>
Cc: pgsql-hackers@postgresql.org
Cc: pgsql-performance@postgresql.org
Subject: Re: [HACKERS] A Better External Sort?
Date: Sat, 8 Oct 2005 17:51:55 -0500
Message-ID: <20051008225155.GA16679@pervasive.com> (raw)
In-Reply-To: <E1539E0ED7043848906A8FF995BDA5797EFA40@m0143.s-mxs.net>
References: <E1539E0ED7043848906A8FF995BDA5797EFA40@m0143.s-mxs.net>
On Thu, Sep 29, 2005 at 03:28:27PM +0200, Zeugswetter Andreas DAZ SD wrote:
>
> > In my original example, a sequential scan of the 1TB of 2KB
> > or 4KB records, => 250M or 500M records of data, being sorted
> > on a binary value key will take ~1000x more time than reading
> > in the ~1GB Btree I described that used a Key+RID (plus node
> > pointers) representation of the data.
>
> Imho you seem to ignore the final step your algorithm needs of
> collecting the
> data rows. After you sorted the keys the collect step will effectively
> access the
> tuples in random order (given a sufficiently large key range).
>
> This random access is bad. It effectively allows a competing algorithm
> to read the
> whole data at least 40 times sequentially, or write the set 20 times
> sequentially.
> (Those are the random/sequential ratios of modern discs)
True, but there is a compromise... not shuffling full tuples around when
sorting in memory. Do your sorting with pointers, then write the full
tuples out to 'tape' if needed.
Of course the other issue here is that as correlation improves it
becomes better and better to do full pointer-based sorting.
--
Jim C. Nasby, Sr. Engineering Consultant jnasby@pervasive.com
Pervasive Software http://pervasive.com work: 512-231-6117
vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461
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: jnasby@pervasive.com, ZeugswetterA@spardat.at, rjpeace@earthlink.net, jwbaker@acm.org, pgsql-hackers@postgresql.org
Subject: Re: [HACKERS] A Better External Sort?
In-Reply-To: <20051008225155.GA16679@pervasive.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