Thread: Using ctid column changes plan drastically

Using ctid column changes plan drastically

From
Thomas Kellerer
Date:
Hi,

I was testing a query to delete duplicates to see how well using ctid works if the table doesn't have a unique
identifieravailable. 

The table definition is:

create table dupes
(
    id integer primary key,
    first_name text,
    last_name text
);

My test table has 100.000 rows with ~13000 being actually unique.

The following statement:

DELETE FROM dupes
WHERE id NOT IN (SELECT min(b.id)
                  FROM   dupes b
                  GROUP BY first_name, last_Name
                  HAVING count(*) > 1);

produces a quite nice execution plan:

Delete on public.dupes  (cost=2770.00..4640.00 rows=50000 width=6) (actual time=299.809..299.809 rows=0 loops=1)
   Buffers: shared hit=88100
   ->  Seq Scan on public.dupes  (cost=2770.00..4640.00 rows=50000 width=6) (actual time=150.113..211.340 rows=86860
loops=1)
         Output: dupes.ctid
         Filter: (NOT (hashed SubPlan 1))
         Buffers: shared hit=1240
         SubPlan 1
           ->  HashAggregate  (cost=2620.00..2745.00 rows=10000 width=18) (actual time=115.739..143.004 rows=13140
loops=1)
                 Output: min(b.id), b.first_name, b.last_name
                 Filter: (count(*) > 1)
                 Buffers: shared hit=620
                 ->  Seq Scan on public.dupes b  (cost=0.00..1620.00 rows=100000 width=18) (actual time=0.006..15.563
rows=100000loops=1) 
                       Output: b.id, b.first_name, b.last_name
                       Buffers: shared hit=620
Total runtime: 301.241 ms

Now assuming I do not have a unique value in the table. In that case I would revert to using the ctid to identify
individualrows: 

DELETE FROM dupes
WHERE ctid NOT IN (SELECT min(b.ctid)
                    FROM   dupes b
                    GROUP BY first_name, last_Name
                    HAVING count(*) > 1);

Which has a completely different execution plan:

Delete on public.dupes  (cost=2620.00..10004490.00 rows=50000 width=6) (actual time=269966.623..269966.623 rows=0
loops=1)
   Buffers: shared hit=88720
   ->  Seq Scan on public.dupes  (cost=2620.00..10004490.00 rows=50000 width=6) (actual time=176.107..269582.651
rows=86860loops=1) 
         Output: dupes.ctid
         Filter: (NOT (SubPlan 1))
         Buffers: shared hit=1240
         SubPlan 1
           ->  Materialize  (cost=2620.00..2795.00 rows=10000 width=20) (actual time=0.002..0.799 rows=12277
loops=100000)
                 Output: (min(b.ctid)), b.first_name, b.last_name
                 Buffers: shared hit=620
                 ->  HashAggregate  (cost=2620.00..2745.00 rows=10000 width=20) (actual time=131.162..164.941
rows=13140loops=1) 
                       Output: min(b.ctid), b.first_name, b.last_name
                       Filter: (count(*) > 1)
                       Buffers: shared hit=620
                       ->  Seq Scan on public.dupes b  (cost=0.00..1620.00 rows=100000 width=20) (actual
time=0.005..29.531rows=100000 loops=1) 
                             Output: b.ctid, b.first_name, b.last_name
                             Buffers: shared hit=620
Total runtime: 269968.515 ms

This is Postgres 9.1.4 64bit on Windows 7

Why does the usage of the CTID column change the plan so drastically?

Regards
Thomas

Re: Using ctid column changes plan drastically

From
Tom Lane
Date:
Thomas Kellerer <spam_eater@gmx.net> writes:
> DELETE FROM dupes
> WHERE id NOT IN (SELECT min(b.id)
>                   FROM   dupes b
>                   GROUP BY first_name, last_Name
>                   HAVING count(*) > 1);

Doesn't that kill the non-duplicates too?

> Why does the usage of the CTID column change the plan so drastically?

IIRC, type tid doesn't have any hash support.

            regards, tom lane

Re: Using ctid column changes plan drastically

