Thread

1. Eliminating unnecessary left joins

   Havasvölgyi Ottó <havasvolgyi.otto@gmail.com> — 2007-04-06T22:01:30Z

   Hi,
   
   When using views built with left joins, and then querying against these
   views, there are a lot of join in the plan that are not necessary, because I
   don't select/use any column of each table in the views every time. Tables
   that are left joined and never referenced anywhere else in the query  should
   be removed from the plan. I think this can be done without any other
   analyzation or catalog lookup, so it is a quite cheap optimization step, and
   doing it won't influence the result, but the query will run faster.
   This way with a complex query against these views usually the half of the
   join can be eliminated, and the plan will be quite more optimal.
   Why left join a table if never used/referenced in the query?
   
   How easy is to teach Postgres to this?
   
   I would like to help somehow to introduce this feature as soon as possible.
   What should I do?
   
   Thanks,
   Otto
   

2. Re: Eliminating unnecessary left joins

   Tom Lane <tgl@sss.pgh.pa.us> — 2007-04-06T23:38:39Z

   "=?ISO-8859-1?Q?Ott=F3_Havasv=F6lgyi?=" <havasvolgyi.otto@gmail.com> writes:
   > When using views built with left joins, and then querying against these
   > views, there are a lot of join in the plan that are not necessary, because I
   > don't select/use any column of each table in the views every time. Tables
   > that are left joined and never referenced anywhere else in the query  should
   > be removed from the plan.
   
   That might cause you to get the wrong number of copies of some rows ---
   what if a row of the left table should join to multiple rows on the right?
   
   			regards, tom lane
   
   

3. Re: Eliminating unnecessary left joins

   Andreas Pflug <pgadmin@pse-consulting.de> — 2007-04-07T02:00:29Z

   Tom Lane wrote:
   > "=?ISO-8859-1?Q?Ott=F3_Havasv=F6lgyi?=" <havasvolgyi.otto@gmail.com> writes:
   >   
   >> When using views built with left joins, and then querying against these
   >> views, there are a lot of join in the plan that are not necessary, because I
   >> don't select/use any column of each table in the views every time. Tables
   >> that are left joined and never referenced anywhere else in the query  should
   >> be removed from the plan.
   >>     
   >
   > That might cause you to get the wrong number of copies of some rows ---
   > what if a row of the left table should join to multiple rows on the right?
   >   
   That would be trouble. But I've seen quite some cases where the right
   can contain only zero or one row, because of PK constraints. In this
   case, elimination would be safe.
   
   
   Regards,
   Andreas
   
   

4. Re: Eliminating unnecessary left joins

   Simon Riggs <simon@2ndquadrant.com> — 2007-04-07T08:50:39Z

   On Fri, 2007-04-06 at 19:38 -0400, Tom Lane wrote:
   > "=?ISO-8859-1?Q?Ott=F3_Havasv=F6lgyi?=" <havasvolgyi.otto@gmail.com> writes:
   > > When using views built with left joins, and then querying against these
   > > views, there are a lot of join in the plan that are not necessary, because I
   > > don't select/use any column of each table in the views every time. Tables
   > > that are left joined and never referenced anywhere else in the query  should
   > > be removed from the plan.
   > 
   > That might cause you to get the wrong number of copies of some rows ---
   > what if a row of the left table should join to multiple rows on the right?
   
   In the case that PKs match between the tables, then exclusion is safe. 
   
   This would enable vertical partitioning, so is a very desirable feature.
   
   If this was possible, it would be a commonly used optimisation.
   
   -- 
     Simon Riggs             
     EnterpriseDB   http://www.enterprisedb.com
   
   
   
   

