Poor plan when joining against a union containing a join - Mailing list pgsql-performance

Hi all,

I'm encountering very poor query plans when joining against a union,
where one branch of the union is itself a join: specifically, Postgres
does the entire inside join and then filters the result, rather than
pushing the filters down to the joined tables.  I've provided a
standalone test case below, including some variations that don't show
the problem for comparison.  The fourth query is the problematic one -
I would have expected the Append portion of the plan to be essentially
the same as the one in the second query.

I'm running Postgres 9.2.3 on Oracle Enterprise Linux 5 (some machines
5.3, some 5.6) x86_64, installed using the RPMs from
http://yum.pgrpms.org/.  The problem occurs with identical results
(other than raw speed) on both a rather underpowered test server with
default Postgres settings and a much better live server which I've
attempted to tune somewhat sensibly.

Thanks for any advice.

START TRANSACTION;

CREATE TABLE bundle_contents(
    item_id     INTEGER PRIMARY KEY,
    bundle_type INTEGER NOT NULL
);
INSERT INTO bundle_contents(item_id, bundle_type)
    SELECT i * 10 + j, i
    FROM GENERATE_SERIES(1, 100) i,
         GENERATE_SERIES(1,  10) j;
CREATE INDEX ON bundle_contents(bundle_type, item_id);
ANALYSE bundle_contents;

CREATE TABLE bundle(
    bundle_id   INTEGER PRIMARY KEY,
    bundle_type INTEGER NOT NULL
);
INSERT INTO bundle(bundle_id, bundle_type)
    SELECT i * 1000 + j, i
    FROM GENERATE_SERIES(1, 100) i,
         GENERATE_SERIES(1, 1000) j;
CREATE INDEX ON bundle(bundle_type, bundle_id);
ANALYSE bundle;

CREATE VIEW bundled_item AS
    SELECT bundle_id AS item_id_a, item_id AS item_id_b
    FROM bundle NATURAL JOIN bundle_contents;

CREATE TABLE unbundled_item(
    item_id_a INTEGER,
    item_id_b INTEGER,
    PRIMARY KEY (item_id_a, item_id_b)
);
INSERT INTO unbundled_item(item_id_a, item_id_b)
    SELECT i, 1 FROM GENERATE_SERIES(1001, 100000, 10) i;
INSERT INTO unbundled_item(item_id_a, item_id_b)
    SELECT i, 2 FROM GENERATE_SERIES(1001, 100000, 20) i;
INSERT INTO unbundled_item(item_id_a, item_id_b)
    SELECT i, 3 FROM GENERATE_SERIES(1001, 100000, 23) i;
INSERT INTO unbundled_item(item_id_a, item_id_b)
    SELECT i, 4 FROM GENERATE_SERIES(1001, 100000, 41) i;
CREATE INDEX ON unbundled_item(item_id_b);
ANALYSE unbundled_item;

CREATE VIEW item AS
    SELECT item_id_a, item_id_b FROM bundled_item
    UNION ALL
    SELECT item_id_a, item_id_b FROM unbundled_item;

CREATE TABLE item_reference(
    reference_id INTEGER PRIMARY KEY,
    item_id_a    INTEGER NOT NULL,
    item_id_b    INTEGER NOT NULL
);
INSERT INTO item_reference(reference_id, item_id_a, item_id_b)
    VALUES(1, 1472, 16),
          (2, 1299, 3);
CREATE INDEX ON item_reference(item_id_a, item_id_b);
CREATE INDEX ON item_reference(item_id_b);
ANALYSE item_reference;

-- no union, nice and fast
EXPLAIN (ANALYSE, BUFFERS)
    SELECT *
    FROM bundled_item
    WHERE (item_id_a, item_id_b) = (1472, 16);
/* http://explain.depesz.com/s/1ye
                                                                 QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..16.56 rows=1 width=8) (actual
time=0.040..0.041 rows=1 loops=1)
   Join Filter: (bundle.bundle_type = bundle_contents.bundle_type)
   Buffers: shared hit=8
   ->  Index Scan using bundle_pkey on bundle  (cost=0.00..8.28 rows=1
width=8) (actual time=0.017..0.017 rows=1 loops=1)
         Index Cond: (bundle_id = 1472)
         Buffers: shared hit=4
   ->  Index Scan using bundle_contents_pkey on bundle_contents
(cost=0.00..8.27 rows=1 width=8) (actual time=0.012..0.013 rows=1
loops=1)
         Index Cond: (item_id = 16)
         Buffers: shared hit=4
 Total runtime: 0.085 ms
(10 rows)
*/

-- using the union, but querying it directly rather
-- than joining to it, still fast
EXPLAIN (ANALYSE, BUFFERS)
    SELECT *
    FROM item
    WHERE (item_id_a, item_id_b) = (1472, 16);
