Thread: Poor query plan across OR operator
One of our most-used queries performs poorly (taking over 2 seconds) and a
tiny amount of refactoring shows it can be fast (less than 1ms) by
transforming the OR case (which spans two tables) into a UNION.
I have created a simple test case (below) which shows the difference we
are seeing in query plans before and after refactoring.
Is it beyond the ability of the query planner to optimise this query
without refactoring? Or is the appropriate index missing, and if so, what
would it be?
Perhaps the refactored query is, in fact, different and could produce
different data in certain corner-cases; I can't see where this could be
though.
Your suggestions are appreciated and I hope the information is useful.
Many thanks.
Mark
-- The plans below are from PostgreSQL 8.5alpha3. Also tested with
-- similar results on PostgreSQL 8.4.2
-- Data structure where a container contains multiple items
CREATE TABLE container (
id integer PRIMARY KEY,
selected bool NOT NULL DEFAULT false
);
CREATE TABLE item (
container_id integer NOT NULL
REFERENCES container(id) ON DELETE CASCADE,
n integer NOT NULL,
selected bool NOT NULL DEFAULT false,
PRIMARY KEY (container_id, n)
);
-- Partial indexes to find selected containers or selected items
CREATE INDEX container_selected
ON container (selected)
WHERE selected IS true;
CREATE INDEX item_selected
ON item (selected)
WHERE selected IS true;
-- Populate the data; for a small minority of items and containers,
-- 'selected' is true
CREATE LANGUAGE plpgsql;
CREATE OR REPLACE FUNCTION populate()
RETURNS VOID
AS $$
DECLARE
i integer;
j integer;
BEGIN
FOR i IN 0..999 LOOP
INSERT INTO container (id, selected)
VALUES (i, RANDOM() < 0.01);
FOR j IN 0..999 LOOP
INSERT INTO item (container_id, n, selected)
VALUES (i, j, RANDOM() < 0.001);
END LOOP;
END LOOP;
END
$$ LANGUAGE plpgsql;
SELECT populate();
VACUUM ANALYZE;
SELECT COUNT(*) FROM container; -- 1000
SELECT COUNT(*) FROM container WHERE selected IS true; -- 9
SELECT COUNT(*) FROM item; -- 1000000
SELECT COUNT(*) FROM item WHERE selected IS true; -- 1004
-- A query to find all items where the item or container is selected
EXPLAIN ANALYZE
SELECT container_id, n
FROM item
INNER JOIN container ON item.container_id = container.id
WHERE item.selected IS true
OR container.selected IS true;
-- Resulting query plan
--
-- Hash Join (cost=28.50..92591.11 rows=10016 width=8) (actual time=372.659..1269.207 rows=9996 loops=1)
-- Hash Cond: (item.container_id = container.id)
-- Join Filter: ((item.selected IS TRUE) OR (container.selected IS TRUE))
-- -> Seq Scan on item (cost=0.00..78778.68 rows=1002468 width=9) (actual time=370.590..663.764 rows=1000000
loops=1)
-- -> Hash (cost=16.00..16.00 rows=1000 width=5) (actual time=0.805..0.805 rows=1000 loops=1)
-- -> Seq Scan on container (cost=0.00..16.00 rows=1000 width=5) (actual time=0.007..0.296 rows=1000 loops=1)
-- Total runtime: 1271.676 ms
-- (7 rows)
-- The refactored SQL, which queries the same data but is fast
EXPLAIN ANALYZE
SELECT container_id, n
FROM item
INNER JOIN container ON item.container_id = container.id
WHERE item.selected IS true
UNION
SELECT container_id, n
FROM item
INNER JOIN container ON item.container_id = container.id
WHERE container.selected IS true;
-- Resulting query plan:
--
-- HashAggregate (cost=18018.43..18120.33 rows=10190 width=8) (actual time=22.784..26.341 rows=9996 loops=1)
-- -> Append (cost=28.50..17967.48 rows=10190 width=8) (actual time=0.908..16.676 rows=10004 loops=1)
-- -> Hash Join (cost=28.50..90.05 rows=1002 width=8) (actual time=0.907..3.113 rows=1004 loops=1)
-- Hash Cond: (public.item.container_id = public.container.id)
-- -> Index Scan using item_selected on item (cost=0.00..47.77 rows=1002 width=8) (actual
time=0.036..1.425rows=1004 loops=1)
-- Index Cond: (selected = true)
-- -> Hash (cost=16.00..16.00 rows=1000 width=4) (actual time=0.856..0.856 rows=1000 loops=1)
-- -> Seq Scan on container (cost=0.00..16.00 rows=1000 width=4) (actual time=0.006..0.379
rows=1000loops=1)
-- -> Nested Loop (cost=0.00..17775.53 rows=9188 width=8) (actual time=0.024..9.175 rows=9000 loops=1)
-- -> Index Scan using container_selected on container (cost=0.00..12.33 rows=9 width=4) (actual
time=0.005..0.012rows=9 loops=1)
-- Index Cond: (selected = true)
-- -> Index Scan using item_pkey on item (cost=0.00..1960.93 rows=1021 width=8) (actual
time=0.014..0.460rows=1000 loops=9)
-- Index Cond: (public.item.container_id = public.container.id)
-- Total runtime: 28.617 ms
-- (14 rows)
just create index on both columns: CREATE INDEX foo_i ON foo(bar1, bar2); HTH
Mark Hills <Mark.Hills@framestore.com> writes:
> One of our most-used queries performs poorly (taking over 2 seconds) and a
> tiny amount of refactoring shows it can be fast (less than 1ms) by
> transforming the OR case (which spans two tables) into a UNION.
I'd suggest going with the UNION. We are unlikely to make the planner
look for such cases, because usually such a transformation would be a
net loss. It seems like rather a corner case that it's a win even on
your example.
regards, tom lane
On Tue, Jan 26, 2010 at 11:41 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote: > Mark Hills <Mark.Hills@framestore.com> writes: >> One of our most-used queries performs poorly (taking over 2 seconds) and a >> tiny amount of refactoring shows it can be fast (less than 1ms) by >> transforming the OR case (which spans two tables) into a UNION. > > I'd suggest going with the UNION. We are unlikely to make the planner > look for such cases, because usually such a transformation would be a > net loss. It seems like rather a corner case that it's a win even on > your example. This has come up for me, too. But even if we grant that it's worthwhile, it seems like a tricky optimization to apply in practice, because unless your row estimates are very accurate, you might easily apply it when you would have been better off leaving it alone. And it seems like getting accurate estimates would be hard, since the conditions might be highly correlated, or not, and they're on different tables. ...Robert
Robert Haas <robertmhaas@gmail.com> writes:
> On Tue, Jan 26, 2010 at 11:41 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I'd suggest going with the UNION. �We are unlikely to make the planner
>> look for such cases, because usually such a transformation would be a
>> net loss. �It seems like rather a corner case that it's a win even on
>> your example.
> This has come up for me, too. But even if we grant that it's
> worthwhile, it seems like a tricky optimization to apply in practice,
> because unless your row estimates are very accurate, you might easily
> apply it when you would have been better off leaving it alone. And it
> seems like getting accurate estimates would be hard, since the
> conditions might be highly correlated, or not, and they're on
> different tables.
Actually, in the type of case Mark is showing, the estimates might be
*more* accurate since the condition gets decomposed into separate
per-table conditions. I'm still dubious about how often it's a win
though.
There's another problem, which is that transforming to UNION isn't
necessarily a safe transformation: it only works correctly if the
query output columns are guaranteed unique. Otherwise it might fold
duplicates together that would have remained distinct in the original
query. If your query output columns include a primary key then the
planner could be confident this was safe, but that reduces the scope
of the transformation even further ...
regards, tom lane
Tom Lane <tgl@sss.pgh.pa.us> wrote: > Actually, in the type of case Mark is showing, the estimates might > be *more* accurate since the condition gets decomposed into > separate per-table conditions. I'm still dubious about how often > it's a win though. > > There's another problem, which is that transforming to UNION isn't > necessarily a safe transformation: it only works correctly if the > query output columns are guaranteed unique. Otherwise it might > fold duplicates together that would have remained distinct in the > original query. If your query output columns include a primary > key then the planner could be confident this was safe, but that > reduces the scope of the transformation even further ... FWIW, I've seen this optimization in other products. I remember being surprised sometimes that it wasn't used where I thought it would be, and I had to explicitly transform the query to UNION to get the performance benefit. That was probably due to the sort of constraints you mention on when it is truly equivalent. Personally, I'd put this one in the "it would be nice if" category. Does it merit a TODO list entry, perhaps? -Kevin