5. Re: Eliminating unnecessary left joins

   Nicolas Barbier <nicolas.barbier@gmail.com> — 2007-04-07T12:57:48Z

   2007/4/7, Andreas Pflug <pgadmin@pse-consulting.de>:
   
   > Tom Lane wrote:
   >
   >> "=?ISO-8859-1?Q?Ott=F3_Havasv=F6lgyi?=" <havasvolgyi.otto@gmail.com> writes:
   >>
   >>> When using views built with left joins, and then querying against these
   >>> views, there are a lot of join in the plan that are not necessary, because I
   >>> don't select/use any column of each table in the views every time. Tables
   >>> that are left joined and never referenced anywhere else in the query  should
   >>> be removed from the plan.
   >>
   >> That might cause you to get the wrong number of copies of some rows ---
   >> what if a row of the left table should join to multiple rows on the right?
   >
   >That would be trouble. But I've seen quite some cases where the right
   >can contain only zero or one row, because of PK constraints. In this
   > case, elimination would be safe.
   
   I would like to mention that this kind of structure is used by
   Hibernate (ORM for Java/.NET) for mapping class hierarchies. I can
   attest that this optimization is supported by MS-SQL and I think (not
   tested) also by Oracle.
   
   To recapitulate, the optimization would be: Remove left outer joined
   tables from the join list, if they are not used by the query, and the
   join attributes are a key for it (I assume an equality join).
   
   Typical example:
   
   PARENT_CLASS (PK: ID)
   CHILD_CLASS (PK: ID)
   
   In query:
   
   SELECT
       P.ID
   FROM
                       PARENT_CLASS P
       LEFT OUTER JOIN CHILD_CLASS C ON P.ID = C.ID;
   
   the join on CHILD_CLASS can be eliminated, because the join attribute
   ID is a key for it, and none of its attributes are used in the query.
   
   Hibernate:
   <url:http://www.hibernate.org/>
   
   Hibernate Inheritance Mapping:
   <url:http://www.hibernate.org/hib_docs/reference/en/html/inheritance.html>
   
   greetings,
   Nicolas
   
   -- 
   Nicolas Barbier
   http://www.gnu.org/philosophy/no-word-attachments.html
   
   

6. Re: Eliminating unnecessary left joins

   Havasvölgyi Ottó <havasvolgyi.otto@gmail.com> — 2007-04-07T16:45:42Z

   Sorry, I have left out the PK requirement.
   What Nicolas wrote is right, I also use an O/R mapper and inheritance is
   solved with vertical partitioning. The tables are connected to each other
   with the PK. And the mapper defines views for each class with left joins.
   The mapper generates queries based on these views. A high fraction of
   the joins would be eliminated almost in every query.
   
   My simple example:
   
   Class hierarchy and fields:
   Shape (ID, X, Y)
   |
   +-Circle (ID, Radius)
   |
   +-Rectangle (ID, Width, Height)
   
   The mapper creates 3 tables with the columns next to the class name.
   And it creates 3 views. One of them:
   
   RectangleView:  SELECT r."ID" as "ID", s."X" as "X", s."Y" as "Y", r."Width"
   as "Width", r."Height" as "Height" FROM "Rectangle" r LEFT JOIN "Shape" s ON
   ( r.ID=s.ID)
   
   Now if I query Rectangle object IDs, whose Width is greater than 5, it will
   generate this:
   
   SELECT "ID" FROM RectangleView WHERE "Width">5
   
   In this case I don't need to left join the Shape table, because X and Y
   columns are not used.
   
   
   The other typical situation is when I execute more complex,
   not-O/Rmapper-generated SQL commands based on these views for reporting. For
   example the average width of rectangles whose height is greater than 10.
   ----------------------------------------------------
   
   This optimization should be also applied to subqueries.
   
   
   
   Is this optimization relatively easy to introduce?
   
   I would gladly work on this, but unfortunately I don't know the codebase at
   all.
   I would really appreciate if someone competent implemented this feature in
   8.4.
   
   Thank you in advance,
   Otto
   

