Date: Sat, 22 Sep 2007 14:33:21 +0200 (CEST)
From: Denes Daniel <panther-d@freemail.hu>
Subject: Re: Query planner unaware of possibly best plan
To: Tom Lane <tgl@sss.pgh.pa.us>
cc: pgsql-performance@postgresql.org
In-Reply-To: <9259.1190441248@sss.pgh.pa.us>
Message-ID: <freemail.20070822143321.8034@fm03.freemail.hu>
MIME-Version: 1.0
Content-Type: MULTIPART/MIXED; BOUNDARY="0-1804289383-1190464401=:8034"

--0-1804289383-1190464401=:8034
Content-Type: TEXT/PLAIN; CHARSET=ISO-8859-2
Content-Transfer-Encoding: QUOTED-PRINTABLE

Tom Lane <tgl@sss.pgh.pa.us> wrote:

> The point here is that you've repeated the same example N times
> without actually making a case that it's interesting to support.  We
> have to think about the intellectual complexity that would be added
> to the planner to support this case, and the cycles that would be
> expended on every query (and wasted, for most queries) on trying to
> detect whether the case applies.  If it were simple and cheap to do,
> these arguments wouldn't hold much weight, but it doesn't look to
> me like either is the case.
>=20
> Another problem is that it's not clear there's much to be gained.
> Avoiding the sort step is only interesting if the query produces so
> many rows that a sort would be expensive ... but if that's the case, it
> seems unlikely that a nestloop indexscan plan would be the best
> choice anyway.
>=20
> So basically this looks like a lot of work for a narrow and questionable
> gain.  If you want it to happen you need to convince people that it's
> easier and more useful than it looks.
>=20
> =09=09=09regards, tom lane


Well, I probably won't tell you that it's easy to do, because you know=20
the planner far far better than I do -- I'm just a user who knows almost=20
nothing about what's happening inside it. I just thought that if the=20
planner is examining a plan, where the outer scan is using a unique=20
index with all it's columns AND doing a nestloop join with the inner scan=
=20
returning the rows in some order, then the planner could say "this is=20
already ordered by (outer.unique, inner.some_order)" and wouldn't=20
make a sort at the end. Of course this is far from perfect, because what=20
about three/four/more table joins... maybe that can be derived from=20
this, I don't really know now.
Another situation that could be optimized this way is if I write "ORDER=20
BY outer.idxcol1, outer.idxcol2, outer.id, inner.something" where
 + there is a non-unique index on (outer.idxcol1, outer.idxcol2),
 + outer.id is a PRI KEY,
 + there is an index on (inner.outer_id, inner.something) too
but that's getting really complicated. Of course if the simpler case=20
would be working, then I could create a unique index on (outer.idxcol1,=20
outer.idxcol2, outer.id) and this would run optimized too.

I think what's common is:
 + outer scan produces uniquely sorted rows
 + nested loop
 + inner scan produces sorted rows
 + ORDER BY says outer.unique_sort, inner.sort
If this is the situation, the sort could be done separately. Even like:

->  Nested Loop
  -> Sort by outer.unique
     ->  Scan producing the required rows from outer
  -> Sort by inner.something
     ->  Scan producing the required rows from inner
         Filter or Index Cond for the join

And this is good for any query that needs data from two tables, but=20
wants to get the joined rows so that all rows for a single outer-row=20
are "packed together" (I mean they do not mix).


Now about if it's worth it. I tried a query on real data, with lots of rows=
.
Tables involved:
- threads: ~200K rows
- msgs: ~8M rows
I wanted to see the last msgs from the last threads, but did not want=20
to mix them. It's like PgSQL's mailing archive viewed by threads. I=20
wanted them paged, not all 8M msgs at once (LIMIT/OFFSET). Query is:

SELECT *
FROM threads AS thr JOIN msgs AS msg ON msg.thrid =3D thr.id
WHERE thr.forid =3D 1
ORDER BY thr.id DESC, msg.msgid DESC
LIMIT 100

