Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
On Wed, Feb 5, 2014 at 10:33 AM, Jon Nelson wrote: > What - if anything - do I need to do to get this on the commitfest > list for the next commitfest? The list of instructions is here: http://wiki.postgresql.org/wiki/Submitting_a_Patch#Patch_submission Then the next commit fest (#1 for 9.5), will be in June and is here: https://commitfest.postgresql.org/action/commitfest_view?id=22 Note that you will need an account on postgresql.org to register your patch. Regards, -- Michael -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
What - if anything - do I need to do to get this on the commitfest list for the next commitfest? -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
What are my next steps here? I believe the concept is sound, the code is appears to work and doesn't crash, and the result does show a performance win in most cases (sometimes a big win). It's also incomplete, at least insofar as it doesn't interface with the cost models at all, etc... -- Jon -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
On Wed, Jan 22, 2014 at 3:26 PM, Tom Lane wrote: > Jeremy Harris writes: >> On 22/01/14 03:53, Tom Lane wrote: >>> Jon Nelson writes: - in createplan.c, eliding duplicate tuples is enabled if we are creating a unique plan which involves sorting first > >>> [ raised eyebrow ... ] And what happens if the planner drops the >>> unique step and then the sort doesn't actually go to disk? > >> I don't think Jon was suggesting that the planner drop the unique step. > > Hm, OK, maybe I misread what he said there. Still, if we've told > tuplesort to remove duplicates, why shouldn't we expect it to have > done the job? Passing the data through a useless Unique step is > not especially cheap. That's correct - I do not propose to drop the unique step. Duplicates are only dropped if it's convenient to do so. In one case, it's a zero-cost drop (no extra comparison is made). In most other cases, an extra comparison is made, typically right before writing a tuple to tape. If it compares as identical to the previously-written tuple, it's thrown out instead of being written. The output of the modified code is still sorted, still *might* (and in most cases, probably will) contain duplicates, but will (probably) contain fewer duplicates. -- Jon -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
Jeremy Harris writes: > On 22/01/14 03:53, Tom Lane wrote: >> Jon Nelson writes: >>> - in createplan.c, eliding duplicate tuples is enabled if we are >>> creating a unique plan which involves sorting first >> [ raised eyebrow ... ] And what happens if the planner drops the >> unique step and then the sort doesn't actually go to disk? > I don't think Jon was suggesting that the planner drop the unique step. Hm, OK, maybe I misread what he said there. Still, if we've told tuplesort to remove duplicates, why shouldn't we expect it to have done the job? Passing the data through a useless Unique step is not especially cheap. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
On 22/01/14 03:53, Tom Lane wrote: Jon Nelson writes: A rough summary of the patch follows: - a GUC variable enables or disables this capability - in nodeAgg.c, eliding duplicate tuples is enabled if the number of distinct columns is equal to the number of sort columns (and both are greater than zero). - in createplan.c, eliding duplicate tuples is enabled if we are creating a unique plan which involves sorting first - ditto planner.c - all of the remaining changes are in tuplesort.c, which consist of: + a new macro, DISCARDTUP and a new structure member, discardtup, are both defined and operate similar to COMPARETUP, COPYTUP, etc... + in puttuple_common, when state is TSS_BUILDRUNS, we *may* simply throw out the new tuple if it compares as identical to the tuple at the top of the heap. Since we're already performing this comparison, this is essentially free. + in mergeonerun, we may discard a tuple if it compares as identical to the *last written tuple*. This is a comparison that did not take place before, so it's not free, but it saves a write I/O. + We perform the same logic in dumptuples [ raised eyebrow ... ] And what happens if the planner drops the unique step and then the sort doesn't actually go to disk? I don't think Jon was suggesting that the planner drop the unique step. -- Cheers, Jeremy -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
On 22/01/14 03:16, Jon Nelson wrote: Greetings -hackers: I have worked up a patch to PostgreSQL which elides tuples during an external sort. The primary use case is when sorted input is being used to feed a DISTINCT operation. The idea is to throw out tuples that compare as identical whenever it's convenient, predicated on the assumption that even a single I/O is more expensive than some number of (potentially extra) comparisons. Obviously, this is where a cost model comes in, which has not been implemented. This patch is a work-in-progress. Dedup-in-sort is also done by my WIP internal merge sort, and extended (in much the same ways as Jon's) to the external merge. https://github.com/j47996/pgsql_sorb I've not done a cost model either, but the dedup capability is exposed from tuplesort.c to the executor, and downstream uniq nodes removed. I've not worked out yet how to eliminate upstream hashagg nodes, which would be worthwhile from testing results. -- Cheers, Jeremy -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
On Tue, Jan 21, 2014 at 9:53 PM, Tom Lane wrote: > Jon Nelson writes: >> A rough summary of the patch follows: > >> - a GUC variable enables or disables this capability >> - in nodeAgg.c, eliding duplicate tuples is enabled if the number of >> distinct columns is equal to the number of sort columns (and both are >> greater than zero). >> - in createplan.c, eliding duplicate tuples is enabled if we are >> creating a unique plan which involves sorting first >> - ditto planner.c >> - all of the remaining changes are in tuplesort.c, which consist of: >> + a new macro, DISCARDTUP and a new structure member, discardtup, are >> both defined and operate similar to COMPARETUP, COPYTUP, etc... >> + in puttuple_common, when state is TSS_BUILDRUNS, we *may* simply >> throw out the new tuple if it compares as identical to the tuple at >> the top of the heap. Since we're already performing this comparison, >> this is essentially free. >> + in mergeonerun, we may discard a tuple if it compares as identical >> to the *last written tuple*. This is a comparison that did not take >> place before, so it's not free, but it saves a write I/O. >> + We perform the same logic in dumptuples > > [ raised eyebrow ... ] And what happens if the planner drops the > unique step and then the sort doesn't actually go to disk? I'm not familiar enough with the code to be able to answer your question with any sort of authority, but I believe that if the state TSS_BUILDRUNS is never hit, then basically nothing new happens. -- Jon -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] PoC: Duplicate Tuple Elidation during External Sort for DISTINCT
Jon Nelson writes: > A rough summary of the patch follows: > - a GUC variable enables or disables this capability > - in nodeAgg.c, eliding duplicate tuples is enabled if the number of > distinct columns is equal to the number of sort columns (and both are > greater than zero). > - in createplan.c, eliding duplicate tuples is enabled if we are > creating a unique plan which involves sorting first > - ditto planner.c > - all of the remaining changes are in tuplesort.c, which consist of: > + a new macro, DISCARDTUP and a new structure member, discardtup, are > both defined and operate similar to COMPARETUP, COPYTUP, etc... > + in puttuple_common, when state is TSS_BUILDRUNS, we *may* simply > throw out the new tuple if it compares as identical to the tuple at > the top of the heap. Since we're already performing this comparison, > this is essentially free. > + in mergeonerun, we may discard a tuple if it compares as identical > to the *last written tuple*. This is a comparison that did not take > place before, so it's not free, but it saves a write I/O. > + We perform the same logic in dumptuples [ raised eyebrow ... ] And what happens if the planner drops the unique step and then the sort doesn't actually go to disk? regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
