Received: from localhost (maia-5.hub.org [200.46.204.182]) by postgresql.org (Postfix) with ESMTP id A8C289FB1CD for ; Sat, 28 Jul 2007 10:16:38 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.182]) (amavisd-maia, port 10024) with ESMTP id 28829-03 for ; Sat, 28 Jul 2007 10:16:29 -0300 (ADT) X-Greylist: delayed 00:23:53.263315 by SQLgrey-1.7.5 Received: from mailb.org (mailb.org [213.239.200.52]) by postgresql.org (Postfix) with ESMTP id 5ACA09FA4EE for ; Sat, 28 Jul 2007 10:16:34 -0300 (ADT) Received: from localhost (dslb-088-072-217-178.pools.arcor-ip.net [88.72.217.178]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mailb.org (Postfix) with ESMTP id 452A8456167 for ; Sat, 28 Jul 2007 14:52:37 +0200 (CEST) Received: by localhost (sSMTP sendmail emulation); Sat, 28 Jul 2007 14:52:36 +0200 Date: Sat, 28 Jul 2007 14:52:36 +0200 From: Tilmann Singer To: pgsql-performance@postgresql.org Subject: Re: Slow query with backwards index scan Message-ID: <20070728125236.GD19392@tils.net> References: <20070727172703.GG25252@tils.net> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: X-message-flag: Please consider using an e-mail program other than Outlook. It's insecure X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.001 tagged_above=0 required=5 tests=BAYES_50=0.001 X-Spam-Level: X-Archive-Number: 200707/393 X-Sequence-Number: 26077 * Nis Jørgensen [20070727 20:31]: > How does the "obvious" UNION query do - ie: > > SELECT * FROM ( > SELECT * FROM large_table lt > WHERE lt.user_id = 12345 > > UNION > > SELECT * FROM large_table lt > WHERE user_id IN (SELECT contact_id FROM relationships WHERE user_id=12345) > ) q > > ORDER BY created_at DESC LIMIT 10; Great for the user with little data: testdb=# EXPLAIN ANALYZE SELECT * FROM ( SELECT * FROM large_table lt WHERE lt.user_id = 12345 UNION SELECT * FROM large_table lt WHERE user_id IN (SELECT contact_id FROM relationships WHERE user_id=12345) ) q ORDER BY created_at DESC LIMIT 10; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=14673.77..14673.80 rows=10 width=3140) (actual time=133.877..133.946 rows=10 loops=1) -> Sort (cost=14673.77..14682.22 rows=3378 width=3140) (actual time=133.870..133.894 rows=10 loops=1) Sort Key: q.created_at -> Unique (cost=14315.34..14442.01 rows=3378 width=622) (actual time=133.344..133.705 rows=38 loops=1) -> Sort (cost=14315.34..14323.78 rows=3378 width=622) (actual time=133.337..133.432 rows=38 loops=1) Sort Key: id, user_id, plaze_id, device, started_at, updated_at, status, "type", duration, permission, created_at, mac_address, subnet, msc -> Append (cost=0.00..14117.35 rows=3378 width=622) (actual time=39.144..133.143 rows=38 loops=1) -> Index Scan using large_user_id_started_at_index on large_table lt (cost=0.00..7243.59 rows=2158 width=622) (actual time=39.138..109.831 rows=34 loops=1) Index Cond: (user_id = 12345) -> Nested Loop (cost=42.78..6839.98 rows=1220 width=622) (actual time=14.859..23.112 rows=4 loops=1) -> HashAggregate (cost=42.78..42.79 rows=1 width=4) (actual time=8.092..8.095 rows=1 loops=1) -> Bitmap Heap Scan on relationships (cost=4.34..42.75 rows=11 width=4) (actual time=8.067..8.070 rows=1 loops=1) Recheck Cond: (user_id = 12345) -> Bitmap Index Scan on relationships_user_id_index (cost=0.00..4.34 rows=11 width=0) (actual time=8.057..8.057 rows=1 loops=1) Index Cond: (user_id = 12345) -> Index Scan using large_user_id_started_at_index on large_table lt (cost=0.00..6768.48 rows=2297 width=622) (actual time=6.751..14.970 rows=4 loops=1) Index Cond: (lt.user_id = relationships.contact_id) Total runtime: 134.220 ms Not so great for the user with many early matches: testdb=# EXPLAIN ANALYZE SELECT * FROM ( SELECT * FROM large_table lt WHERE lt.user_id = 55555 UNION SELECT * FROM large_table lt WHERE user_id IN (SELECT contact_id FROM relationships WHERE user_id=55555) ) q ORDER BY created_at DESC LIMIT 10; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=14673.77..14673.80 rows=10 width=3140) (actual time=3326.304..3326.367 rows=10 loops=1) -> Sort (cost=14673.77..14682.22 rows=3378 width=3140) (actual time=3326.297..3326.318 rows=10 loops=1) Sort Key: q.created_at -> Unique (cost=14315.34..14442.01 rows=3378 width=622) (actual time=2413.070..3019.385 rows=69757 loops=1) -> Sort (cost=14315.34..14323.78 rows=3378 width=622) (actual time=2413.062..2590.354 rows=69757 loops=1) Sort Key: id, user_id, plaze_id, device, started_at, updated_at, status, "type", duration, permission, created_at, mac_address, subnet, msc -> Append (cost=0.00..14117.35 rows=3378 width=622) (actual time=0.067..1911.626 rows=69757 loops=1) -> Index Scan using large_user_id_started_at_index on large_table lt (cost=0.00..7243.59 rows=2158 width=622) (actual time=0.062..3.440 rows=739 loops=1) Index Cond: (user_id = 55555) -> Nested Loop (cost=42.78..6839.98 rows=1220 width=622) (actual time=0.451..1557.901 rows=69018 loops=1) -> HashAggregate (cost=42.78..42.79 rows=1 width=4) (actual time=0.404..0.580 rows=40 loops=1) -> Bitmap Heap Scan on relationships (cost=4.34..42.75 rows=11 width=4) (actual time=0.075..0.241 rows=40 loops=1) Recheck Cond: (user_id = 55555) -> Bitmap Index Scan on relationships_user_id_index (cost=0.00..4.34 rows=11 width=0) (actual time=0.053..0.053 rows=40 loops=1) Index Cond: (user_id = 55555) -> Index Scan using large_user_id_started_at_index on large_table lt (cost=0.00..6768.48 rows=2297 width=622) (actual time=0.048..28.033 rows=1725 loops=40) Index Cond: (lt.user_id = relationships.contact_id) Total runtime: 3327.744 ms > How about > > SELECT * FROM large_table lt > WHERE lt.user_id = 12345 OR user_id IN (SELECT contact_id FROM > relationships WHERE user_id=12345) > ORDER BY created_at DESC LIMIT 10; Not good for the one with few matches: testdb=# EXPLAIN ANALYZE SELECT * FROM large_table lt WHERE lt.user_id = 12345 OR user_id IN (SELECT contact_id FROM relationships WHERE user_id=12345) ORDER BY created_at DESC LIMIT 10; QUERY PLAN ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=42.78..47.05 rows=10 width=622) (actual time=38360.090..62008.336 rows=10 loops=1) -> Index Scan Backward using large_created_at_index on large_table lt (cost=42.78..935924.84 rows=2192498 width=622) (actual time=38360.084..62008.269 rows=10 loops=1) Filter: ((user_id = 12345) OR (hashed subplan)) SubPlan -> Bitmap Heap Scan on relationships (cost=4.34..42.75 rows=11 width=4) (actual time=0.031..0.034 rows=1 loops=1) Recheck Cond: (user_id = 12345) -> Bitmap Index Scan on relationships_user_id_index (cost=0.00..4.34 rows=11 width=0) (actual time=0.020..0.020 rows=1 loops=1) Index Cond: (user_id = 12345) Total runtime: 62008.500 ms Good for the one with many early matches: testdb=# EXPLAIN ANALYZE SELECT * FROM large_table lt WHERE lt.user_id = 55555 OR user_id IN (SELECT contact_id FROM relationships WHERE user_id=55555) ORDER BY created_at DESC LIMIT 10; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=42.78..47.05 rows=10 width=622) (actual time=0.473..0.572 rows=10 loops=1) -> Index Scan Backward using large_created_at_index on large_table lt (cost=42.78..935924.84 rows=2192498 width=622) (actual time=0.467..0.512 rows=10 loops=1) Filter: ((user_id = 55555) OR (hashed subplan)) SubPlan -> Bitmap Heap Scan on relationships (cost=4.34..42.75 rows=11 width=4) (actual time=0.070..0.264 rows=40 loops=1) Recheck Cond: (user_id = 55555) -> Bitmap Index Scan on relationships_user_id_index (cost=0.00..4.34 rows=11 width=0) (actual time=0.047..0.047 rows=40 loops=1) Index Cond: (user_id = 55555) Total runtime: 0.710 ms > I am missing a unique constraint on (user_id, contact_id) - otherwise > the subselect is not equivalent to the join. > > It might be good to know whether contact_id = user_id is possible - > since this would rule out the possibility of a row satisfying both > branches of the union. Thanks for the hint - this is a rails project with the validations starting out in the application only, so sometimes we forget to also check the data integrity in the database. There were in fact a couple of duplicate user_id/contact_id pairs and a couple of rows where user_id=contact_id although those shouldn't be allowed. I added a unique index on (user_id, contact_id) and a check constraint to prevent (user_id=contact_id), vacuumed, and ran the 4 above query variants again - but it did not result in changed plans or substantial differences in execution time. > Probably you also should have foreign key constraints on > relationships.user_id and relationships.contact_id. These are unlikely > to affect performance though, in my experience. They are there, I just removed them from the schema output before posting, also assuming that they are not relevant for join performance. Til