Thread: 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.
Attachment
On Mon, Feb 04, 2008 at 07:10:10PM +0100, mac_man2005@hotmail.it wrote: > 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. Patches for new features need to be on CVS TIP, as the project does not add new features to stable releases. How do you want to be named on this? Cheers, David. -- David Fetter <david@fetter.org> http://fetter.org/ Phone: +1 415 235 3778 AIM: dfetter666 Yahoo!: dfetter Skype: davidfetter XMPP: david.fetter@gmail.com Remember to vote! Consider donating to Postgres: http://www.postgresql.org/about/donate
HI. I send you the diff of my code against the current CVS TIP. Please tell me if it's what you were asking for. Thanks. Regards, Manolo di Domenico ---------------------------------------- > Date: Wed, 6 Feb 2008 17:03:16 -0800 > From: david@fetter.org > To: mac_man2005@hotmail.it > Subject: Re: [PATCHES] 2WRS [WIP] > > > Go here and snoop around a bit. > > http://neilconway.org/talks/hacking _________________________________________________________________ Express yourself instantly with MSN Messenger! Download today it's FREE! http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/
Attachment
On Feb 7, 2008 6:04 AM, Manolo _ <mac_man2005@hotmail.it> wrote:
>
> HI.
>
> I send you the diff of my code against the current CVS TIP.
> Please tell me if it's what you were asking for.
>
not actually, because your patch removes an improvement that was
included in 8.3...
what you will have to do (if someone has a better solution feel free
to comment on this) is to manually merge your 8.2's patch into the
8.3's source and then generate a diff
another sugestion is to comment a little more your code. simply put a
mark where you modify something is not a comment, specially if you can
get that info from a simple cvs diff
--
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
On Fri, Feb 08, 2008 at 12:27:23AM -0500, Jaime Casanova wrote: > On Feb 7, 2008 6:04 AM, Manolo _ <mac_man2005@hotmail.it> wrote: > > > > HI. > > > > I send you the diff of my code against the current CVS TIP. > > Please tell me if it's what you were asking for. > > > > not actually, because your patch removes an improvement that was > included in 8.3... > what you will have to do (if someone has a better solution feel free > to comment on this) is to manually merge your 8.2's patch into the > 8.3's source and then generate a diff s/8.3/HEAD/ -- Decibel!, aka Jim C. Nasby, Database Architect decibel@decibel.org Give your computer some brain candy! www.distributed.net Team #1828
Attachment
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. Thanks. Regards, Manolo.
Attachment
On Thu, Feb 21, 2008 at 6:44 AM, <manolo.espa@gmail.com> 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
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" <systemguards@gmail.com> Sent: Friday, February 22, 2008 5:30 AM To: <manolo.espa@gmail.com> Cc: "Decibel!" <decibel@decibel.org>; "Manolo _" <mac_man2005@hotmail.it>; "David Fetter" <david@fetter.org>; <pgsql-patches@postgresql.org>; <pgsql-hackers@postgresql.org> Subject: Re: [HACKERS] [PATCHES] 2WRS [WIP] > On Thu, Feb 21, 2008 at 6:44 AM, <manolo.espa@gmail.com> 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 >
Attachment
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" <systemguards@gmail.com> Sent: Friday, February 22, 2008 5:30 AM To: <manolo.espa@gmail.com> Cc: "Decibel!" <decibel@decibel.org>; "Manolo _" <mac_man2005@hotmail.it>; "David Fetter" <david@fetter.org>; <pgsql-patches@postgresql.org>; <pgsql-hackers@postgresql.org> Subject: Re: [HACKERS] [PATCHES] 2WRS [WIP] > On Thu, Feb 21, 2008 at 6:44 AM, <manolo.espa@gmail.com> 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 >
Attachment
We need more testing to show this is a good idea. --------------------------------------------------------------------------- Manolo _ wrote: > > HI. > > I send you the diff of my code against the current CVS TIP. > Please tell me if it's what you were asking for. > > Thanks. > > Regards, Manolo di Domenico > > ---------------------------------------- > > Date: Wed, 6 Feb 2008 17:03:16 -0800 > > From: david@fetter.org > > To: mac_man2005@hotmail.it > > Subject: Re: [PATCHES] 2WRS [WIP] > > > > > > Go here and snoop around a bit. > > > > http://neilconway.org/talks/hacking > _________________________________________________________________ > Express yourself instantly with MSN Messenger! Download today it's FREE! > http://messenger.msn.click-url.com/go/onm00200471ave/direct/01/ [ Attachment, skipping... ] > > ---------------------------(end of broadcast)--------------------------- > TIP 5: don't forget to increase your free space map settings -- Bruce Momjian <bruce@momjian.us> http://momjian.us EnterpriseDB http://postgres.enterprisedb.com + If your life is a hard drive, Christ can be your backup. +