Received: from localhost (maia-1.hub.org [200.46.204.191]) by postgresql.org (Postfix) with ESMTP id 9DC029FB1EF for ; Sat, 28 Jul 2007 17:54:53 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.191]) (amavisd-maia, port 10024) with ESMTP id 69245-08 for ; Sat, 28 Jul 2007 17:54:49 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.5 Received: from mailb.org (mailb.org [213.239.200.52]) by postgresql.org (Postfix) with ESMTP id AEEC29FB1EC for ; Sat, 28 Jul 2007 17:54:49 -0300 (ADT) Received: from localhost (e178042039.adsl.alicedsl.de [85.178.42.39]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mailb.org (Postfix) with ESMTP id E6865457448 for ; Sat, 28 Jul 2007 22:54:46 +0200 (CEST) Received: by localhost (sSMTP sendmail emulation); Sat, 28 Jul 2007 22:54:50 +0200 Date: Sat, 28 Jul 2007 22:54:50 +0200 From: Tilmann Singer To: pgsql-performance@postgresql.org Subject: Re: Slow query with backwards index scan Message-ID: <20070728205450.GI19392@tils.net> References: <200707281903.l6SJ3qs07818@pillette.com> <20070728192713.GH19392@tils.net> <46ABA1AA.7020701@emolecules.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <46ABA1AA.7020701@emolecules.com> 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.136 tagged_above=0 required=5 tests=AWL=0.135, BAYES_50=0.001 X-Spam-Level: X-Archive-Number: 200707/405 X-Sequence-Number: 26089 * Craig James [20070728 22:00]: > >>SELECT * FROM ( > >> (SELECT * FROM large_table lt > >> WHERE lt.user_id = 12345 > >> ORDER BY created_at DESC LIMIT 10) AS q1 > >> UNION > >> (SELECT * FROM large_table lt > >> WHERE user_id IN (SELECT contact_id FROM relationships WHERE > >> user_id=12345) > >> ORDER BY created_at DESC LIMIT 10) AS q2 > >>ORDER BY created_at DESC LIMIT 10; > > > >It's not possible to use ORDER BY or LIMIT within unioned queries. > > > >http://www.postgresql.org/docs/8.2/static/sql-select.html#SQL-UNION > > If I'm reading this documentation correctly, it *is* possible, as long as > they're inside of a sub-select, as in this case. I completely overlooked that obvious note in the documentation, sorry. I tried it only with the aliases which fooled me into thinking that doesn't work at all: testdb=# (select 1 limit 1) as q1 union (select 2) as q2; ERROR: syntax error at or near "as" LINE 1: (select 1 limit 1) as q1 union (select 2) as q2; ^ but this works: testdb=# (select 1 limit 1) union (select 2); ?column? ---------- 1 2 Great - that works! What I didn't realize in the original post is that the problem actually seems to be how to retrieve the rows from large_table for the correlated relationships in an efficient way - the second of the two queries that could be UNIONed. Using a subselect is efficient for the user with few relationships and matched rows at the end of the sorted large_table: testdb=# EXPLAIN ANALYZE SELECT * FROM large_table lt WHERE user_id IN (SELECT contact_id FROM relationships WHERE user_id=12345) ORDER BY created_at DESC LIMIT 10; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=6963.94..6963.96 rows=10 width=621) (actual time=94.598..94.629 rows=4 loops=1) -> Sort (cost=6963.94..6966.96 rows=1211 width=621) (actual time=94.592..94.602 rows=4 loops=1) Sort Key: lt.created_at -> Nested Loop (cost=39.52..6901.92 rows=1211 width=621) (actual time=85.670..94.547 rows=4 loops=1) -> HashAggregate (cost=39.52..39.53 rows=1 width=4) (actual time=23.549..23.552 rows=1 loops=1) -> Bitmap Heap Scan on relationships (cost=4.33..39.49 rows=10 width=4) (actual time=23.526..23.530 rows=1 loops=1) Recheck Cond: (user_id = 12345) -> Bitmap Index Scan on relationships_user_id_contact_id_index (cost=0.00..4.33 rows=10 width=0) (actual time=0.027..0.027 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..6834.04 rows=2268 width=621) (actual time=62.108..70.952 rows=4 loops=1) Index Cond: (lt.user_id = relationships.contact_id) Total runtime: 94.875 ms But the subselect is not fast for the user with many relationships and matched rows at the beginning of the sorted large_table: testdb=# EXPLAIN ANALYZE SELECT * FROM large_table lt WHERE user_id IN (SELECT contact_id FROM relationships WHERE user_id=55555) ORDER BY created_at DESC LIMIT 10; QUERY PLAN ----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=6963.94..6963.96 rows=10 width=621) (actual time=53187.349..53187.424 rows=10 loops=1) -> Sort (cost=6963.94..6966.96 rows=1211 width=621) (actual time=53187.341..53187.360 rows=10 loops=1) Sort Key: lt.created_at -> Nested Loop (cost=39.52..6901.92 rows=1211 width=621) (actual time=201.728..52673.800 rows=69018 loops=1) -> HashAggregate (cost=39.52..39.53 rows=1 width=4) (actual time=178.777..178.966 rows=40 loops=1) -> Bitmap Heap Scan on relationships (cost=4.33..39.49 rows=10 width=4) (actual time=47.049..178.560 rows=40 loops=1) Recheck Cond: (user_id = 55555) -> Bitmap Index Scan on relationships_user_id_contact_id_index (cost=0.00..4.33 rows=10 width=0) (actual time=28.721..28.721 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..6834.04 rows=2268 width=621) (actual time=21.994..1301.375 rows=1725 loops=40) Index Cond: (lt.user_id = relationships.contact_id) Total runtime: 53188.584 ms Using a join now the query for matches for the user with little data is slow: testdb=# EXPLAIN ANALYZE SELECT * FROM large_table lt JOIN relationships r ON lt.user_id=r.contact_id WHERE r.user_id=12345 ORDER BY lt.created_at DESC LIMIT 10; QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.00..24116.65 rows=10 width=645) (actual time=100348.436..145552.633 rows=4 loops=1) -> Nested Loop (cost=0.00..28751864.52 rows=11922 width=645) (actual time=100348.429..145552.602 rows=4 loops=1) -> Index Scan Backward using large_created_at_index on large_table lt (cost=0.00..824833.09 rows=4384343 width=621) (actual time=28.961..82448.167 rows=4384064 loops=1) -> Index Scan using relationships_user_id_contact_id_index on relationships r (cost=0.00..6.36 rows=1 width=24) (actual time=0.009..0.009 rows=0 loops=4384064) Index Cond: ((r.user_id = 12345) AND (lt.user_id = r.contact_id)) Total runtime: 145552.809 ms And for the user with much data it's fast: testdb=# EXPLAIN ANALYZE SELECT * FROM large_table lt JOIN relationships r ON lt.user_id=r.contact_id WHERE r.user_id=55555 ORDER BY lt.created_at DESC LIMIT 10; QUERY PLAN ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- Limit (cost=0.00..24116.65 rows=10 width=645) (actual time=0.068..0.428 rows=10 loops=1) -> Nested Loop (cost=0.00..28751864.52 rows=11922 width=645) (actual time=0.063..0.376 rows=10 loops=1) -> Index Scan Backward using large_created_at_index on large_table lt (cost=0.00..824833.09 rows=4384343 width=621) (actual time=0.028..0.064 rows=13 loops=1) -> Index Scan using relationships_user_id_contact_id_index on relationships r (cost=0.00..6.36 rows=1 width=24) (actual time=0.010..0.013 rows=1 loops=13) Index Cond: ((r.user_id = 55555) AND (lt.user_id = r.contact_id)) Total runtime: 0.609 ms Any ideas? tia, Til