thr.forid is a FKEY to forums. Say forum 1 is the pgsql-performance list.
Table msgs has only a PRI KEY: (thrid, msgid).
Table threads has a PRI KEY: (id) and a unique index: (forid, id).
First time I ran the query with seqscan, bitmapscan, hashjoin,=20
mergejoin disabled (just to get the nested loop plan with the needless=20
sort). Second time I ran it without disabling anything, but I modified=20
ORDER BY to only "thr.id DESC" (deleted "msg.msgid DESC"), to give me=20
the same plan as before, but without the sort.
PSQL input and output attached.

I think the 5000x speed would be worth it.


Regards,
Denes Daniel
---------------------------------


=0A=0AJ=E1tssz a meg=FAjult Kv=EDzparton! V=E1lassz t=F6bb mint 400 kv=EDz =
k=F6z=FCl minden t=E9m=E1ban!
________________________________________________________
http://cthandler.adverticum.net/?cturl=3Dhttp%3A%2F%2Fkvizpart.hu%2F?fmalja


--0-1804289383-1190464401=:8034
Content-Type: TEXT/plain; name="expana.txt"; CHARSET=ISO-8859-2
Content-Disposition: attachment; filename="expana.txt"

-- =========== Test #1 =========== --

BEGIN;
SET enable_seqscan TO false; SET enable_bitmapscan TO false; SET enable_hashjoin TO false; SET enable_mergejoin TO false;
EXPLAIN ANALYZE SELECT * FROM threads AS thr JOIN msgs AS msg ON msg.thrid = thr.id WHERE thr.forid = 1 ORDER BY thr.id DESC, msg.msgid DESC LIMIT 100;
ROLLBACK;

                                                                            QUERY PLAN                                                                   
-------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=64537577.92..64537677.92 rows=100 width=447) (actual time=61923.813..61924.379 rows=100 loops=1)
   ->  Sort  (cost=64537577.92..64633839.92 rows=96262 width=447) (actual time=61923.804..61924.038 rows=100 loops=1)
         Sort Key: thr.id, msg.msgid
         ->  Nested Loop  (cost=0.00..61339121.37 rows=96262 width=447) (actual time=0.248..40366.113 rows=431350 loops=1)
               ->  Index Scan using threads_uni_forid_id on threads thr  (cost=0.00..14229.22 rows=2850 width=176) (actual time=0.127..5246.470 rows=8339 loops=1)
                     Index Cond: (forid = 1)
               ->  Index Scan using msgs_pkey on msgs msg  (cost=0.00..12595.51 rows=2974 width=271) (actual time=1.544..4.000 rows=52 loops=8339)
                     Index Cond: (msg.thrid = "outer".id)
 Total runtime: 62079.452 ms
(9 rows)


-- =========== Test #2 =========== --

EXPLAIN ANALYZE SELECT * FROM threads AS thr JOIN msgs AS msg ON msg.thrid = thr.id WHERE thr.forid = 1 ORDER BY thr.id DESC LIMIT 100;

                                                                             QUERY PLAN                                                                    
----------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..63721.01 rows=100 width=447) (actual time=9.579..10.775 rows=100 loops=1)
   ->  Nested Loop  (cost=0.00..61339121.37 rows=96262 width=447) (actual time=9.574..10.438 rows=100 loops=1)
         ->  Index Scan Backward using threads_uni_forid_id on threads thr  (cost=0.00..14229.22 rows=2850 width=176) (actual time=0.082..0.145 rows=4 loops=1)
               Index Cond: (forid = 1)
         ->  Index Scan using msgs_pkey on msgs msg  (cost=0.00..12595.51 rows=2974 width=271) (actual time=2.399..2.475 rows=25 loops=4)
               Index Cond: (msg.thrid = "outer".id)
 Total runtime: 11.071 ms
(7 rows)


--0-1804289383-1190464401=:8034--