From: Ron Peacetree <rjpeace@earthlink.net>
To: Zeugswetter Andreas DAZ SD <ZeugswetterA@spardat.at>
To: pgsql-hackers@postgresql.org
To: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] A Better External Sort?
Date: Thu, 29 Sep 2005 22:57:19 -0400 (EDT)
Message-ID: <6812451.1128049039096.JavaMail.root@elwamui-polski.atl.sa.earthlink.net> (raw)
>From: Zeugswetter Andreas DAZ SD <ZeugswetterA@spardat.at>
>Sent: Sep 29, 2005 9:28 AM
>Subject: RE: [HACKERS] [PERFORM] A Better External Sort?
>
>>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).
>
"Collecting" the data rows can be done for each RAM buffer full of
of data in one pass through RAM after we've built the Btree. Then
if desired those data rows can be read out to HD in sorted order
in essentially one streaming burst. This combination of index build
+ RAM buffer rearrangement + write results to HD can be repeat
as often as needed until we end up with an overall Btree index and
a set of sorted sublists on HD. Overall HD IO for the process is only
two effectively sequential passes through the data.
Subsequent retrieval of the sorted information from HD can be
done at full HD streaming speed and whatever we've decided to
save to HD can be reused later if we desire.
Hope this helps,
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 using the --to and --cc options:
reply via email
To: pgsql-performance@postgresql.org
Cc: rjpeace@earthlink.net, ZeugswetterA@spardat.at, pgsql-hackers@postgresql.org
Subject: Re: [PERFORM] A Better External Sort?
In-Reply-To: <6812451.1128049039096.JavaMail.root@elwamui-polski.atl.sa.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