Re: Implementing Sorting Refinements

You'll get better response if you don't hijack threads. :) Also,
there's nothing in here that describes what the benefits of this
change are.

On Jan 1, 2008, at 2:09 PM, Manolo _ wrote:

>
> Hi to all.
>
> This mail is aimed at asking some suggestion to face PostgreSQL
> (PG) development to implement a refinement to PG source code. I'll
> briefly summarize the idea of the "2-Way Replacement
> Selection" (2WRS) refinement, just in case. If you already remember
> what 2WRS is, you can please jump directly to the IMPLEMENTATION
> ISSUES part of this mail.
>
>
> 2WRS.
> Refinement of the Replacement Selection (RS) technique currently
> used by PG in src/backend/utils/sort/tuplesort.c .
> The 2WRS uses two heaps instead of just one in order to create the
> current (logical) run. Here there are some fundamental points of
> the 2WRS technique:
> - 'qsort' the initial unsorted 'memtuples' array
> - divide the 'memtuples' array into two parts and each of those
> will be managed as a heap
> - one of the heaps will arrange its elements in ascending order,
> while the other heap in descending order
> - each heap will spill its current root in its corresponding run
> (i.e.: we have a run per each of those two heaps), so we are
> actually creating 2 physical current runs
> - those 2 current physical runs could "theoretically" be merged
> into the same logical run, actually we can make 'mergesort' think
> they do belong to the same physical run. That reduces the number of
> comparisons 'mergesort' has to do at each merge step (that means
> less seek delay time on mass storage). We can also think the
> average length of logical runs produced by 2WRS will probably be
> greater than the average length produced by RS (again less seek
> delay time: the longer each run the less number of final runs
> produced, that means the less number of comparisons at each
> 'mergesort' step).
>
>
> IMPLEMENTATION ISSUES.
> Where to place those heaps?
> 1) I think that both heaps could be arranged on the same
> 'memtuples' array. That allows easily subsequent resizing those
> heaps according to their effective use or according to some
> heuristic, without reallocating memory.
>
> How to arrange those heaps?
> 2a) It's convenient to arrange those heaps "root to root". That is
> arranging those heaps with their roots toward the center of
> 'memtuples' (in a way we can say they lay "face to face", or "root
> to root" as said before) while their leaves lay towards the extreme
> indexes of the 'memtuples' array (that is the last leaf of one heap
> will lay at index 0, the last leaf of the other heap laying at
> index memtupsize-1. This arrangement prevents overlapping elements
> between those physical runs associated to the same current logical
> run.
> PRO: once we qsort memtuples and divide it into 2 parts we already
> get those two heaps, no need to build them.
> CONTRA: ???
>
> 2b) As in 2a) but arranging heaps "leaf to leaf", that is their
> roots will lay at the extreme indexes of 'memtuples' while their
> leaves towards the center of the 'memtuples' array.
> Or even start building heaps as soon as we get initial elements,
> instead of qsort the whole 'memtuples' array.
> Any PRO/CONTRA compared to 2a)???
>
> Current run numbers
> I think I should duplicate the 'int currentRun' variable in the
> Tuplesortstate struct. I'll replace it with a 'int currentRunUP'
> and 'int currentRunDOWN' variables in order to distinguish those
> two physical runs associated to those 2 heaps. In this case I will
> give a run number (max{currentRunUP,currentRunDOWN} + 1) to
> elements not belonging to the current logical run. I suppose no
> need to touch 'long availMem' nor 'long allowedMem' variables nor
> any others.
>
> Heap functions
> I will duplicate all the heap management functions in order to
> adapt them to the kind of heap they should be applied to (for
> example, the tuplesort_heap_siftup function should be replaced with
> tuplesort_heap_siftupUP and tuplesort_heap_siftupDOWN functions).
>
> Merge Plan
> This technique would use a sort of "merge plan" to instruct
> mergesort on how to use those physical runs. Actually mergesort
> should consider at first "odd runs" before "pair runs". That is,
> for example, mergesort should start merging runs with run number
> 1,3,5,7,... and when run number X terminates start considering run
> number X+1. Obviously that doesn't need any merge plan, but I
> remember someone else (as Simon Riggs) was interested in sorting
> improvements so it could be a good thing to know if I should
> consider any conventions or paramethers in order to possibly create
> that merge plan.
>
>
> DEVELOPMENT CONTEXT
> I preferred to use the "last stable release" at the moment, that is
> 8.2.
>
>
> Any comment/suggestion/advice ?
>
> Thanks for your attention and for your time.
> Regards, Manolo.
> _________________________________________________________________
> Express yourself instantly with MSN Messenger! Download today it's
> FREE!
> http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/
> ---------------------------(end of
> broadcast)---------------------------
> TIP 4: Have you searched our list archives?
>
> http://archives.postgresql.org
>

--
Decibel!, aka Jim C. Nasby, Database Architect decibel(at)decibel(dot)org
Give your computer some brain candy! www.distributed.net Team #1828