Message-Id: <46040DAC.EE98.0025.0@wicourts.gov>
Date: Fri, 23 Mar 2007 17:26:04 -0500
From: "Kevin Grittner" <Kevin.Grittner@wicourts.gov>
To: "Tom Lane" <tgl@sss.pgh.pa.us>
Cc: <pgsql-hackers@postgresql.org>,<pgsql-performance@postgresql.org>,
	"Andrea Olson" <Aolson.CCAP.Courts@wicourts.gov>,
	"Bill Severson" <BSEVERS.CCAP.Courts@wicourts.gov>,
	"John Hutchins" <jhutchi.CCAP.Courts@wicourts.gov>,
	"Randy Peterson" <RPETERS.CCAP.Courts@wicourts.gov>,
	"Shannon Spranger" <ssprang.CCAP.Courts@wicourts.gov>
Subject: Re: EXISTS optimization
References: 
 <4603C1A3.EE98.0025.0@wicourts.gov><4603C1A3.EE98.0025.0@wicourts.gov>
	<25339.1174686582@sss.pgh.pa.us>
In-Reply-To: <25339.1174686582@sss.pgh.pa.us>
Mime-Version: 1.0
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline


>>> On Fri, Mar 23, 2007 at  4:49 PM, in message <25339.1174686582@sss.pgh.=
pa.us>,
Tom Lane <tgl@sss.pgh.pa.us> wrote:=20
> "Kevin Grittner" <Kevin.Grittner@wicourts.gov> writes:
>> explain analyze
>> SELECT "A"."adjustmentNo", "A"."tranNo", "A"."countyNo", "H"."date",=20
> "H"."userId", "H"."time"
>>   FROM "Adjustment" "A"
>>   JOIN "TranHeader" "H" ON ("H"."tranId" =3D "A"."adjustmentNo" AND=20
> "H"."countyNo" =3D "A"."countyNo" AND "H"."tranNo" =3D "A"."tranNo")
>>   WHERE "H"."tranType" =3D 'A'
>>     AND "A"."date" > DATE '2006- 01- 01'
>>     AND "H"."countyNo" =3D 66
>>     AND "A"."countyNo" =3D 66
>>     AND EXISTS
>>         (
>>           SELECT 1 FROM "TranDetail" "D"
>>             WHERE "D"."tranNo" =3D "H"."tranNo"
>>               AND "D"."countyNo" =3D "H"."countyNo"
>>               AND "D"."caseNo" LIKE '2006TR%'
>>         )
>> ;
>=20
>> The commercial product scans the index on caseNo in TranDetail to build =
a=20
> work table of unique values, then uses indexed access to the TranHeader =
and=20
> then to Adjustment.
>=20
> If you want that, try rewriting the EXISTS to an IN:
>=20
>    AND ("H"."tranNo", "H"."countyNo") IN
>         (
>           SELECT "D"."tranNo", "D"."countyNo" FROM "TranDetail" "D"
>             WHERE "D"."caseNo" LIKE '2006TR%'
>         )

Nice.  I get this:
=20
explain analyze
SELECT "A"."adjustmentNo", "A"."tranNo", "A"."countyNo", "H"."date", =
"H"."userId", "H"."time"
  FROM "Adjustment" "A"
  JOIN "TranHeader" "H" ON ("H"."tranId" =3D "A"."adjustmentNo" AND =
"H"."countyNo" =3D "A"."countyNo" AND "H"."tranNo" =3D "A"."tranNo")
  WHERE "H"."tranType" =3D 'A'
    AND "A"."date" > DATE '2006- 01- 01'
    AND "H"."countyNo" =3D 66
    AND "A"."countyNo" =3D 66
    AND ("H"."tranNo", "H"."countyNo") IN
        (
          SELECT "D"."tranNo", "D"."countyNo" FROM "TranDetail" "D"
            WHERE "D"."caseNo" LIKE '2006TR%'
        )
;
=20
 Nested Loop  (cost=3D27.76..36.38 rows=3D1 width=3D46) (actual time=3D92.9=
99..200.398 rows=3D2209 loops=3D1)
   Join Filter: (("H"."tranNo")::integer =3D ("A"."tranNo")::integer)
   ->  Nested Loop  (cost=3D27.76..32.08 rows=3D1 width=3D50) (actual =
time=3D92.970..176.472 rows=3D2209 loops=3D1)
         ->  HashAggregate  (cost=3D27.76..27.77 rows=3D1 width=3D6) =
(actual time=3D92.765..100.810 rows=3D9788 loops=3D1)
               ->  Index Scan using "TranDetail_TranDetCaseNo" on =
