Received: from maia.hub.org (maia-1.hub.org [200.46.208.211]) by mail.postgresql.org (Postfix) with ESMTP id B723463326A for ; Mon, 3 May 2010 10:57:40 -0300 (ADT) Received: from mail.postgresql.org ([200.46.204.86]) by maia.hub.org (mx1.hub.org [200.46.208.211]) (amavisd-maia, port 10024) with ESMTP id 45925-02 for ; Mon, 3 May 2010 13:57:23 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail-yw0-f200.google.com (mail-yw0-f200.google.com [209.85.211.200]) by mail.postgresql.org (Postfix) with ESMTP id 2BE63632347 for ; Mon, 3 May 2010 10:57:32 -0300 (ADT) Received: by ywh38 with SMTP id 38so1197914ywh.29 for ; Mon, 03 May 2010 06:57:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:received:mime-version:received:in-reply-to :references:from:date:message-id:subject:to:cc:content-type; bh=tg74yNvy+QX03JZyvrsTCeSg++IgvInskRMo1j/rcFU=; b=h5rB4Bdpp9K5XyAJMhYHnOT8m/c0c25eoz6WAGI5VWFcO+033ncOLqTdtcGudScIWJ wrvnEbdaE+z8HsvDGi2osax195JWllBSe7Yil/WFfCpM8HZjip9DqywYree7Fuahl9ig 5AJOioehVw9PZDmKSKt0kZtPq1njnE/1wlz/Q= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc:content-type; b=J89BdipbzLjnlI0Re7Kc+v/jddiV2Ix+OMQ7qeJGcGt955nOcEzhKXOvFqVKF+P5Ry SgUhA3Dh0gT3UAV/j0bA5tIf8Qp8+JNBQXt5VlvV1/Fm26W5OBsc6Fal0WrjZoEe2Ucr dLnjQ/45stqblVRdKe78sCd6ibqjD/c3d2K5w= Received: by 10.101.139.28 with SMTP id r28mr2397911ann.188.1272895047432; Mon, 03 May 2010 06:57:27 -0700 (PDT) MIME-Version: 1.0 Received: by 10.100.209.6 with HTTP; Mon, 3 May 2010 06:57:06 -0700 (PDT) In-Reply-To: <5252.1272300692@sss.pgh.pa.us> References: <5252.1272300692@sss.pgh.pa.us> From: Alexander Korotkov Date: Mon, 3 May 2010 17:57:06 +0400 Message-ID: Subject: Re: Planner issue on sorting joining of two tables with limit To: Tom Lane Cc: pgsql-performance@postgresql.org Content-Type: multipart/alternative; boundary=0016e6d3de5b293c5a0485b0f9ed X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=-1.899 tagged_above=-10 required=5 tests=BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001 X-Spam-Level: X-Archive-Number: 201005/23 X-Sequence-Number: 38607 --0016e6d3de5b293c5a0485b0f9ed Content-Type: text/plain; charset=ISO-8859-1 > > Well, no, because that plan wouldn't produce the specified ordering; > or at least it would be a lucky coincidence if it did. It's only > sorting on t1.value. > I just don't find why it is coincidence. I think that such plan will always produce result ordered by two columns, because such nested index scan always produce this result. Let's consider some simple example in order to illustrate how this plan works. t1 id | value ---+------ 1 | 0.1 2 | 0.3 3 | 0.2 t2 id | id1 | value ---+-----+------ 1 | 2 | 0.2 2 | 1 | 0.9 3 | 2 | 0.6 4 | 1 | 0.7 5 | 1 | 0.4 6 | 3 | 0.2 1) The outer index scan will find the row of t1 with least value using test1_value_idx. It will be row (1, 0.1) 2) The inner index scan will find all the rows in t2 where id1 = 1 using test2_id1_value_idx. But index test2_id1_value_idx have second order by value column and the index scan result will be ordered by value. That's why inner index scan will find rows (5, 1, 0.4), (4, 1, 0.7) and (2, 1, 0.9). And following query output will be produced: value1 | value2 --------+------- 0.1 | 0.4 0.1 | 0.7 0.1 | 0.9 3) The outer index scan will find the row of t1 with the second value using test1_value_idx. It will be row (3, 0.2) 4) The inner index scan will find all the rows in t2 where id1 = 3 using test2_id1_value_idx. This row is (6, 3, 0.2). The following query output will be produced: value1 | value2 --------+------- 0.2 | 0.2 5) The outer index scan will find the row of t1 with the third value using test1_value_idx. It will be row (2, 0.3) 6) The inner index scan will find all the rows in t2 where id1 = 2 using test2_id1_value_idx. These rows are (1, 2, 0.2) and (3, 2, 0.6). The following query output will be produced: value1 | value2 --------+------- 0.3 | 0.2 0.3 | 0.6 And the whole query result is: value1 | value2 --------+------- 0.1 | 0.4 0.1 | 0.7 0.1 | 0.9 0.2 | 0.2 0.3 | 0.2 0.3 | 0.6 And this result is really ordered by t1.value, t2.value. I can't find error in my reasoning :) The query without limit produce similar plan. EXPLAIN SELECT t1.value AS value1, t2.value AS value2 FROM test1 t1 JOIN test2 t2 ON t2.id1 = t1.id ORDER BY t1.value Nested Loop (cost=0.00..62109.86 rows=995025 width=16) -> Index Scan using test1_value_idx on test1 t1 (cost=0.00..19.19 rows=200 width=12) -> Index Scan using test2_id1_value_idx on test2 t2 (cost=0.00..248.27 rows=4975 width=12) Index Cond: (t2.id1 = t1.id) And I checked that the result is ordered by t1.value and t2.value. 2010/4/26 Tom Lane > =?KOI8-R?B?68/Sz9TLz9cg4czFy9PBzsTS?= writes: > > So PostgreSQL planner can produce the plan I need but it doesn't produce > > this plan when I specify particular second ordering column. > > Well, no, because that plan wouldn't produce the specified ordering; > or at least it would be a lucky coincidence if it did. It's only > sorting on t1.value. > > > So is there any > > way to make planner produce desired plan when particular second ordering > > column is specified? > > Not when the ordering columns come from two different tables. (If they > were in the same table then scanning a two-column index could produce > the demanded sort order.) I don't see any way to satisfy this query > without an explicit sort step, which means it has to look at the whole > join output. > > If you're willing to make assumptions like "the required 10 rows will be > within the first 100 t1.value rows" then you could nest an ORDER BY > t1.value LIMIT 100 query inside something that did an ORDER BY with both > columns. But this fails if you have too many duplicate t1.value values, > and your test case suggests that you might have a lot of them. In any > case it would stop being fast if you make the inner LIMIT very large. > > regards, tom lane > --0016e6d3de5b293c5a0485b0f9ed Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable
Well, no, because that plan wouldn't produc= e=20 the specified ordering;
or at least it would be a lucky coincidence if it did. =A0It's only
sorting on t1.value.
I just don'= ;t find why it is coincidence. I think that such=20 plan will=20 always produce result ordered by two columns, because such nested index=20 scan always produce this result.
Let's consider some simple example in order to illustrate how this plan= =20 works.

