5

Script to create the tables

DROP TABLE IF EXISTS history;
CREATE TABLE history (
    id integer NOT NULL,
    ticket_id integer NOT NULL);
ALTER TABLE ONLY history ADD CONSTRAINT history_pkey PRIMARY KEY (id);
CREATE INDEX history_ticket_id ON history USING btree (ticket_id);
DROP TABLE IF EXISTS ticket;
CREATE TABLE ticket (
    id integer NOT NULL
);
ALTER TABLE ONLY ticket ADD CONSTRAINT ticket_pkey PRIMARY KEY (id);

Dummy data

INSERT INTO history values (generate_series(1, 30000), generate_series(1, 30000));
ANALYZE history;

INSERT INTO ticket values (generate_series(1, 40000));
ANALYZE ticket;

Query with sub-select

explain analyze select distinct ticket_id from history
       where ticket_id not in (select id from ticket);

explain analyze slow sub-select

     HashAggregate  (cost=15510545.50..15510695.50 rows=15000 width=4) (actual time=170892.668..170892.668 rows=0 loops=1)
   ->  Seq Scan on history  (cost=0.00..15510508.00 rows=15000 width=4) (actual time=170892.644..170892.644 rows=0 loops=1)
         Filter: (NOT (SubPlan 1))
         Rows Removed by Filter: 30000
         SubPlan 1
           ->  Materialize  (cost=0.00..934.00 rows=40000 width=4) (actual time=0.006..2.685 rows=15000 loops=30000)
                 ->  Seq Scan on ticket  (cost=0.00..577.00 rows=40000 width=4) (actual time=0.038..21.347 rows=30000 loops=1)
 Total runtime: 170892.965 ms

Query with EXCEPT

explain analyze select distinct ticket_id from history
       except select id from ticket;

explain analyze with EXCEPT

HashSetOp Except  (cost=0.29..2449.29 rows=30000 width=4) (actual time=41.641..41.641 rows=0 loops=1)
   ->  Append  (cost=0.29..2274.29 rows=70000 width=4) (actual time=0.024..27.835 rows=70000 loops=1)
         ->  Subquery Scan on "*SELECT* 1"  (cost=0.29..1297.29 rows=30000 width=4) (actual time=0.024..14.527 rows=30000 loops=1)
               ->  Unique  (cost=0.29..997.29 rows=30000 width=4) (actual time=0.022..10.856 rows=30000 loops=1)
                     ->  Index Only Scan using history_ticket_id on history  (cost=0.29..922.29 rows=30000 width=4) (actual time=0.021..6.031 rows=30000 loops=1)
                           Heap Fetches: 30000
         ->  Subquery Scan on "*SELECT* 2"  (cost=0.00..977.00 rows=40000 width=4) (actual time=0.018..8.364 rows=40000 loops=1)
               ->  Seq Scan on ticket  (cost=0.00..577.00 rows=40000 width=4) (actual time=0.018..3.808 rows=40000 loops=1)
 Total runtime: 41.702 ms

DBMS version

  • PostgreSQL 9.3.10

Questions

  • Why does one take much longer than the other?
  • The first plan shows Index Scan using history_pkey on history (...rows=1389582) the second plan shows Index Scan using history_pkey on history (... rows=2738415). So the second plan expects nearly twice as much rows as the first one. Given that this is the primary key index, it's strange that the same where condition would result is such a drastic difference in the estimates. Do you have an index on history.id? – a_horse_with_no_name Mar 12 '16 at 9:40
  • Thanks for the test-setup. On my 9.5.1 installation the not in is about twice as fast as the except solution: not in execution plan and except plan – a_horse_with_no_name Mar 12 '16 at 18:02
1

in is better for list of constant values. Try using not exists instead.

Query:

explain analyze select distinct ticket_id from history h
       where not EXISTS (select id from ticket t where t.id = h.ticket_id);

And execution plan:

Unique  (cost=0.58..2294.04 rows=1 width=4) (actual time=23.140..23.140 rows=0 loops=1)
  ->  Merge Anti Join  (cost=0.58..2294.04 rows=1 width=4) (actual time=23.139..23.139 rows=0 loops=1)
        Merge Cond: (h.ticket_id = t.id)
        ->  Index Only Scan using history_ticket_id on history h  (cost=0.29..922.29 rows=30000 width=4) (actual time=0.037..6.848 rows=30000 loops=1)
              Heap Fetches: 30000
        ->  Index Only Scan using ticket_pkey on ticket t  (cost=0.29..1228.29 rows=40000 width=4) (actual time=0.026..6.970 rows=30000 loops=1)
              Heap Fetches: 30000
Total runtime: 23.189 ms

Reason for that I think is that for NOT IN Postgres will need to build distinct list of values from table ticket and then only filter history. NOT EXISTS does not need to create a list. It can just check if value exists in tickets PK index.

Usually when you don't get "Anti Join" in such type of queries - something is written bad.

  • 4
    We usually appreciate more detailed answers and justified claims. Is IN always slow when combined with subqueries? Why? What plans are produced? Cared to share some analysis / benchmarks? Why do you suggest NOT EXISTS? There are at least two other basic ways to write such queries besides using IN and NOT EXISTS: Using LEFT JOIN / IS NULL and EXCEPT (what the OP did). And you haven't answered the OP's question. Why the EXCEPT solution is so much faster in this case? – ypercubeᵀᴹ Mar 15 '16 at 8:17
  • Thank you for providing a third way to get the result. Yes, your "NOT EXISTS" solution is fast even on the old Postgres 9.3 where the sub-select version takes ages. But it takes twice as long as the EXCEPT version. One question still remains: Why is the sub-query that slow in the old postgres version. But this question is just for curiosity. My initial goal is reached. My conclusion: Upgrade to newer DB version. – guettli Mar 15 '16 at 10:27
  • Planner is getting smarter with newer versions. I would say this is the main reason :) – Andriy Senyshyn Mar 15 '16 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.