"TranDetail" "D"  (cost=3D0.00..27.66 rows=3D20 width=3D6) (actual =
time=3D0.059..60.967 rows=3D46301 loops=3D1)
                     Index Cond: ((("caseNo")::bpchar >=3D '2006TR'::bpchar=
) AND (("caseNo")::bpchar < '2006TS'::bpchar) AND (("countyNo")::smallint =
=3D 66))
                     Filter: (("caseNo")::bpchar ~~ '2006TR%'::text)
         ->  Index Scan using "TranHeader_pkey" on "TranHeader" "H"  =
(cost=3D0.00..4.30 rows=3D1 width=3D46) (actual time=3D0.006..0.006 =
rows=3D0 loops=3D9788)
               Index Cond: ((("H"."tranNo")::integer =3D ("D"."tranNo")::in=
teger) AND (("H"."countyNo")::smallint =3D 66))
               Filter: (("tranType")::bpchar =3D 'A'::bpchar)
   ->  Index Scan using "Adjustment_pkey" on "Adjustment" "A"  (cost=3D0.00=
..4.28 rows=3D1 width=3D22) (actual time=3D0.008..0.009 rows=3D1 loops=3D22=
09)
         Index Cond: ((("H"."tranId")::bpchar =3D ("A"."adjustmentNo")::bpc=
har) AND (("A"."countyNo")::smallint =3D 66))
         Filter: ((date)::date > '2006-01-01'::date)
 Total runtime: 201.306 ms
=20
That's the good news.  The bad news is that I operate under a management =
portability dictate which doesn't currently allow that syntax, since not =
all of the products they want to cover support it.  I tried something =
which seems equivalent, but it is running for a very long time.  I'll show =
it with just the explain while I wait to see how long the explain analyze =
takes.
=20
explain
SELECT "A"."adjustmentNo", "A"."tranNo", "A"."countyNo", "H"."date", =
"H"."userId", "H"."time"
  FROM "Adjustment" "A"
  JOIN "TranHeader" "H" ON ("H"."tranId" =3D "A"."adjustmentNo" AND =
"H"."countyNo" =3D "A"."countyNo" AND "H"."tranNo" =3D "A"."tranNo")
  WHERE "H"."tranType" =3D 'A'
    AND "A"."date" > DATE '2006- 01- 01'
    AND "H"."countyNo" =3D 66
    AND "A"."countyNo" =3D 66
    AND "H"."tranNo" IN
        (
          SELECT "D"."tranNo" FROM "TranDetail" "D"
            WHERE "D"."caseNo" LIKE '2006TR%'
              AND "D"."countyNo" =3D "H"."countyNo"
        )
;

 Nested Loop  (cost=3D0.00..181673.08 rows=3D1 width=3D46)
   Join Filter: (("H"."tranId")::bpchar =3D ("A"."adjustmentNo")::bpchar)
   ->  Seq Scan on "Adjustment" "A"  (cost=3D0.00..2384.27 rows=3D11733 =
width=3D22)
         Filter: (((date)::date > '2006-01-01'::date) AND (("countyNo")::sm=
allint =3D 66))
   ->  Index Scan using "TranHeader_pkey" on "TranHeader" "H"  (cost=3D0.00=
..15.27 rows=3D1 width=3D46)
         Index Cond: ((("H"."tranNo")::integer =3D ("A"."tranNo")::integer)=
 AND (("H"."countyNo")::smallint =3D 66))
         Filter: ((("tranType")::bpchar =3D 'A'::bpchar) AND (subplan))
         SubPlan
           ->  Index Scan using "TranDetail_TranDetCaseNo" on "TranDetail" =
"D"  (cost=3D0.00..27.66 rows=3D20 width=3D4)
                 Index Cond: ((("caseNo")::bpchar >=3D '2006TR'::bpchar) =
AND (("caseNo")::bpchar < '2006TS'::bpchar) AND (("countyNo")::smallint =
=3D ($0)::smallint))
                 Filter: (("caseNo")::bpchar ~~ '2006TR%'::text)

> We don't currently try to flatten EXISTS into a unique/join plan as we
> do for IN.  I seem to recall not doing so when I rewrote IN planning
> because I didn't think it would be exactly semantically equivalent,
> but that was awhile ago.  Right at the moment it seems like it ought
> to be equivalent as long as the comparison operators are strict.
=20
There are a great many situations where they are exactly semantically =
equivalent.  In fact, the commercial database product usually generates an =
identical plan.  I could try to work out (or better yet find) a formal =
description of when that equivalence holds, if someone would be up for =
implementing it.  Barring that, I could see if management would approve =
some time for me to look at submitting a patch, but I haven't looked at =
the code involved, so I have no idea of the scale of effort involved yet.
=20
-Kevin
=20