7. Re: Eliminating unnecessary left joins

   Nicolas Barbier <nicolas.barbier@gmail.com> — 2007-04-08T12:02:26Z

   2007/4/7, Ottó Havasvölgyi <havasvolgyi.otto@gmail.com>:
   
   > My simple example:
   >
   > Class hierarchy and fields:
   > Shape (ID, X, Y)
   > |
   > +-Circle (ID, Radius)
   > |
   > +-Rectangle (ID, Width, Height)
   >
   > The mapper creates 3 tables with the columns next to the class name.
   > And it creates 3 views. One of them:
   >
   > RectangleView:  SELECT r."ID" as "ID", s."X" as "X", s."Y" as "Y", r."Width"
   > as "Width", r."Height" as "Height" FROM "Rectangle" r LEFT JOIN "Shape" s ON
   > ( r.ID=s.ID)
   
   I find this view definition a bit strange: why is there a left outer
   join? I expect there to be a FK from Rectangle.ID to Shape.ID ("all
   rectangles are shapes"), which makes the definition totally equivalent
   with one in which a normal join is used (whether attributes of Shape
   are used or not).
   
   The main use case I see for the original optimization is ORMs that
   join in a whole hierarchy, even when only a part of it is needed. I
   guess that that is rather common. The ORM that I use does exactly
   this, because the main target-DBMSs (MS-SQL and Oracle) do the
   optimization for it.
   
   Example (somewhat less contrived than my previous one):
   
   Imagine an implementation of the typical "books that are borrowed by
   people" n-m relationship, using three tables ("Book", "Borrowed",
   "Person"). Let's find all books that have been borrowed by a certain
   person.
   
   The "non-ORM" version would be something like:
   
   SELECT Book.*
   FROM
            Book
       JOIN Borrowed ON Borrowed.book_id = Book.id
   WHERE Borrowed.person_id = <x>;
   
   Now assume that Borrowed is a class hierarchy mapped into multiple
   tables by a typical ORM. The query would probably become something
   like:
   
   SELECT Book.*
   FROM
                 Book
            JOIN Borrowed_Parent ON Borrowed_Parent.book_id = Book.id
       LEFT JOIN Borrowed_Child1 ON Borrowed_Child1.id = Borrowed_Parent.id
       LEFT JOIN Borrowed_Child2 ON Borrowed_Child2.id = Borrowed_Parent.id
       (...)
   WHERE Borrowed_Parent.person_id = <x>;
   
   It is clear that the children of the hierarchy are needlessly joined
   in (as the only attribute that is actually needed is person_id, which
   is on the parent level). It is not always trivial for the ORM to find
   that out, without writing stuff that looks suspiciously similar to a
   DBMS optimizer.
   
   Maybe it is debatable whether this optimization should be done by the
   application (i.e. the ORM) or by the DBMS. I am personally in favor of
   doing it in the DBMS.
   
   greetings,
   Nicolas
   
   -- 
   Nicolas Barbier
   http://www.gnu.org/philosophy/no-word-attachments.html
   
   