From
Thomas Kellerer
Date:
Tom Lane, 24.07.2012 16:23:
> Thomas Kellerer <spam_eater@gmx.net> writes:
>> DELETE FROM dupes
>> WHERE id NOT IN (SELECT min(b.id)
>>                    FROM   dupes b
>>                    GROUP BY first_name, last_Name
>>                    HAVING count(*) > 1);
>
> Doesn't that kill the non-duplicates too?

Ah right - another good point on how important the correct test data is ;)

>> Why does the usage of the CTID column change the plan so drastically?
>
> IIRC, type tid doesn't have any hash support.
>

So the "bad" plan is expected?

Regards
Thomas



Re: Using ctid column changes plan drastically

From
Tom Lane
Date:
Thomas Kellerer <spam_eater@gmx.net> writes:
> Tom Lane, 24.07.2012 16:23:
>> IIRC, type tid doesn't have any hash support.

> So the "bad" plan is expected?

Joins on tid columns just aren't supported very well at the moment.
Partly that's from lack of round tuits, and partly it's because it
doesn't seem all that wise to encourage people to use them.  There
are gotchas if any of the rows receive concurrent updates.

FWIW, it might be helpful to cast this as a NOT EXISTS rather than
NOT IN subquery.

            regards, tom lane

Re: Using ctid column changes plan drastically

From
Thomas Kellerer
Date:
Tom Lane wrote on 24.07.2012 17:55:
> Joins on tid columns just aren't supported very well at the moment.
> Partly that's from lack of round tuits, and partly it's because it
> doesn't seem all that wise to encourage people to use them.  There
> are gotchas if any of the rows receive concurrent updates.

Thanks for the clarification. I will keep that in mind.

> FWIW, it might be helpful to cast this as a NOT EXISTS rather than
> NOT IN subquery.

Hmm. How would you change that into an NOT EXISTS clause (so that one of the duplicates remains)
Everything I come up with is in fact slower than the NOT IN solution.

Regards
Thomas



Re: Using ctid column changes plan drastically

From
Tom Lane
Date:
Thomas Kellerer <spam_eater@gmx.net> writes:
> Tom Lane wrote on 24.07.2012 17:55:
>> FWIW, it might be helpful to cast this as a NOT EXISTS rather than
>> NOT IN subquery.

> Hmm. How would you change that into an NOT EXISTS clause (so that one of the duplicates remains)
> Everything I come up with is in fact slower than the NOT IN solution.

Well, it would only help if you're running a PG version that's new
enough to recognize the NOT EXISTS as an anti-join; and even then,
it's possible that joining on a tid column forecloses enough plan
types that you don't get any real benefit.  But I'm just guessing.
Can you show exactly what you tried and what EXPLAIN ANALYZE results
you got?

            regards, tom lane

Re: Using ctid column changes plan drastically

From
Thomas Kellerer
Date:
Tom Lane, 24.07.2012 19:12:
> Well, it would only help if you're running a PG version that's new
> enough to recognize the NOT EXISTS as an anti-join; and even then,
> it's possible that joining on a tid column forecloses enough plan
> types that you don't get any real benefit.  But I'm just guessing.
> Can you show exactly what you tried and what EXPLAIN ANALYZE results
> you got?
>

I am using 9.1.4 (as I said in my initial post).

I finally found a solution that runs fine:

DELETE FROM dupes a
WHERE EXISTS (SELECT 1
               FROM  dupes b
               WHERE b.first_name = a.first_name
                 AND b.last_name = a.last_name
                 AND b.ctid > a.ctid);

The execution plan for this is:

