Bruce Momjian wrote:
>
> > >From what I remember, the quick sort algorithm works just as fast on
> > sorted data as on unsorted data. In other words, the algorithm does not
> > take advantage of the fact that the data is sorted.
> >
> > On the other hand, if you go to something like bubble sort, it will
> > work faster than quick sort if the data is sorted and you are adding one
> > more item, but on unsorted data it takes an enormously longer length of
> > time to sort a large list.
> >
>
> One thing I am going to look into is replacing the btree-build in the
^^^^^^^^^^^
> current psort with a qsort of HeapTuple pointers.
I don't fully understand what do you mean...
btree-build uses qsort to sort items on a page and has own
priority queue methods (instead of lselect.c - leftist tree
selection algorithm).
Do you want use qsort for in-memory sorts ?
BTW, I may suggest additional trick:
if size of sort-keys is (much?) smaller then size of tuple
(select _int4_field_, _big_text_field_ from ... order by _int4_field_)
and you are going to switch to tape-methods (i.e. you've pallocted
all sort-memory) then you may try to create temp-file to store
(unsorted) tuples there and to deal with sort-keys only. After
you'll got sort-keys (or better say - records which keep sort-keys
and pointers - temp-file offsets - to original tuples) sorted, you
may use these pointers to get requested tuple from temp-file.
Even for select int4_field from ... order by int4_field
current psort palloc 48(header) + 4 (field) + 4 (aligning) = 56 bytes
for each tuple - why don't work with 4(field) + 4 (offset) = 8 bytes
of sort-records (tm-:)) ?
Vadim
------------------------------
