Re: Removing INNER JOINs - Mailing list pgsql-hackers
| From | David Rowley |
|---|---|
| Subject | Re: Removing INNER JOINs |
| Date | |
| Msg-id | CAApHDvqsJ-s8-3=TdR6qda_x+Bv0kjrD+j8okV3xT77PW3LbTA@mail.gmail.com Whole thread Raw |
| In response to | Re: Removing INNER JOINs (Robert Haas <robertmhaas@gmail.com>) |
| Responses |
Re: Removing INNER JOINs
Re: Removing INNER JOINs |
| List | pgsql-hackers |
On 3 December 2014 at 08:13, Robert Haas <robertmhaas@gmail.com> wrote:
On Sun, Nov 30, 2014 at 12:51 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Bottom line, given all the restrictions on whether the optimization can
> happen, I have very little enthusiasm for the whole idea. I do not think
> the benefit will be big enough to justify the amount of mess this will
> introduce.
This optimization applies to a tremendous number of real-world cases,
and we really need to have it. This was a huge problem for me in my
previous life as a web developer. The previous work that we did to
remove LEFT JOINs was an enormous help, but it's not enough; we need a
way to remove INNER JOINs as well.
I thought that David's original approach of doing this in the planner
was a good one. That fell down because of the possibility that
apparently-valid referential integrity constraints might not be valid
at execution time if the triggers were deferred. But frankly, that
seems like an awfully nitpicky thing for this to fall down on. Lots
of web applications are going to issue only SELECT statements that run
as as single-statement transactions, and so that issue, so troubling
in theory, will never occur in practice. That doesn't mean that we
don't need to account for it somehow to make the code safe, but any
argument that it abridges the use case significantly is, in my
opinion, not credible.
Anyway, David was undeterred by the rejection of that initial approach
and rearranged everything, based on suggestions from Andres and later
Simon, into the form it's reached now. Kudos to him for his
persistance. But your point that we might have chosen a whole
different plan if it had known that this join was cheaper is a good
one. However, that takes us right back to square one, which is to do
this at plan time. I happen to think that's probably better anyway,
but I fear we're just going around in circles here. We can either do
it at plan time and find some way of handling the fact that there
might be deferred triggers that haven't fired yet; or we can do it at
execution time and live with the fact that we might have chosen a plan
that is not optimal, though still better than executing a
completely-unnecessary join.
Just so that I don't end up going around in circles again, let me summarise my understanding of the pros and cons of each of the states that this patch has been in.
*** Method 1: Removing Inner Joins at planning time:
Pros:
1. Plan generated should be optimal, i.e should generate the same plan for the query as if the removed relations were never included in the query's text.
2. On successful join removal planning likely will be faster as there's less paths to consider having fewer relations and join combinations.
Cons:
1. Assumptions must be made during planning about the trigger queue being empty or not. During execution, if there are pending fk triggers which need to be executed then we could produce wrong results.
*** Method 2: Marking scans as possibly skippable during planning, and skipping joins at execution (Andres' method)
Pros:
1. The plan can be executed as normal if there are any foreign key triggers pending.
Cons:
1. Planner may not generate optimal plan. e.g sort nodes may be useless for Merge joins
2. Code needed to be added to all join methods to allow skipping, nested loop joins suffered from a small overhead.
3. Small overhead from visiting extra nodes in the plan which would not be present if those nodes had been removed.
4. Problems writing regression tests due to having to use EXPLAIN ANALYZE to try to work out what's going on, and the output containing variable runtime values.
*** Method 3: Marking scans as possibly skippable during planning and removing redundant join nodes at executor startup (Simon's method)
Pros:
1. The plan can be executed as normal if there are any foreign key triggers pending.
2. Does not require extra code in all join types (see cons #2 above)
3. Does not suffer from extra node visiting overhead (see cons #3 above)
Cons:
1. Executor must modify the plan.
2. Planner may have generated a plan which is not optimal for modification by the executor (e.g. Sort nodes for merge join, or index scans for pre-sorted input won't become seqscans which may be more efficient as ordering may not be required after removing a merge join)
With each of the methods listed above, someone has had a problem with, and from the feedback given I've made changes based and ended up with the next revision of the patch.
Tom has now pointed out that he does not like the executor modifying the plan, which I agree with to an extent as it I really do hate the extra useless nodes that I'm unable to remove from the plan.
I'd like to propose Method 4 which I believe solves quite a few of the problems seen in the other method.
Method 4: (Which is I think what Mart had in mind, I've only expanded on it a bit with thoughts about possible implementations methods)
1. Invent planner flags which control the optimiser's ability to perform join removals
2. Add a GUC for the default planner flags. (PLANFLAG_REMOVE_INNER_JOINS)
3. Join removal code checks if the appropriate planner flag is set before performing join removal.
4. If join removals are performed, planner sets flags which were "utilised" by the planner.
5. At Executor startup check plan's "utilised" flags and verifies the plan is compatible for current executor status. e.g if PLANFLAG_REMOVE_INNER_JOINS is set, then we'd better be sure there's no pending foreign key triggers, if there are then the executor invokes the planner with: planflags & ~(all_flags_which_are_not_compatible)
6. planner generates a plan without removing inner joins. (does not set utilised flag)
7. goto step 5
If any users are suffering the overhead of this replanning then they can Zero out the planner_flags GUC and get the standard behaviour back
This would also allow deferrable unique indexes to be used for LEFT JOIN removals... We'd just need to tag PLANFLAG_REMOVE_LEFT_JOIN_WITH_DEFERRED_UNIQUE_IDX (or something shorter), onto the utilised flags and have the executor check that no unique indexes are waiting to be updated.
Things I'm currently not sure about are:
a. can we invoke the planner during executor init?
b. PREPAREd statements... Which plan do we cache? It might not be very nice to force the executor to re-plan if the generated plan was not compatible with the current executor state. Or if we then replaced the cached plan, then subsequent executions of the prepared statement could contain redundant joins. Perhaps we can just stash both plans having planned them lazily as and when required.
Pros:
1. Generates optimal plan
2. Could speed up planning when useless joins are removed.
3. Executor does not have to modify the plan.
4. No wrong results from removing joins when there's pending fk triggers.
5. No extra overhead from visiting useless plan nodes at execution time.
Cons:
1. Executor may have to invoke planner.
2. May have to plan queries twice.
I'm not seeing cons #2 as massively bad, as likely this won't happen too often. This seems far better than generating an alternative plan which may never be used, though, it all hangs on, is it even possible for the executor to call planner() or standard_planner() ?
Regards
David Rowley
pgsql-hackers by date: