Thread: optimizing queries using IN and EXISTS

optimizing queries using IN and EXISTS

From
Nick Hofstede
Date:
Hi,

I'm surprised at the difference in speed/execution plan between two logically equivalent queries, one using IN, the
otherusing EXISTS. (At least I think they are logically equivalent) 

I've created a small setup that illustrates what I mean.

Consider the following tables:

CREATE TABLE foo
(
  id integer NOT NULL,
  CONSTRAINT foo_pkey PRIMARY KEY (id )
)

CREATE TABLE bar
(
  foo_ref integer,
  value character varying,
  id integer NOT NULL,
  CONSTRAINT bar_pkey PRIMARY KEY (id ),
  CONSTRAINT bar_foo_ref_fkey FOREIGN KEY (foo_ref)
      REFERENCES foo (id) MATCH SIMPLE
      ON UPDATE NO ACTION ON DELETE NO ACTION
)

The following two queries have very different query plans:

SELECT *
FROM   foo
WHERE  'text6' IN (SELECT value
                   FROM   bar
                          JOIN foo AS foo2
                            ON bar.foo_ref = foo2.id
                   WHERE  foo2.id = foo.id)

and

SELECT *
FROM   foo
WHERE  EXISTS(SELECT 0
              FROM   bar
                     JOIN foo AS foo2
                       ON bar.foo_ref = foo2.id
              WHERE  foo2.id = foo.id
                     AND bar.value = 'text6')

Whereas the second one uses the indexes to look up the matching bar rows, the first one performs a full table scan on
bar.
Given that both queries are logically equivalent, I'm wondering why this optimization isn't made. Is there information
missingfor the optimizer to make the better decision? Are these queries not equivalent perhaps? 

An EXPLAIN ANALYZE on the two queries on filled and analyzed tables highlighting the difference:

EXPLAIN ANALYZE SELECT * FROM foo WHERE 'text6' IN (SELECT value FROM bar JOIN foo AS foo2 ON bar.foo_ref = foo2.id
WHEREfoo2.id = foo.id) 

"Seq Scan on foo  (cost=0.00..3316934.60 rows=5000 width=4) (actual time=6.416..10803.056 rows=1 loops=1)"
"  Filter: (SubPlan 1)"
"  SubPlan 1"
"    ->  Nested Loop  (cost=0.00..663.29 rows=1 width=8) (actual time=0.667..1.079 rows=1 loops=10000)"
"          ->  Seq Scan on bar  (cost=0.00..655.00 rows=1 width=12) (actual time=0.660..1.072 rows=1 loops=10000)"
"                Filter: (foo_ref = foo.id)"
"          ->  Index Scan using foo_pkey on foo foo2  (cost=0.00..8.28 rows=1 width=4) (actual time=0.002..0.003 rows=1
loops=10000)"
"                Index Cond: (id = foo.id)"
"Total runtime: 10803.088 ms"


EXPLAIN ANALYZE SELECT * FROM foo WHERE EXISTS(SELECT 0 FROM bar JOIN foo AS foo2 ON bar.foo_ref = foo2.id WHERE
foo2.id= foo.id AND bar.value = 'text6') 

"Nested Loop  (cost=16.58..24.88 rows=1 width=4) (actual time=0.032..0.032 rows=1 loops=1)"
"  ->  HashAggregate  (cost=16.58..16.59 rows=1 width=8) (actual time=0.029..0.029 rows=1 loops=1)"
"        ->  Nested Loop  (cost=0.00..16.58 rows=1 width=8) (actual time=0.025..0.025 rows=1 loops=1)"
"              ->  Index Scan using bar_value_idx on bar  (cost=0.00..8.29 rows=1 width=4) (actual time=0.019..0.020
rows=1loops=1)" 
"                    Index Cond: ((value)::text = 'text6'::text)"
"              ->  Index Scan using foo_pkey on foo foo2  (cost=0.00..8.28 rows=1 width=4) (actual time=0.002..0.003
rows=1loops=1)" 
"                    Index Cond: (id = bar.foo_ref)"
"  ->  Index Scan using foo_pkey on foo  (cost=0.00..8.28 rows=1 width=4) (actual time=0.001..0.002 rows=1 loops=1)"
"        Index Cond: (id = bar.foo_ref)"
"Total runtime: 0.064 ms"

Hoping someone sheds some light on this and restores my confidence in the optimizer,

Nick Hofstede

PS: I know the EXIST can also be rewritten to a JOIN

SELECT foo.id
FROM   foo
       JOIN bar
         ON bar.foo_ref = foo.id
       JOIN foo AS foo2
         ON bar.foo_ref = foo2.id
WHERE  foo2.id = foo.id
       AND bar.value = 'text6'

and ultimately to (thanks to foo2.id = foo.id)

SELECT foo.id
FROM   foo
       JOIN bar
         ON bar.foo_ref = foo.id
WHERE  bar.value = 'text6'

.. all of wich have an execution plan and performance similar to the EXISTS query.
What I'm concerned about is that the first step from IN to EXISTS isn't made (which also precludes all following
optimizationsteps) 


________________________________

Inventive Designers' Email Disclaimer:
http://www.inventivedesigners.com/email-disclaimer

Re: optimizing queries using IN and EXISTS