8. Re: Eliminating unnecessary left joins

   Havasvölgyi Ottó <havasvolgyi.otto@gmail.com> — 2007-04-08T16:58:03Z

   My mapper joins the parent classes' tables to the current class' table in
   the view. In the ShapeView only ID, X, and Y is selected from the shape
   table, and none of the child tables are touched, opposite to your sample.
   But even though all Shape objects (circles and rectangles too) are in the
   resultset as Shape objects. I see this storage model quite consistent.
   You are right, that this can be done with inner join too, this is an option
   in the mapper. Oracle and MSSQL performs this left join optimization, so it
   is usually used with left join by other mapper users. I have asked them (the
   developers of the mapper) to perform this optimization at mapper level
   because not all DBMSs supported this optimization, but it seemed they didn't
   like this idea... And then I came here. This optimization would be useful
   for every Postgres users.
   
   To be honest I also find your sample strange, more exactly that
   *sibling* child tables are left joined to the parent. Maybe because the
   storage model is different than in my mapper.
   
   In my case the left joined parent tables should be excluded by the optimizer
   if possible.
   
   Best regards,
   Otto
   
   
   
   2007/4/8, Nicolas Barbier <nicolas.barbier@gmail.com>:
   >
   > 2007/4/7, Ottó Havasvölgyi <havasvolgyi.otto@gmail.com>:
   >
   > > My simple example:
   > >
   > > Class hierarchy and fields:
   > > Shape (ID, X, Y)
   > > |
   > > +-Circle (ID, Radius)
   > > |
   > > +-Rectangle (ID, Width, Height)
   > >
   > > The mapper creates 3 tables with the columns next to the class name.
   > > And it creates 3 views. One of them:
   > >
   > > RectangleView:  SELECT r."ID" as "ID", s."X" as "X", s."Y" as "Y",
   > r."Width"
   > > as "Width", r."Height" as "Height" FROM "Rectangle" r LEFT JOIN "Shape"
   > s ON
   > > ( r.ID=s.ID)
   >
   > I find this view definition a bit strange: why is there a left outer
   > join? I expect there to be a FK from Rectangle.ID to Shape.ID ("all
   > rectangles are shapes"), which makes the definition totally equivalent
   > with one in which a normal join is used (whether attributes of Shape
   > are used or not).
   >
   > The main use case I see for the original optimization is ORMs that
   > join in a whole hierarchy, even when only a part of it is needed. I
   > guess that that is rather common. The ORM that I use does exactly
   > this, because the main target-DBMSs (MS-SQL and Oracle) do the
   > optimization for it.
   >
   > Example (somewhat less contrived than my previous one):
   >
   > Imagine an implementation of the typical "books that are borrowed by
   > people" n-m relationship, using three tables ("Book", "Borrowed",
   > "Person"). Let's find all books that have been borrowed by a certain
   > person.
   >
   > The "non-ORM" version would be something like:
   >
   > SELECT Book.*
   > FROM
   >         Book
   >    JOIN Borrowed ON Borrowed.book_id = Book.id <http://book.id/>
   > WHERE Borrowed.person_id = <x>;
   >
   > Now assume that Borrowed is a class hierarchy mapped into multiple
   > tables by a typical ORM. The query would probably become something
   > like:
   >
   > SELECT Book.*
   > FROM
   >              Book
   >         JOIN Borrowed_Parent ON Borrowed_Parent.book_id = Book.id<http://book.id/>
   >    LEFT JOIN Borrowed_Child1 ON Borrowed_Child1.id = Borrowed_Parent.id
   >    LEFT JOIN Borrowed_Child2 ON Borrowed_Child2.id = Borrowed_Parent.id
   >    (...)
   > WHERE Borrowed_Parent.person_id = <x>;
   >
   > It is clear that the children of the hierarchy are needlessly joined
   > in (as the only attribute that is actually needed is person_id, which
   > is on the parent level). It is not always trivial for the ORM to find
   > that out, without writing stuff that looks suspiciously similar to a
   > DBMS optimizer.
   >
   > Maybe it is debatable whether this optimization should be done by the
   > application (i.e. the ORM) or by the DBMS. I am personally in favor of
   > doing it in the DBMS.
   >
   > greetings,
   > Nicolas
   >
   > --
   > Nicolas Barbier
   > http://www.gnu.org/philosophy/no-word-attachments.html
   >
   

