Re: [HACKERS] [PATCHES] 2WRS [WIP]
For the joy of all of you: that's the correct WIP patch. At the moment it only tries to create runs uding two heaps. Hope you can help me with writing those runs on tapes. I'd be very pleased to give you more details. Thenks for your time. Regards, Manolo. -- From: Jaime Casanova [EMAIL PROTECTED] Sent: Friday, February 22, 2008 5:30 AM To: [EMAIL PROTECTED] Cc: Decibel! [EMAIL PROTECTED]; Manolo _ [EMAIL PROTECTED]; David Fetter [EMAIL PROTECTED]; pgsql-patches@postgresql.org; [EMAIL PROTECTED] Subject: Re: [HACKERS] [PATCHES] 2WRS [WIP] On Thu, Feb 21, 2008 at 6:44 AM, [EMAIL PROTECTED] wrote: Hi. That's the last release and refers to 8.3.0 and not to 8.2.5 as before. Hope you can tell me if I created it correctly please. no, it doesn't... ! /* GUC variables */ #ifdef TRACE_SORT bool trace_sort = false; #endif - #ifdef DEBUG_BOUNDED_SORT - bool optimize_bounded_sort = true; - #endif it's seems you're removing something added in 8.3 -- regards, Jaime Casanova Programming today is a race between software engineers striving to build bigger and better idiot-proof programs and the universe trying to produce bigger and better idiots. So far, the universe is winning. Richard Cook ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match tuplesort.patch Description: Binary data ---(end of broadcast)--- TIP 6: explain analyze is your friend
[PATCHES] 2WRS [WIP]
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