t1
id | value
---+------
1=A0 | 0.1
2=A0 | 0.33=A0 | 0.2

t2
id | id1 | value
---+-----+------
1=A0 |=A0 2=A0 = |=20 0.2
2=A0 |=A0 1=A0 | 0.9
3=A0 |=A0 2=A0 | 0.6
4=A0 |=A0 1=A0 | 0.7
5= =A0 |=A0 1=A0 | 0.4
6=A0 |=A0 3=A0 | 0.2

1) The outer index scan will find the row of t1 wit= h least value using test1_value_idx. It will be row (1, 0.1)
2) The=20 inner index scan will find all the rows in t2 where id1 =3D 1 using=20 test2_id1_value_idx. But index test2_id1_value_idx have second order by=20 value column and the index scan result will be ordered by value. That's= =20 why inner index scan will find rows (5, 1, 0.4), (4, 1, 0.7) and (2, 1,=20 0.9). And following query output will be produced:
value1=A0 | value2
--------+-------
0.1=A0=A0=A0=A0 | 0.4
0.1=A0= =A0=A0=A0 | 0.7
0.1=A0=A0=A0=A0 | 0.9
3) The outer index scan will find the row of t1 with the=20 second value using test1_value_idx. It will be row (3, 0.2)
4) The=20 inner index scan will find all the rows in t2 where id1 =3D 3 using=20 test2_id1_value_idx. This row is (6, 3, 0.2). The following query output will be produced:
value1=A0 | value2
--------+-------
0.2=A0=A0=A0=A0 | 0.2
5) The o= uter=20 index scan will find the row of t1 with the third value using=20 test1_value_idx. It will be row (2, 0.3)
6) The inner index scan will find all the rows in t2 where id1 =3D 2 using test2_id1_value_idx. These= =20 rows are (1, 2, 0.2) and (3, 2, 0.6). The following query output will be produced:
value1=A0 | value2
--------+-------
0.3=A0=A0=A0=A0 | 0.2
0.3=A0= =A0=A0=A0 | 0.6