9. Re: Eliminating unnecessary left joins

   Decibel! <decibel@decibel.org> — 2007-04-11T22:07:19Z

   I agree with others that the way that query is constructed is a bit  
   odd, but it does bring another optimization to mind: when doing an  
   inner-join between a parent and child table when RI is defined  
   between them, if the query only refers to the child table you can  
   drop the parent table from the join, because each row in the child  
   table must have one and only one row in the parent.
   
   Use-case: I'll often use views to make it easier to query several  
   related tables, but not all queries against the views need to hit  
   every table. IE: if a table has several status fields that have RI to  
   parent tables that describe what each status is, you sometimes will  
   query for the status description, sometimes not.
   
   I suspect that checking to see if tables have the right unique keys  
   or RI would add a noticeable amount of extra work to query planning,  
   so we might want a GUC to disable it.
   
   On Apr 7, 2007, at 12:45 PM, Ottó Havasvölgyi wrote:
   
   > Sorry, I have left out the PK requirement.
   > What Nicolas wrote is right, I also use an O/R mapper and  
   > inheritance is solved with vertical partitioning. The tables are  
   > connected to each other with the PK. And the mapper defines views  
   > for each class with left joins. The mapper generates queries based  
   > on these views. A high fraction of the joins would be eliminated  
   > almost in every query.
   >
   > My simple example:
   >
   > Class hierarchy and fields:
   > Shape (ID, X, Y)
   > |
   > +-Circle (ID, Radius)
   > |
   > +-Rectangle (ID, Width, Height)
   >
   > The mapper creates 3 tables with the columns next to the class name.
   > And it creates 3 views. One of them:
   >
   > RectangleView:  SELECT r."ID" as "ID", s."X" as "X", s."Y" as "Y",  
   > r."Width" as "Width", r."Height" as "Height" FROM "Rectangle" r  
   > LEFT JOIN "Shape" s ON ( r.ID=s.ID)
   >
   > Now if I query Rectangle object IDs, whose Width is greater than 5,  
   > it will generate this:
   >
   > SELECT "ID" FROM RectangleView WHERE "Width">5
   >
   > In this case I don't need to left join the Shape table, because X  
   > and Y columns are not used.
   >
   >
   > The other typical situation is when I execute more complex, not-O/ 
   > Rmapper-generated SQL commands based on these views for reporting.  
   > For example the average width of rectangles whose height is greater  
   > than 10.
   > ----------------------------------------------------
   >
   > This optimization should be also applied to subqueries.
   >
   >
   >
   > Is this optimization relatively easy to introduce?
   >
   > I would gladly work on this, but unfortunately I don't know the  
   > codebase at all.
   > I would really appreciate if someone competent implemented this  
   > feature in 8.4.
   >
   > Thank you in advance,
   > Otto
   >
   
   --
   Jim Nasby                                            jim@nasby.net
   EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)
   
   
   
   

