Hi to all.

I'm implementing a refinement of the External Sorting (ES) algorithm 
[postgresql-8.2.5/src/backend/utils/sort/tuplesort.c] . The patch is still WIP.
Here it follows the explanation of my refinement. Please ask ask ask for any 
kind of related question.
At the moment I'm stuck on what I'll write on the "*** HOW TO ? ***" part of 
this mail. At least please jump directly to that part please.

"Two Way Replacement Selection" (2WRS)
Recall current ES is implemented through Replacement Selection (RS) [as for run 
formation] and Polyphase Merge (PM) to merge [when RS terminates] all of the 
runs built by RS.
As for the run formation phase, this technique uses 2 heaps instead of just one 
as in the current PostgreSQL version of RS: that's why we call it "Two Way 
Replacement Selection" (2WRS).

What I do is:
1) fill the 'memtuples' array
2) qsort 'memtuples' and divide it into two [suppose equal] part: HeapUP and 
HeapDOWN, each heap builds it's own "physical run" respectively a runUP and a 
3) a new input tuple exclusively goes into one of those two heaps: the 
corresponding root of the destination heap is written into the physical run 
associated to that heap
4) when one of the heap is over we stop building the corresponding run and 
possibly go on executing using only the other one, in case it isn't still over. 
When both heaps are over, we start building the next "logical run"
5) repeat steps from 2 to 4 until the input is over.

That is the refinement to the phase of "run formation".
More details.

*** THE HEAPS ***
After dividing memory we obtain 2 heaps arranged in a "sand clock" way. 
In a way we could say HeapUP is an "upside down" heap, while HeapDOWN is an 
"ordinary heap".
Both heaps have their own root towards the center of 'memtuples'. They are not 
communicating in any way: each of them builds its own physical run.

It's what should be passed to the merge phase. It would be obtained by reading 
backward the corresponding runUP and appending the corresponding runDOWN to it. 
Of course we should avoid making useless "extra work" joining those two runs, 
we could just take in account their arrangement while merging.

Any change to the current merge algorithm [Polyphase Merge] is not taken in 
account at the moment. Now I'd just like to test the technique supposing the 
Polyphase Merge gets correctly the "logical run" in the same way it 
got/wrote/red the ordinary runs. Recall the runUP should be red backward while 
merging and that actually 2WRS produces two physical runs instead of just one. 
That's why, at the moment, I prefer making that above "extra work" to 
physically join those two part [runUP and runDOWN associated to the same 
logical run] to prove that we do build logical runs longer than ordinary runs 
built by current RS.

*** TODO ***
Temporarily write runUP and runDOWN in a tape different from destTape and join 
them into destTape when we finish building them.

*** HOW TO ? ***
How to do that joining those two runs? I should know the position on disk (?) 
where the first and the last tuple of a certain run are stored. I tried to 
follow all of the function calls made starting from LogicalTapeWrite() but I 
get lost into the various buffers used before finally writing to disk. Is there 
any other way to get that info? Actually I suppose BufFile structure has 
something to do... but there's no documentation related so I ask you please 
give me any suggestion.

Thanks for your attention.

Regards, Manolo.

Attachment: tuplesort.patch
Description: Binary data

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

Reply via email to