Thread: BUG #4934: regression in IN with joins in subselect

BUG #4934: regression in IN with joins in subselect

From
"Benjamin Reed"
Date:
The following bug has been logged online:

Bug reference:      4934
Logged by:          Benjamin Reed
Email address:      ranger@opennms.org
PostgreSQL version: 8.4.0
Operating system:   Mac OS X 10.5
Description:        regression in IN with joins in subselect
Details:

I've hit a regression vs. PostgreSQL 8.2 and 8.3 (and probably others)
related to subselects.  This query:

---(snip!)---
SELECT DISTINCT ipInterface.ipAddr FROM ipInterface
    JOIN node ON (ipInterface.nodeID = node.nodeID)
    JOIN ifServices ON (ipInterface.id = ifServices.ipInterfaceId)
    JOIN service ON (ifServices.serviceID = service.serviceID)
WHERE
    (
        node.nodeID IN (
            SELECT category_node.nodeID FROM category_node, categories
            WHERE categories.categoryID = category_node.categoryID
            AND categories.categoryName = 'IMP_mid'
        )
    ) AND
    (
        node.nodeID IN (
            SELECT category_node.nodeID FROM category_node, categories
            WHERE categories.categoryID = category_node.categoryID
            AND categories.categoryName = 'DEV_AC'
        )
    ) AND
    (
        node.nodeID IN (
            SELECT category_node.nodeID FROM category_node, categories
            WHERE categories.categoryID = category_node.categoryID
            AND categories.categoryName = 'OPS_Online'
        )
    ) AND
    (node.nodeId = 1) AND
    (ipInterface.ipAddr = '192.168.1.1') AND
    (service.serviceName = 'ICMP')
LIMIT 1;
---(snip!)---

...passes in PostgreSQL 8.2 and 8.3 (which I have handy to test), but fail
in 8.4.0, as well as current origin/REL8_4_STABLE in git.  I reported it in
IRC, and the original hope was that it was related to bug #4906, but since
testing latest git, it appears that is not the case.

The query plan in 8.3 is this:

---(snip!)---
 Limit  (cost=4.27..76.68 rows=1 width=50)
   ->  Unique  (cost=4.27..76.68 rows=1 width=50)
         ->  Nested Loop IN Join  (cost=4.27..76.68 rows=1 width=50)
               ->  Nested Loop IN Join  (cost=4.27..60.12 rows=1 width=54)
                     ->  Nested Loop IN Join  (cost=4.27..43.56 rows=1
width=54)
                           ->  Nested Loop  (cost=4.27..26.99 rows=1
width=54)
                                 ->  Nested Loop  (cost=4.27..18.72 rows=1
width=54)
                                       ->  Nested Loop  (cost=4.27..17.90
rows=2 width=58)
                                             ->  Index Scan using
ipinterface_nodeid_ipaddr_ismanaged_idx on ipinterface  (cost=0.00..8.27
rows=1 width=58)
                                                   Index Cond: ((1 = nodeid)
AND ((ipaddr)::text = '192.168.1.1'::text))
                                             ->  Bitmap Heap Scan on
ifservices  (cost=4.27..9.60 rows=2 width=8)
                                                   Recheck Cond:
(ipinterface.id = ifservices.ipinterfaceid)
                                                   ->  Bitmap Index Scan on
ifservicves_ipinterfaceid_idx  (cost=0.00..4.27 rows=2 width=0)
                                                         Index Cond:
(ipinterface.id = ifservices.ipinterfaceid)
                                       ->  Index Scan using pk_serviceid on
service  (cost=0.00..0.40 rows=1 width=4)
                                             Index Cond:
(ifservices.serviceid = service.serviceid)
                                             Filter: ((servicename)::text =
'ICMP'::text)
                                 ->  Index Scan using node_id_type_idx on
node  (cost=0.00..8.27 rows=1 width=4)
                                       Index Cond: (nodeid = 1)
                           ->  Nested Loop  (cost=0.00..16.55 rows=1
width=4)
                                 ->  Index Scan using category_idx on
categories  (cost=0.00..8.27 rows=1 width=4)
                                       Index Cond: ((categoryname)::text =
'IMP_mid'::text)
                                 ->  Index Scan using catenode_unique_idx on
category_node  (cost=0.00..8.27 rows=1 width=8)
                                       Index Cond:
((public.categories.categoryid = public.category_node.categoryid) AND (1 =
public.category_node.nodeid))
                     ->  Nested Loop  (cost=0.00..16.55 rows=1 width=4)
                           ->  Index Scan using category_idx on categories
(cost=0.00..8.27 rows=1 width=4)
                                 Index Cond: ((categoryname)::text =
'OPS_Online'::text)
                           ->  Index Scan using catenode_unique_idx on
category_node  (cost=0.00..8.27 rows=1 width=8)
                                 Index Cond: ((public.categories.categoryid
= public.category_node.categoryid) AND (1 = public.category_node.nodeid))
               ->  Nested Loop  (cost=0.00..16.55 rows=1 width=4)
                     ->  Index Scan using category_idx on categories
(cost=0.00..8.27 rows=1 width=4)
                           Index Cond: ((categoryname)::text =
'DEV_AC'::text)
                     ->  Index Scan using catenode_unique_idx on
category_node  (cost=0.00..8.27 rows=1 width=8)
                           Index Cond: ((public.categories.categoryid =
public.category_node.categoryid) AND (1 = public.category_node.nodeid))
---(snip!)---

...and in the stable branch, this:

---(snip!)---
 Limit  (cost=16.56..72.51 rows=1 width=50)
   ->  Unique  (cost=16.56..72.51 rows=1 width=50)
         ->  Nested Loop Semi Join  (cost=16.56..72.51 rows=1 width=50)
               ->  Nested Loop Semi Join  (cost=16.56..55.94 rows=1
width=54)
                     ->  Nested Loop  (cost=16.56..39.38 rows=1 width=54)
                           ->  Nested Loop Semi Join  (cost=16.56..38.57
rows=2 width=58)
                                 ->  Index Scan using node_id_type_idx on
node  (cost=0.00..8.27 rows=1 width=4)
                                       Index Cond: (nodeid = 1)
                                 ->  Nested Loop  (cost=16.56..37.16 rows=2
width=62)
                                       ->  Nested Loop  (cost=16.56..24.85
rows=1 width=62)
                                             ->  Index Scan using
ipinterface_nodeid_ipaddr_ismanaged_idx on ipinterface  (cost=0.00..8.27
rows=1 width=58)
                                                   Index Cond: ((nodeid = 1)
AND ((ipaddr)::text = '192.168.1.1'::text))
                                             ->  HashAggregate
(cost=16.56..16.57 rows=1 width=4)
                                                   ->  Nested Loop
(cost=0.00..16.55 rows=1 width=4)
                                                         ->  Index Scan
using category_idx on categories  (cost=0.00..8.27 rows=1 width=4)
                                                               Index Cond:
((categoryname)::text = 'DEV_AC'::text)
                                                         ->  Index Scan
using catenode_unique_idx on category_node  (cost=0.00..8.27 rows=1
width=8)
                                                               Index Cond:
((public.category_node.categoryid = public.categories.categoryid) AND
(public.category_node.nodeid = 1))
                                       ->  Index Scan using
ifservicves_ipinterfaceid_idx on ifservices  (cost=0.00..12.29 rows=2
width=8)
                                             Index Cond:
(ifservices.ipinterfaceid = ipinterface.id)
                           ->  Index Scan using pk_serviceid on service
(cost=0.00..0.39 rows=1 width=4)
                                 Index Cond: (service.serviceid =
ifservices.serviceid)
                                 Filter: ((service.servicename)::text =
'ICMP'::text)
                     ->  Nested Loop  (cost=0.00..16.55 rows=1 width=4)
                           ->  Index Scan using category_idx on categories
(cost=0.00..8.27 rows=1 width=4)
                                 Index Cond: ((categoryname)::text =
'IMP_mid'::text)
                           ->  Index Scan using catenode_unique_idx on
category_node  (cost=0.00..8.27 rows=1 width=8)
                                 Index Cond:
((public.category_node.categoryid = public.categories.categoryid) AND
(public.category_node.nodeid = 1))
               ->  Nested Loop  (cost=0.00..16.55 rows=1 width=4)
                     ->  Index Scan using category_idx on categories
(cost=0.00..8.27 rows=1 width=4)
                           Index Cond: ((categoryname)::text =
'OPS_Online'::text)
                     ->  Index Scan using catenode_unique_idx on
category_node  (cost=0.00..8.27 rows=1 width=8)
                           Index Cond: ((public.category_node.categoryid =
public.categories.categoryid) AND (public.category_node.nodeid = 1))
---(snip!)---

If I cut the select down to:

---(snip!)---
SELECT DISTINCT ipInterface.ipAddr FROM ipInterface
    JOIN node ON (ipInterface.nodeID = node.nodeID)
    JOIN ifServices ON (ipInterface.id = ifServices.ipInterfaceId)
    JOIN service ON (ifServices.serviceID = service.serviceID)
WHERE
    (node.nodeId = 1) AND
    (ipInterface.ipAddr = '192.168.1.1') AND
    (service.serviceName = 'ICMP')
LIMIT 1;
---(snip!)---

...it passes, but as soon as I add one of the node.nodeID IN() bits, it
fails.  Also, if I change it to hardcode one of the passing node IDs:

---(snip!)---
SELECT DISTINCT ipInterface.ipAddr FROM ipInterface
JOIN node ON (ipInterface.nodeID = node.nodeID)
JOIN ifServices ON (ipInterface.id = ifServices.ipInterfaceId)
JOIN service ON (ifServices.serviceID = service.serviceID)
WHERE
(
node.nodeID IN ( SELECT 1 )
) AND
(node.nodeId = 1) AND
(ipInterface.ipAddr = '192.168.1.1') AND
(service.serviceName = 'ICMP')
LIMIT 1;
---(snip!)---

...it passes, so it appears to be related specifically to the joined
subselect.

If there's anything else you need (database dumps, whatever) to help debug
this, let me know.

Thanks.

Re: BUG #4934: regression in IN with joins in subselect

From
Tom Lane
Date:
"Benjamin Reed" <ranger@opennms.org> writes:
> I've hit a regression vs. PostgreSQL 8.2 and 8.3 (and probably others)
> related to subselects.  This query:

It's not going to be possible to examine this with just the query.
You need to provide a self-contained test case.

            regards, tom lane

Re: BUG #4934: regression in IN with joins in subselect

From
Benjamin Reed
Date:
On 7/22/09 4:39 PM, Tom Lane wrote:
> "Benjamin Reed" <ranger@opennms.org> writes:
>> I've hit a regression vs. PostgreSQL 8.2 and 8.3 (and probably others)
>> related to subselects.  This query:
>
> It's not going to be possible to examine this with just the query.
> You need to provide a self-contained test case.

Attached is a test case, including the query that causes the error at
the end.  On 8.3, it returns 1 row (192.168.1.1), on 8.4 including the
git 8.4 branch, it returns none.

--
Benjamin Reed
The OpenNMS Group
http://www.opennms.org/


Attachment

Re: BUG #4934: regression in IN with joins in subselect

From
Tom Lane
Date:
Benjamin Reed <ranger@opennms.org> writes:
> Attached is a test case, including the query that causes the error at
> the end.  On 8.3, it returns 1 row (192.168.1.1), on 8.4 including the
> git 8.4 branch, it returns none.

Thanks, it seems like the problem is that it's applying *both* its
methods for implementing an IN join: it's unique-ifying the sub-select
output via a HashAggregate, and then using a Semi Join anyway when that
gets joined to the "node" table.  And the Semi Join has indeterminate
output for some of the other output columns.  (The join order it's
choosing seems a bit odd too, but with so few rows in the tables it may
be that all the join orders seem to have the same cost.)  I think this
is probably a small fix, but running out of energy for tonight ...

            regards, tom lane

Re: BUG #4934: regression in IN with joins in subselect

From
Tom Lane
Date:
Benjamin Reed <ranger@opennms.org> writes:
> Attached is a test case, including the query that causes the error at
> the end.  On 8.3, it returns 1 row (192.168.1.1), on 8.4 including the
> git 8.4 branch, it returns none.

Thanks for the test case.  This patch should fix it.

            regards, tom lane

Index: joinrels.c
===================================================================
RCS file: /cvsroot/pgsql/src/backend/optimizer/path/joinrels.c,v
retrieving revision 1.100.2.1
diff -c -r1.100.2.1 joinrels.c
*** joinrels.c    19 Jul 2009 20:32:56 -0000    1.100.2.1
--- joinrels.c    23 Jul 2009 17:39:13 -0000
***************
*** 400,405 ****
--- 400,421 ----
              continue;

          /*
+          * If it's a semijoin and we already joined the RHS to any other
+          * rels within either input, then we must have unique-ified the RHS
+          * at that point (see below).  Therefore the semijoin is no longer
+          * relevant in this join path.
+          */
+         if (sjinfo->jointype == JOIN_SEMI)
+         {
+             if (bms_is_subset(sjinfo->syn_righthand, rel1->relids) &&
+                 !bms_equal(sjinfo->syn_righthand, rel1->relids))
+                 continue;
+             if (bms_is_subset(sjinfo->syn_righthand, rel2->relids) &&
+                 !bms_equal(sjinfo->syn_righthand, rel2->relids))
+                 continue;
+         }
+
+         /*
           * If one input contains min_lefthand and the other contains
           * min_righthand, then we can perform the SJ at this join.
           *
***************
*** 491,499 ****
               * We assume that make_outerjoininfo() set things up correctly
               * so that we'll only match to some SJ if the join is valid.
               * Set flag here to check at bottom of loop.
-              *
-              * For a semijoin, assume it's okay if either side fully contains
-              * the RHS (per the unique-ification case above).
               *----------
               */
              if (sjinfo->jointype != JOIN_SEMI &&
--- 507,512 ----
***************
*** 503,514 ****
                  /* seems OK */
                  Assert(!bms_overlap(joinrelids, sjinfo->min_lefthand));
              }
-             else if (sjinfo->jointype == JOIN_SEMI &&
-                      (bms_is_subset(sjinfo->syn_righthand, rel1->relids) ||
-                       bms_is_subset(sjinfo->syn_righthand, rel2->relids)))
-             {
-                 /* seems OK */
-             }
              else
                  is_valid_inner = false;
          }
--- 516,521 ----