10. Re: Eliminating unnecessary left joins

    Havasvölgyi Ottó <havasvolgyi.otto@gmail.com> — 2007-04-12T09:18:00Z

    Jim,
    
    Maybe odd, but simpler to optimize this way.
    
    Your idea would be also a very good optimization, there was already a
    discussion about that here:
    http://archives.postgresql.org/pgsql-performance/2006-01/msg00151.php, but
    that time Tom refused it because it was too expensive and rare. Maybe now he
    has a different opinion.
    However, left join optimization is lot simpler and cheaper, and can
    be useful not only for O/R mappers, but for efficient vertical partitioning
    as Simon mentioned.
    
    Best regards,
    Otto
    
    
    2007/4/12, Jim Nasby <decibel@decibel.org>:
    >
    > I agree with others that the way that query is constructed is a bit
    > odd, but it does bring another optimization to mind: when doing an
    > inner-join between a parent and child table when RI is defined
    > between them, if the query only refers to the child table you can
    > drop the parent table from the join, because each row in the child
    > table must have one and only one row in the parent.
    >
    > Use-case: I'll often use views to make it easier to query several
    > related tables, but not all queries against the views need to hit
    > every table. IE: if a table has several status fields that have RI to
    > parent tables that describe what each status is, you sometimes will
    > query for the status description, sometimes not.
    >
    > I suspect that checking to see if tables have the right unique keys
    > or RI would add a noticeable amount of extra work to query planning,
    > so we might want a GUC to disable it.
    >
    > On Apr 7, 2007, at 12:45 PM, Ottó Havasvölgyi wrote:
    >
    > > Sorry, I have left out the PK requirement.
    > > What Nicolas wrote is right, I also use an O/R mapper and
    > > inheritance is solved with vertical partitioning. The tables are
    > > connected to each other with the PK. And the mapper defines views
    > > for each class with left joins. The mapper generates queries based
    > > on these views. A high fraction of the joins would be eliminated
    > > almost in every query.
    > >
    > > My simple example:
    > >
    > > Class hierarchy and fields:
    > > Shape (ID, X, Y)
    > > |
    > > +-Circle (ID, Radius)
    > > |
    > > +-Rectangle (ID, Width, Height)
    > >
    > > The mapper creates 3 tables with the columns next to the class name.
    > > And it creates 3 views. One of them:
    > >
    > > RectangleView:  SELECT r."ID" as "ID", s."X" as "X", s."Y" as "Y",
    > > r."Width" as "Width", r."Height" as "Height" FROM "Rectangle" r
    > > LEFT JOIN "Shape" s ON ( r.ID=s.ID)
    > >
    > > Now if I query Rectangle object IDs, whose Width is greater than 5,
    > > it will generate this:
    > >
    > > SELECT "ID" FROM RectangleView WHERE "Width">5
    > >
    > > In this case I don't need to left join the Shape table, because X
    > > and Y columns are not used.
    > >
    > >
    > > The other typical situation is when I execute more complex, not-O/
    > > Rmapper-generated SQL commands based on these views for reporting.
    > > For example the average width of rectangles whose height is greater
    > > than 10.
    > > ----------------------------------------------------
    > >
    > > This optimization should be also applied to subqueries.
    > >
    > >
    > >
    > > Is this optimization relatively easy to introduce?
    > >
    > > I would gladly work on this, but unfortunately I don't know the
    > > codebase at all.
    > > I would really appreciate if someone competent implemented this
    > > feature in 8.4.
    > >
    > > Thank you in advance,
    > > Otto
    > >
    >
    > --
    > Jim Nasby                                            jim@nasby.net
    > EnterpriseDB      http://enterprisedb.com      512.569.9461 (cell)
    >
    >
    >
    

11. Re: Eliminating unnecessary left joins

    Zeugswetter Andreas DCP SD <zeugswettera@spardat.at> — 2007-04-12T09:49:21Z

    > Maybe odd, but simpler to optimize this way.
    > 
    > Your idea would be also a very good optimization, there was 
    > already a discussion about that here:
    > http://archives.postgresql.org/pgsql-performance/2006-01/msg00
    > 151.php, but that time Tom refused it because it was too 
    > expensive and rare. Maybe now he has a different opinion.
    > However, left join optimization is lot simpler and cheaper, 
    > and can be useful not only for O/R mappers, but for efficient 
    > vertical partitioning as Simon mentioned.
    
    For the views use case there is a simple solution without the expensive optimization:
    If you have a PK FK relationship simply rewrite the view to use a left join instead
    of a join. Since there is always one row on the outer (PK) side it makes no difference to the result set.
    And then the left join optimization can be used.
    
    Andreas
    
    

12. Re: Eliminating unnecessary left joins

    Stephan Szabo <sszabo@megazone.bigpanda.com> — 2007-04-12T15:09:21Z

    On Wed, 11 Apr 2007, Jim Nasby wrote:
    
    > I agree with others that the way that query is constructed is a bit
    > odd, but it does bring another optimization to mind: when doing an
    > inner-join between a parent and child table when RI is defined
    > between them, if the query only refers to the child table you can
    > drop the parent table from the join, because each row in the child
    > table must have one and only one row in the parent.
    
    I don't think that's quite true without qualifications. First, I think it
    needs to be an immediate constraint (and I don't remember how we handle
    set constraints inside functions that might be called from a statement, so
    it might need to be not deferrable). Second, I think you also need to take
    care of NULLs since child rows with NULLs in the key pass the constraint
    but have no rows in the parent and would get culled by the inner join.
    
    Also, there's a possible issue that constraints do not actually guarantee
    that they always hold true, merely that they hold true at particular
    times. I don't know if it's possible to get a statement executed such that
    it would see the table state between the action and constraint check or
    if such is allowed by spec.