From
Peter Geoghegan
Date:
On 18 July 2012 17:10, Nick Hofstede <Nick.Hofstede@inventivegroup.com> wrote:
> Hi,
>
> I'm surprised at the difference in speed/execution plan between two logically equivalent queries, one using IN, the
otherusing EXISTS. (At least I think they are logically equivalent) 

They are not logically equivalent.

http://www.postgresql.org/docs/current/static/functions-subquery.html

See the notes about NULL under IN.

--
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Re: optimizing queries using IN and EXISTS

From
Nick Hofstede
Date:
I realize there is a case where IN returns NULL and EXISTS returns FALSE (in case there is a matching bar with
bar.valueset to NULL) 
In that case however, this would result in the foo row not being included in the resultset, which is the same outcome
inboth cases. 
NOT IN vs NOT EXISTS is another story, I agree.
So even though the subqueries aren't logically equivalent, I still believe the queries in their totality are.

Is this reasoning (knowing the NULL will be treated as FALSE by the WHERE) a bridge too far for the optimizer?
I retested with bar.value declared as NOT NULL but that doesn't seem to help.

Even though this is a bit disappointing, I think it gave me a feel of what the optimizer knows about and takes into
considerationand what not ... 

With kind regards,

Nick
________________________________________
Van: Peter Geoghegan [peter@2ndquadrant.com]
Verzonden: woensdag 18 juli 2012 20:40
Aan: Nick Hofstede
CC: pgsql-performance@postgresql.org
Onderwerp: Re: [PERFORM] optimizing queries using IN and EXISTS

On 18 July 2012 17:10, Nick Hofstede <Nick.Hofstede@inventivegroup.com> wrote:
> Hi,
>
> I'm surprised at the difference in speed/execution plan between two logically equivalent queries, one using IN, the
otherusing EXISTS. (At least I think they are logically equivalent) 

They are not logically equivalent.

http://www.postgresql.org/docs/current/static/functions-subquery.html

See the notes about NULL under IN.

--
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

--
This message has been scanned for viruses and
dangerous content by MailScanner, and is
believed to be clean.


________________________________

Inventive Designers' Email Disclaimer:
http://www.inventivedesigners.com/email-disclaimer

Re: optimizing queries using IN and EXISTS

From
Tom Lane
Date:
Nick Hofstede <Nick.Hofstede@inventivegroup.com> writes:
> I'm surprised at the difference in speed/execution plan between two logically equivalent queries, one using IN, the
otherusing EXISTS. (At least I think they are logically equivalent) 

> SELECT *
> FROM   foo
> WHERE  'text6' IN (SELECT value
>                    FROM   bar
>                           JOIN foo AS foo2
>                             ON bar.foo_ref = foo2.id
>                    WHERE  foo2.id = foo.id)

Hm.  convert_ANY_sublink_to_join() rejects subqueries that contain any
Vars of the parent query level, so the reference to foo.id prevents this
from being converted to a semijoin.  However, it seems like that's
overly restrictive.  I'm not sure that we could remove the test
altogether, but at least outer vars used in WHERE seem safe.

In the meantime, you can recast like this:

SELECT *
FROM   foo
WHERE  ('text6', id) IN (SELECT value, foo2.id
                   FROM   bar
                          JOIN foo AS foo2
                            ON bar.foo_ref = foo2.id)

and still get a semijoin plan from an IN-style query.

            regards, tom lane

Re: optimizing queries using IN and EXISTS

From
Nick Hofstede
Date:
Interesting.
Thanks for the work-around.

Regards,

Nick

-----Original Message-----
From: pgsql-performance-owner@postgresql.org [mailto:pgsql-performance-owner@postgresql.org] On Behalf Of Tom Lane
Sent: donderdag 19 juli 2012 0:36
To: Nick Hofstede
Cc: pgsql-performance@postgresql.org
Subject: Re: [PERFORM] optimizing queries using IN and EXISTS

Nick Hofstede <Nick.Hofstede@inventivegroup.com> writes:
> I'm surprised at the difference in speed/execution plan between two
> logically equivalent queries, one using IN, the other using EXISTS.
> (At least I think they are logically equivalent)

> SELECT *
> FROM   foo
> WHERE  'text6' IN (SELECT value
>                    FROM   bar
>                           JOIN foo AS foo2
>                             ON bar.foo_ref = foo2.id
>                    WHERE  foo2.id = foo.id)

Hm.  convert_ANY_sublink_to_join() rejects subqueries that contain any Vars of the parent query level, so the reference
tofoo.id prevents this from being converted to a semijoin.  However, it seems like that's overly restrictive.  I'm not
surethat we could remove the test altogether, but at least outer vars used in WHERE seem safe. 

In the meantime, you can recast like this:

SELECT *
FROM   foo
WHERE  ('text6', id) IN (SELECT value, foo2.id
                   FROM   bar
                          JOIN foo AS foo2
                            ON bar.foo_ref = foo2.id)

and still get a semijoin plan from an IN-style query.

                        regards, tom lane

--
Sent via pgsql-performance mailing list (pgsql-performance@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-performance

--
This message has been scanned for viruses and dangerous content by MailScanner, and is believed to be clean.


________________________________

Inventive Designers' Email Disclaimer:
http://www.inventivedesigners.com/email-disclaimer