MIME-Version: 1.0
From: Clint Miller <clint.miller1@gmail.com>
Date: Fri, 23 Jun 2017 17:58:28 -0500
Message-ID: 
 <CALck7q=QCruONy5WSbyiSrGUyrHRxWfaLcT=TkDNEyozOVomTA@mail.gmail.com>
Subject: Efficiently merging and sorting collections of sorted rows
To: pgsql-performance@postgresql.org
Content-Type: multipart/alternative; boundary="94eb2c191c262197e10552a88a6f"
Precedence: bulk
Sender: pgsql-performance-owner@postgresql.org

--94eb2c191c262197e10552a88a6f
Content-Type: text/plain; charset="UTF-8"

Let's say I have the following table and index:

create table foo(s text, i integer);
create index foo_idx on foo (s, i);

If I run the following commands:

start transaction;
set local enable_sort = off;
explain analyze select * from foo where s = 'a' order by i;
end;

I get the following query plan:

Index Only Scan using foo_idx on foo (cost=0.14..8. 15 row=1 width=36)
(actual time=0.008..0.0 10 rows=3 loops=1)

  Index Cond: (s = 'a'::text)

  Heap Fetches: 3


That's a good plan because it's not doing a quick sort. Instead, it's just
reading the sort order off of the index, which is exactly what I want. (I
had to disable enable_sort because I didn't have enough rows of test data
in the table to get Postgres to use the index. But if I had enough rows,
the enable_sort stuff wouldn't be necessary. My real table has lots of rows
and doesn't need enable_sort turned off to do the sort with the index.)

But, if I run the following commands:

start transaction;
set local enable_sort = off;
explain analyze select * from foo where s = 'a' or s = 'b' order by i;
end;

I get the following plan:

Sort  (cost=10000000001.16..10000000001.16 rows=2 width=36) (actual
time=0.020..0.021 rows=7 loops=1)
  Sort Key: i
  Sort Method: quicksort  Memory: 25kB
  ->  Seq Scan on foo  (cost=0.00..1.15 rows=2 width=36) (actual
time=0.009..0.011 rows=7 loops=1)
        Filter: ((s = 'a'::text) OR (s = 'b'::text))
        Rows Removed by Filter: 3

Here, it's loading the full result set into memory and doing a quick sort.
(I think that's what it's doing, at least. If that's not the case, let me
know.) That's not good.

What I'd really like Postgres to do is use the index to get a sorted list
of rows where s = 'a'. Then, use the index again to get a sorted list of
rows where s = 'b'. Then it seems like Postgres should be able to merge the
sorted lists into a single sorted result set in O(n) time and O(1) memory
using a single merge operation.

Am I doing something wrong here? Is there a way to get Postgres to not do a
quick sort here?

My concern is that my real table has a significant number of rows, and the
result set will not fit into memory. So instead of getting a quick sort,
I'll end up getting a slow, disk-based merge sort. I really need the bulk
of the sort operation to come off of the index so that time and memory are
small.

Thanks for any help on this issue.

--94eb2c191c262197e10552a88a6f
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Let&#39;s say I have the following table and index:<div><b=
r></div><div><blockquote style=3D"margin:0px 0px 0px 40px;border:none;paddi=
ng:0px"><div><div>create table foo(s text, i integer);</div><div>create ind=
ex foo_idx on foo (s, i);</div></div><div><br></div></blockquote>If I run t=
he following commands:</div><div><br></div><div><blockquote style=3D"margin=
:0px 0px 0px 40px;border:none;padding:0px"><div><div>start transaction;</di=
v><div>set local enable_sort =3D off;</div><div>explain analyze select * fr=
om foo where s =3D &#39;a&#39; order by i;</div><div>end;</div></div><div><=
br></div></blockquote>I get the following query plan:</div><div><br></div><=
div><blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><=
div>Index Only Scan using foo_idx on foo (cost=3D0.14..8. 15 row=3D1 width=
=3D36) (actual time=3D0.008..0.0 10 rows=3D3 loops=3D1)</div></blockquote><=
blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=
=C2=A0 Index Cond: (s =3D &#39;a&#39;::text)</div></blockquote><blockquote =
style=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div>=C2=A0 Heap =
Fetches: 3</div></blockquote></div><div><br></div><div>That&#39;s a good pl=
an because it&#39;s not doing a quick sort. Instead, it&#39;s just reading =
the sort order off of the index, which is exactly what I want. (I had to di=
sable enable_sort because I didn&#39;t have enough rows of test data in the=
 table to get Postgres to use the index. But if I had enough rows, the enab=
le_sort stuff wouldn&#39;t be necessary. My real table has lots of rows and=
 doesn&#39;t need enable_sort turned off to do the sort with the index.)</d=
iv><div><br></div><div>But, if I run the following commands:</div><div><br>=
</div><div><blockquote style=3D"margin:0px 0px 0px 40px;border:none;padding=
:0px"><div><div>start transaction;</div><div>set local enable_sort =3D off;=
</div><div>explain analyze select * from foo where s =3D &#39;a&#39; or s =
=3D &#39;b&#39; order by i;</div><div>end;</div></div><div><br></div></bloc=
kquote>I get the following plan:</div><div><br></div><div><blockquote style=
=3D"margin:0px 0px 0px 40px;border:none;padding:0px"><div><div>Sort =C2=A0(=
cost=3D10000000001.16..10000000001.16 rows=3D2 width=3D36) (actual time=3D0=
.020..0.021 rows=3D7 loops=3D1)</div><div>=C2=A0 Sort Key: i</div><div>=C2=
=A0 Sort Method: quicksort =C2=A0Memory: 25kB</div><div>=C2=A0 -&gt; =C2=A0=
Seq Scan on foo =C2=A0(cost=3D0.00..1.15 rows=3D2 width=3D36) (actual time=
=3D0.009..0.011 rows=3D7 loops=3D1)</div><div>=C2=A0 =C2=A0 =C2=A0 =C2=A0 F=
ilter: ((s =3D &#39;a&#39;::text) OR (s =3D &#39;b&#39;::text))</div><div>=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 Rows Removed by Filter: 3</div></div><div><br><=
/div></blockquote>Here, it&#39;s loading the full result set into memory an=
d doing a quick sort. (I think that&#39;s what it&#39;s doing, at least. If=
 that&#39;s not the case, let me know.) That&#39;s not good.</div><div><br>=
</div><div>What I&#39;d really like Postgres to do is use the index to get =
a sorted list of rows where s =3D &#39;a&#39;. Then, use the index again to=
 get a sorted list of rows where s =3D &#39;b&#39;. Then it seems like Post=
gres should be able to merge the sorted lists into a single sorted result s=
et in O(n) time and O(1) memory using a single merge operation.</div><div><=
br></div><div>Am I doing something wrong here? Is there a way to get Postgr=
es to not do a quick sort here?</div><div><br></div><div>My concern is that=
 my real table has a significant number of rows, and the result set will no=
t fit into memory. So instead of getting a quick sort, I&#39;ll end up gett=
ing a slow, disk-based merge sort. I really need the bulk of the sort opera=
tion to come off of the index so that time and memory are small.</div><div>=
<br></div><div>Thanks for any help on this issue.</div></div>

--94eb2c191c262197e10552a88a6f--