And the whole query result is:
value1=A0 | value2
--------+-------
0.= 1=A0=A0=A0=A0 | 0.4
0.1=A0=A0=A0=A0 | 0.7
0.1=A0=A0=A0=A0 | 0.9
0.2=A0=A0=A0=A0= | 0.2
0.3=A0=A0=A0=A0 |=20 0.2
0.3=A0=A0=A0=A0 | 0.6

And this result is really ordered by t1.value,= =20 t2.value.
I can't find error in my reasoning :)

The query=20 without limit produce similar plan.

EXPLAIN SELECT=20 t1.value AS=20 value1, t2.value AS value2 FROM test1 t1 JOIN test2 t2 ON t2.id1 =3D t1.id ORDER BY t1.value

Nested Loop=A0 (cost=3D0.00..62109.86 rows=3D995025 width=3D16)
=A0 ->=A0 Index Scan using test1_value_idx on= test1 t1=A0=20 (cost=3D0.00..19.19 rows=3D200 width=3D12)
=A0 ->=A0=20 Index Scan using test2_id1_value_idx on test2 t2=A0 (cost=3D0.00..248.27=20 rows=3D4975 width=3D12)
=A0=A0=A0=A0=A0=A0=A0 Index Cond: (t2.id1 =3D t1.i= d)

And I checked that the result is ordered by t1.value and t2.value.
<= /div>
2010/4/26 Tom Lane &l= t;tgl@sss.pgh.pa.us>
=
=3D?KOI8-R?B?68/Sz9TLz9cg4czFy9PBzsTS?=3D <aekorotkov@gmail.com> writes:
> So PostgreSQL planner can produce the plan I need but it doesn't p= roduce
> this plan when I specify particular second ordering column.

Well, no, because that plan wouldn't produce the specified orderi= ng;
or at least it would be a lucky coincidence if it did. =A0It's only
sorting on t1.value.

> So is there any
> way to make planner produce desired plan when particular second orderi= ng
> column is specified?

Not when the ordering columns come from two different tables. =A0(If = they
were in the same table then scanning a two-column index could produce
the demanded sort order.) =A0I don't see any way to satisfy this query<= br> without an explicit sort step, which means it has to look at the whole
join output.

If you're willing to make assumptions like "the required 10 rows w= ill be
within the first 100 t1.value rows" then you could nest an ORDER BY t1.value LIMIT 100 query inside something that did an ORDER BY with both columns. =A0But this fails if you have too many duplicate t1.value values,<= br> and your test case suggests that you might have a lot of them. =A0In any case it would stop being fast if you make the inner LIMIT very large.

=A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0regards, tom lane

--0016e6d3de5b293c5a0485b0f9ed--