Re: [HACKERS] proposal: window function - change_number
Hi Pavel (and others), Pavel Stehule wrote: Hi I tried to solve following task: I have a table start, reason, km = 2014-01-01 08:00:00, private, 10 2014-01-01 09:00:00, commerc, 20 2014-01-01 10:00:00, commerc, 20 2014-01-01 11:00:00, private, 8 and I would reduce these rows to 2014-01-01 08:00:00, private, 10 2014-01-01 09:00:00, commerc, 20 + 20 = 40 2014-01-01 11:00:00, private, 8 It is relative hard to it now with SQL only. But we can simplify this task with window function that returns number of change in some column. Then this task can be solved by select min(start), min(reason), sum(km) from (select start, reason, km, change_number(reason) over (order by start)) group by change_number; What about select srk.reason, min(srk.start), sum(srk.km) from start_reason_km srk group by srk.reason, (select max(start) from start_reason_km other WHERE other.start srk.start and other.reason != srk.reason); In general, I think window function are very specific in how the queryplan must look like, leaving not much room for the optimizer. On the other hand, if there happends to be an efficient way to get the results of the table ordered by start, then the window function will very likely much faster then a join. I would be nice if the optimizer is able to add such stream order operations. Do you think, so it has sense? Regards Pavel Regards, Mart PS: This is my first post to the mailing list. I am a software developer interest is performance making webapplications with a different database server during working hours. -- 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] proposal: window function - change_number
Hi Pavel (and others), Op zondag 21 september 2014 15:35:46 schreef u: 2014-09-21 14:30 GMT+02:00 Mart Kelder m...@kelder31.nl: Hi Pavel (and others), Pavel Stehule wrote: Hi I tried to solve following task: I have a table start, reason, km = 2014-01-01 08:00:00, private, 10 2014-01-01 09:00:00, commerc, 20 2014-01-01 10:00:00, commerc, 20 2014-01-01 11:00:00, private, 8 and I would reduce these rows to 2014-01-01 08:00:00, private, 10 2014-01-01 09:00:00, commerc, 20 + 20 = 40 2014-01-01 11:00:00, private, 8 It is relative hard to it now with SQL only. But we can simplify this task with window function that returns number of change in some column. Then this task can be solved by select min(start), min(reason), sum(km) from (select start, reason, km, change_number(reason) over (order by start)) group by change_number; What about select srk.reason, min(srk.start), sum(srk.km) from start_reason_km srk group by srk.reason, (select max(start) from start_reason_km other WHERE other.start srk.start and other.reason != srk.reason); This query is Cartesian product, so for some large data it is significantly slower then window function (required only sorts without joins) I think we have the same queryplan in mind (with only one scan). As far as I know, SQL is a language where you define the result you want to get, and let the server find a way how to find the data. I think windowed function also say how the server needs to get the information. The real challenge is of course of finding heuristics to remove the additional join. In this particular case, I can tell how to remove the inner join from the subquery: * the where-clause of the self-join contains other.start srk.start. From that we can conclude that if the table is (or can be) sorted on start, we have seen the data before the subquery is executed * because we only need an aggregate, we need to store the intermediate max for each reason. And then add the result to the stream. Recently, I had a simular problem with a table containing a timestamp, a state and a object where the state belongs to. A object remains in a state until there is a more recent tuple in the table. I needed basically to query all the previous state for each tuple, but preverably without the additional join. My motivation was a) to implement described task without Cartesian product. Good reason (if you consider the queryplan and not the query). b) introduce some tool for this kind of problems. I seen more times a request .. reduce a time series, and a window function change_number (or maybe consistent_series_number) can be good candidate. I also need to note that there is a lot of difference in complexity between the possible solutions of this problem. Where a new window function can probably be very easy implemented, the optimizer changes descripted above are complex and not easy to implement. I also want to note that I am not really against new window functions, I only want to point out that a more generic solution also might be possible. Regards, Mart -- 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] Removing INNER JOINs
Hi David (and others), David Rowley wrote: Hi, Starting a new thread which continues on from http://www.postgresql.org/message-id/caaphdvoec8ygwoahvsri-84en2k0tnh6gpxp1k59y9juc1w...@mail.gmail.com To give a brief summary for any new readers: The attached patch allows for INNER JOINed relations to be removed from the plan, providing none of the columns are used for anything, and a foreign key exists which proves that a record must exist in the table being removed which matches the join condition: I'm looking for a bit of feedback around the method I'm using to prune the redundant plan nodes out of the plan tree at executor startup. Particularly around not stripping the Sort nodes out from below a merge join, even if the sort order is no longer required due to the merge join node being removed. This potentially could leave the plan suboptimal when compared to a plan that the planner could generate when the removed relation was never asked for in the first place. I did read this patch (and the previous patch about removing SEMI-joins) with great interest. I don't know the code well enough to say much about the patch itself, but I hope to have some usefull ideas about the the global process. I think performance can be greatly improved if the planner is able to use information based on the current data. I think these patches are just two examples of where assumptions during planning are usefull. I think there are more possibilities for this kind of assumpions (for example unique constraints, empty tables). There are some more details around the reasons behind doing this weird executor startup plan pruning around here: http://www.postgresql.org/message-id/20141006145957.ga20...@awork2.anarazel.de The problem here is that assumpions done during planning might not hold during execution. That is why you placed the final decision about removing a join in the executor. If a plan is made, you know under which assumptions are made in the final plan. In this case, the assumption is that a foreign key is still valid. In general, there are a lot more assumptions, such as the still existing of an index or the still existing of columns. There also are soft assumptions, assuming that the used statistics are still reasonable. My suggestion is to check the assumptions at the start of executor. If they still hold, you can just execute the plan as it is. If one or more assumptions doesn't hold, there are a couple of things you might do: * Make a new plan. The plan is certain to match all conditions because at that time, a snapshot is already taken. * Check the assumption. This can be a costly operation with no guarantee of success. * Change the existing plan to not rely on the failed assumption. * Use an already stored alternate plan (generate during the initial plan). You currently change the plan in executer code. I suggest to go back to the planner if the assumpion doesn't hold. The planner can then decide to change the plan. The planner can also conclude to fully replan if there are reasons for it. If the planner knows that it needs to replan if the assumption will not hold during execution, the cost of replanning multiplied by the chance of the assumption not holding during exeuction should be part of the decision to deliver a plan with an assumpion in the first place. There are also other cases such as MergeJoins performing btree index scans in order to obtain ordered results for a MergeJoin that would be better executed as a SeqScan when the MergeJoin can be removed. Perhaps some costs could be adjusted at planning time when there's a possibility that joins could be removed at execution time, although I'm not quite sure about this as it risks generating a poor plan in the case when the joins cannot be removed. Maybe this is a case where you are better off replanning if the assumption doesn't hold instead of changing the generated exeuction plan. In that case you can remove the join before the path is made. Comments are most welcome Regards David Rowley Regards, Mart -- 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] Asynchronous execution again (which is not parallel)
Hi Robert and others, First, I currently don't know the postgresql code well enough yet. I still hope my toughts are usefull. Robert Haas wrote: > It is unclear to me how useful this is beyond ForeignScan, Gather, and > Append. MergeAppend's ordering constraint makes it less useful; we > can asynchronously kick off the request for the next tuple before > returning the previous one, but we're going to need to have that tuple > before we can return the next one. But it could be done. It could > potentially even be applied to seq scans or index scans using some set > of asynchronous I/O interfaces, but I don't see how it could be > applied to joins or aggregates, which typically can't really proceed > until they get the next tuple. They could be plugged into this > interface easily enough but it would only help to the extent that it > enabled asynchrony elsewhere in the plan tree to be pulled up towards > the root. As far as I understand, this comes down to a number of subplans. The subplan can be asked to return a tuple directly or at some later point in time (asynchrone). Conceptionally, the subplan goes in a "tuples wanted" state and it starts it works that need to be done to receive that tuple. Later, it either returns the tuple or the message that there are no tuples. I see opportunities to use this feature to make some queryplans less memory intensive without increasing the total amount of work to be done. I think the same subplan can be placed at several places in the execution plan. If the subplan ends with a tuple store, then if a row is requested, it can either return it from store, or generate it in the subplan. If both outputs of the subplan request tuples at around the same rate, the tuple store size is limited where we currently need to save all the tuples or generate the tuples multiple times. I think this can be potentionally beneficial for CTE's. I also think the planner can predict what the chances are that a subplan can be reused. If both subplans are on a different side of a hash join, it can know that one output will be exhausted before the second output will request the first row. That would mean that the everything needs to be stored. Also, not every callback needs to be invoked at the same rate: tuple storage might be avoided by choosing the callback to invoke wisely. I am a little bit worried about the performance as a result of context switching. I think it is a good idea to only register the callback if it actually hits a point where the tuple can't be generated directly. > Thoughts? Regards, Mart -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
