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 runDOWN 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. http://maxotek.net/images/base/sandClock.png 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. *** THE LOGICAL 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. *** STATE OF THE ART *** 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.
tuplesort.patch
Description: Binary data
---------------------------(end of broadcast)--------------------------- TIP 5: don't forget to increase your free space map settings