/* http://explain.depesz.com/s/rwA

QUERY PLAN

---------------------------------------------------------------------------------------------------------------------------------------------------------
 Result  (cost=0.00..24.84 rows=2 width=8) (actual time=0.017..0.068
rows=1 loops=1)
   Buffers: shared hit=6 read=3
   I/O Timings: read=0.032
   ->  Append  (cost=0.00..24.84 rows=2 width=8) (actual
time=0.015..0.066 rows=1 loops=1)
         Buffers: shared hit=6 read=3
         I/O Timings: read=0.032
         ->  Nested Loop  (cost=0.00..16.56 rows=1 width=8) (actual
time=0.015..0.017 rows=1 loops=1)
               Join Filter: (bundle.bundle_type = bundle_contents.bundle_type)
               Buffers: shared hit=6
               ->  Index Scan using bundle_pkey on bundle
(cost=0.00..8.28 rows=1 width=8) (actual time=0.006..0.007 rows=1
loops=1)
                     Index Cond: (bundle_id = 1472)
                     Buffers: shared hit=3
               ->  Index Scan using bundle_contents_pkey on
bundle_contents  (cost=0.00..8.27 rows=1 width=8) (actual
time=0.004..0.005 rows=1 loops=1)
                     Index Cond: (item_id = 16)
                     Buffers: shared hit=3
         ->  Index Scan using unbundled_item_item_id_b_idx on
unbundled_item  (cost=0.00..8.27 rows=1 width=8) (actual
time=0.049..0.049 rows=0 loops=1)
               Index Cond: (item_id_b = 16)
               Filter: (item_id_a = 1472)
               Buffers: shared read=3
               I/O Timings: read=0.032
 Total runtime: 0.116 ms
(21 rows)
*/

-- join but no union, still fast
EXPLAIN (ANALYSE, BUFFERS)
    SELECT *
    FROM bundled_item
    NATURAL JOIN item_reference
    WHERE reference_id = 1;
/* http://explain.depesz.com/s/oOy
                                                                      QUERY PLAN

------------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=1.04..4.50 rows=1 width=12) (actual
time=0.092..0.096 rows=1 loops=1)
   Buffers: shared hit=5 read=3
   I/O Timings: read=0.038
   ->  Merge Join  (cost=1.04..1.33 rows=1 width=16) (actual
time=0.032..0.035 rows=1 loops=1)
         Merge Cond: (bundle_contents.item_id = item_reference.item_id_b)
         Buffers: shared hit=4
         ->  Index Scan using bundle_contents_pkey on bundle_contents
(cost=0.00..43.25 rows=1000 width=8) (actual time=0.010..0.013 rows=7
loops=1)
               Buffers: shared hit=3
         ->  Sort  (cost=1.03..1.04 rows=1 width=12) (actual
time=0.012..0.012 rows=1 loops=1)
               Sort Key: item_reference.item_id_b
               Sort Method: quicksort  Memory: 25kB
               Buffers: shared hit=1
               ->  Seq Scan on item_reference  (cost=0.00..1.02 rows=1
width=12) (actual time=0.005..0.007 rows=1 loops=1)
                     Filter: (reference_id = 1)
                     Rows Removed by Filter: 1
                     Buffers: shared hit=1
   ->  Index Only Scan using bundle_bundle_type_bundle_id_idx on
bundle  (cost=0.00..3.16 rows=1 width=8) (actual time=0.056..0.057
rows=1 loops=1)
         Index Cond: ((bundle_type = bundle_contents.bundle_type) AND
(bundle_id = item_reference.item_id_a))
         Heap Fetches: 1
         Buffers: shared hit=1 read=3
         I/O Timings: read=0.038
 Total runtime: 0.139 ms
(22 rows)
*/

-- join to the union, slow.  the conditions are pushed into the
-- index scan in the non-join branch of the union, but in the join
-- branch they're applied after the entire join is built
EXPLAIN (ANALYSE, BUFFERS)
    SELECT *
    FROM item
    NATURAL JOIN item_reference
    WHERE reference_id = 1;
/* http://explain.depesz.com/s/M73
                                                                     QUERY PLAN

-----------------------------------------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=27.50..27979.82 rows=26 width=12) (actual
time=3.230..554.473 rows=1 loops=1)
   Buffers: shared hit=452
   ->  Seq Scan on item_reference  (cost=0.00..1.02 rows=1 width=12)
(actual time=0.013..0.016 rows=1 loops=1)
         Filter: (reference_id = 1)
         Rows Removed by Filter: 1
         Buffers: shared hit=1
   ->  Append  (cost=27.50..27978.78 rows=2 width=8) (actual
time=3.214..554.454 rows=1 loops=1)
         Buffers: shared hit=451
         ->  Subquery Scan on "*SELECT* 1"  (cost=27.50..27970.50
rows=1 width=8) (actual time=3.212..554.422 rows=1 loops=1)
               Filter: ((item_reference.item_id_a = "*SELECT*
1".item_id_a) AND (item_reference.item_id_b = "*SELECT* 1".item_id_b))
               Rows Removed by Filter: 999999
               Buffers: shared hit=448
               ->  Hash Join  (cost=27.50..12970.50 rows=1000000
width=8) (actual time=0.617..344.127 rows=1000000 loops=1)
                     Hash Cond: (bundle.bundle_type =
bundle_contents.bundle_type)
                     Buffers: shared hit=448
                     ->  Seq Scan on bundle  (cost=0.00..1443.00
rows=100000 width=8) (actual time=0.009..22.066 rows=100000 loops=1)
                           Buffers: shared hit=443
                     ->  Hash  (cost=15.00..15.00 rows=1000 width=8)
(actual time=0.594..0.594 rows=1000 loops=1)
                           Buckets: 1024  Batches: 1  Memory Usage: 40kB
                           Buffers: shared hit=5
                           ->  Seq Scan on bundle_contents
(cost=0.00..15.00 rows=1000 width=8) (actual time=0.008..0.207
rows=1000 loops=1)
                                 Buffers: shared hit=5
         ->  Index Only Scan using unbundled_item_pkey on
unbundled_item  (cost=0.00..8.28 rows=1 width=8) (actual
time=0.021..0.021 rows=0 loops=1)
               Index Cond: ((item_id_a = item_reference.item_id_a) AND
(item_id_b = item_reference.item_id_b))
               Heap Fetches: 0
               Buffers: shared hit=3
 Total runtime: 554.533 ms
(27 rows)
*/

ROLLBACK;