From: Craig A. James <cjames@modgraph-usa.com>
To: Markus Schaber <schabi@logix-tt.com>
Cc: pgsql-performance@postgresql.org
Cc: pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
Date: Thu, 16 Feb 2006 08:27:04 -0800
Message-ID: <43F4A7D8.4050907@modgraph-usa.com> (raw)
In-Reply-To: <43F481CD.2010509@logix-tt.com>
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>
<43F481CD.2010509@logix-tt.com>
Markus Schaber wrote:
> Ron wrote:
>>...and of course if you know enough about the data to be sorted so as to
>>constrain it appropriately, one should use a non comparison based O(N)
>>sorting algorithm rather than any of the general comparison based
>>O(NlgN) methods.
>
> Sounds interesting, could you give us some pointers (names, URLs,
> papers) to such algorithms?
Most of these techniques boil down to good ol' "bucket sort". A simple example: suppose you have a column of integer percentages, range zero to 100. You know there are only 101 distinct values. So create 101 "buckets" (e.g. linked lists), make a single pass through your data and drop each row's ID into the right bucket, then make a second pass through the buckets, and write the row ID's out in bucket order. This is an O(N) sort technique.
Any time you have a restricted data range, you can do this. Say you have 100 million rows of scientific results known to be good to only three digits -- it can have at most 1,000 distinct values (regardless of the magnitude of the values), so you can do this with 1,000 buckets and just two passes through the data.
You can also use this trick when the optimizer is asked for "fastest first result." Say you have a cursor on a column of numbers with good distribution. If you do a bucket sort on the first two or three digits only, you know the first "page" of results will be in the first bucket. So you only need to apply qsort to that first bucket (which is very fast, since it's small), and you can deliver the first page of data to the application. This can be particularly effective in interactive situations, where the user typically looks at a few pages of data and then abandons the search.
I doubt this is very relevant to Postgres. A relational database has to be general purpose, and it's hard to give it "hints" that would tell it when to use this particular optimization.
Craig
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: cjames@modgraph-usa.com, schabi@logix-tt.com, pgsql-hackers@postgresql.org
Subject: Re: qsort again (was Re: [PERFORM] Strange Create Index
In-Reply-To: <43F4A7D8.4050907@modgraph-usa.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