Delete on public.dupes a  (cost=14575.95..16978.87 rows=25000 width=12) (actual time=2419.334..2419.334 rows=0 loops=1)
   Buffers: shared hit=18029
   ->  Merge Semi Join  (cost=14575.95..16978.87 rows=25000 width=12) (actual time=2043.674..2392.707 rows=17097
loops=1)
         Output: a.ctid, b.ctid
         Merge Cond: ((a.first_name = b.first_name) AND (a.last_name = b.last_name))
         Join Filter: (b.ctid > a.ctid)
         Buffers: shared hit=930
         ->  Sort  (cost=7287.98..7475.48 rows=75000 width=20) (actual time=1024.195..1030.051 rows=75000 loops=1)
               Output: a.ctid, a.first_name, a.last_name
               Sort Key: a.first_name, a.last_name
               Sort Method: quicksort  Memory: 8870kB
               Buffers: shared hit=465
               ->  Seq Scan on public.dupes a  (cost=0.00..1215.00 rows=75000 width=20) (actual time=0.025..23.234
rows=75000loops=1) 
                     Output: a.ctid, a.first_name, a.last_name
                     Buffers: shared hit=465
         ->  Sort  (cost=7287.98..7475.48 rows=75000 width=20) (actual time=1019.148..1028.483 rows=105841 loops=1)
               Output: b.ctid, b.first_name, b.last_name
               Sort Key: b.first_name, b.last_name
               Sort Method: quicksort  Memory: 8870kB
               Buffers: shared hit=465
               ->  Seq Scan on public.dupes b  (cost=0.00..1215.00 rows=75000 width=20) (actual time=0.017..19.133
rows=75000loops=1) 
                     Output: b.ctid, b.first_name, b.last_name
                     Buffers: shared hit=465
Total runtime: 2420.953 ms

Which is a lot better than the plan using "WHERE ctid NOT IN (.....)":

Delete on public.dupes  (cost=1777.50..4925055.00 rows=37500 width=6) (actual time=582515.094..582515.094 rows=0
loops=1)
   Buffers: shared hit=18027
   ->  Seq Scan on public.dupes  (cost=1777.50..4925055.00 rows=37500 width=6) (actual time=1038.164..582332.927
rows=17097loops=1) 
         Output: dupes.ctid
         Filter: (NOT (SubPlan 1))
         Buffers: shared hit=930
         SubPlan 1
           ->  Materialize  (cost=1777.50..1890.00 rows=7500 width=20) (actual time=0.001..2.283 rows=35552
loops=75000)
                 Output: (min(b.ctid)), b.first_name, b.last_name
                 Buffers: shared hit=465
                 ->  HashAggregate  (cost=1777.50..1852.50 rows=7500 width=20) (actual time=90.964..120.228 rows=57903
loops=1)
                       Output: min(b.ctid), b.first_name, b.last_name
                       Buffers: shared hit=465
                       ->  Seq Scan on public.dupes b  (cost=0.00..1215.00 rows=75000 width=20) (actual
time=0.008..25.515rows=75000 loops=1) 
                             Output: b.ctid, b.first_name, b.last_name
                             Buffers: shared hit=465
Total runtime: 582517.711 ms

Using "WHERE id NOT IN (...)" is the fastest way:

Delete on public.dupes  (cost=1871.25..3273.75 rows=37500 width=6) (actual time=187.949..187.949 rows=0 loops=1)
   Buffers: shared hit=18490
   ->  Seq Scan on public.dupes  (cost=1871.25..3273.75 rows=37500 width=6) (actual time=125.351..171.108 rows=17097
loops=1)
         Output: dupes.ctid
         Filter: (NOT (hashed SubPlan 1))
         Buffers: shared hit=930
         SubPlan 1
           ->  HashAggregate  (cost=1777.50..1852.50 rows=7500 width=18) (actual time=73.131..93.421 rows=57903
loops=1)
                 Output: min(b.id), b.first_name, b.last_name
                 Buffers: shared hit=465
                 ->  Seq Scan on public.dupes b  (cost=0.00..1215.00 rows=75000 width=18) (actual time=0.004..8.515
rows=75000loops=1) 
                       Output: b.id, b.first_name, b.last_name
                       Buffers: shared hit=465
Total runtime: 189.222 ms

Regards
Thomas


Re: Using ctid column changes plan drastically

From
"Kevin Grittner"
Date:
Thomas Kellerer <spam_eater@gmx.net> wrote:

> I finally found a solution that runs fine:
>
> DELETE FROM dupes a
> WHERE EXISTS (SELECT 1
>                FROM  dupes b
>                WHERE b.first_name = a.first_name
>                  AND b.last_name = a.last_name
>                  AND b.ctid > a.ctid);

How does performance for that compare to?:

CREATE TABLE nodupes AS
  SELECT DISTINCT ON (last_name, first_name) * FROM dupes
  ORDER BY last_name, first_name, ctid;

-Kevin