Re: Sorting. When?

Hi.

Which operations invoke the sorting algorithms implemented in the
sorting module (tuplesort.c) ?
Of course, one of those operations invoking sorting is the ORDER BY
clause and the DISTINCT too.

Moreover, the Merge Join should be implemented invoking sorting.

Is there any other operation invoking sorting?

Thanks.
Regards.

Fava

2011/2/10 mac_man2008(at)yahoo(dot)it <mac_man2008(at)yahoo(dot)it>:

> Which operations invoke the sorting algorithms implemented in the sorting
> module (tuplesort.c) ?
> Of course, one of those operations invoking sorting is the ORDER BY clause
> and the DISTINCT too.
>
> Moreover, the Merge Join should be implemented invoking sorting.
>
> Is there any other operation invoking sorting?

AFAIK, all set operators except for UNION ALL. (I am probably missing
a whole boatload of other things.)

Nicolas

On Thu, Feb 10, 2011 at 6:21 PM, Nicolas Barbier
<nicolas(dot)barbier(at)gmail(dot)com> wrote:
> 2011/2/10 mac_man2008(at)yahoo(dot)it <mac_man2008(at)yahoo(dot)it>:
>
>> Which operations invoke the sorting algorithms implemented in the sorting
>> module (tuplesort.c) ?
>> Of course, one of those operations invoking sorting is the ORDER BY clause
>> and the DISTINCT too.
>>
>> Moreover, the Merge Join should be implemented invoking sorting.
>>
>> Is there any other operation invoking sorting?
>
> AFAIK, all set operators except for UNION ALL. (I am probably missing
> a whole boatload of other things.)

Merge joins don't necessarily involve a sort - you could do a merge
over a pair of index scans, for example.

Set operations can be implemented using hashing or sorting, too.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Thank you all for your replies.

So, is there any precise way to discover when sorting is invoked?

Thanks.
Regards.

Fava

Il 11/02/2011 01:17, Robert Haas ha scritto:
> On Thu, Feb 10, 2011 at 6:21 PM, Nicolas Barbier
> <nicolas(dot)barbier(at)gmail(dot)com> wrote:
>> 2011/2/10 mac_man2008(at)yahoo(dot)it<mac_man2008(at)yahoo(dot)it>:
>>
>>> Which operations invoke the sorting algorithms implemented in the sorting
>>> module (tuplesort.c) ?
>>> Of course, one of those operations invoking sorting is the ORDER BY clause
>>> and the DISTINCT too.
>>>
>>> Moreover, the Merge Join should be implemented invoking sorting.
>>>
>>> Is there any other operation invoking sorting?
>> AFAIK, all set operators except for UNION ALL. (I am probably missing
>> a whole boatload of other things.)
> Merge joins don't necessarily involve a sort - you could do a merge
> over a pair of index scans, for example.
>
> Set operations can be implemented using hashing or sorting, too.
>

[ Please don't top-post. <URL:http://en.wikipedia.org/wiki/Posting_style> ]

2011/2/11 mac_man2008(at)yahoo(dot)it <mac_man2008(at)yahoo(dot)it>:

> So, is there any precise way to discover when sorting is invoked?

EXPLAIN shows how a query would be executed; explicit sorts should be
mostly obvious.
<URL:http://www.postgresql.org/docs/9.0/static/sql-explain.html>

Nicolas

Nicolas, thanks.

Unfortunately I don't think I can get precise infos from that link. That
"explains" how the EXPLAIN works, while I need to know, from an
algorithmic point of view, in which cases sorting is invoked.
Actually, maybe I can spend some time in trying to perform samples
queries and trying to deduce which operations calls the sorting module.
But I think it is not the most effective way to do that, since that
would mean running a bounch of queries for different values of work_mem,
or for different size of the involved tables. Even if I try to do that,
some cases can not be evident to my sight.

I am searching for someone telling me (how to get) a list of operations
invoking sorting, and in which cases they do that.
Just for example:
- ORDER BY, always invokes sorting.
- DISTINCT, always invokes sorting
- Merge Join, just in case (..bla bla bla..)
- ...

Is it possible?
Any other suggestion?

Thanks for your time.
Best regards.

Fava

Il 11/02/2011 11:50, Nicolas Barbier ha scritto:
> [ Please don't top-post.<URL:http://en.wikipedia.org/wiki/Posting_style> ]
>
> 2011/2/11 mac_man2008(at)yahoo(dot)it<mac_man2008(at)yahoo(dot)it>:
>
>> So, is there any precise way to discover when sorting is invoked?
> EXPLAIN shows how a query would be executed; explicit sorts should be
> mostly obvious.
> <URL:http://www.postgresql.org/docs/9.0/static/sql-explain.html>
>
> Nicolas
>

"mac_man2008(at)yahoo(dot)it" <mac_man2008(at)yahoo(dot)it> wrote:

> I need to know, from an algorithmic point of view, in which cases
> sorting is invoked.

Well, I think the only accurate answer to that is "when the
estimated cost of a plan using a sort is lower than the estimated
cost of any alternatives". There are cases where you can be sure a
sort will be used, like when you have an ORDER BY clause and there
is no index which can scan rows in that order; but there are a lot
of situations where plans which involve sorts are in competition
with plans which don't. The plan chosen can depend on such things
as how bloated your table is, how close the order of the tuples in
the heap corresponds to the order of a particular index, how many
rows are in which tables, what work_mem is set to, etc.

Are your really looking to categorize the types of queries where
sorting is *invoked*, or the ones where it is *considered*? Or
perhaps only those where it is *required*, since there are no
possible plans without sorting?

-Kevin

2011/2/11 Kevin Grittner <Kevin(dot)Grittner(at)wicourts(dot)gov>:

> "mac_man2008(at)yahoo(dot)it" <mac_man2008(at)yahoo(dot)it> wrote:
>
>> I need to know, from an algorithmic point of view, in which cases
>> sorting is invoked.

[..]

> Are your really looking to categorize the types of queries where
> sorting is *invoked*, or the ones where it is *considered*?  Or
> perhaps only those where it is *required*, since there are no
> possible plans without sorting?

Or, if you are seeking the exact rules that are used by the planner to
determine all possible plans from which the one with minimum cost is
chosen (and hence all ways in which sorts can be used), I think that
the source code is the only complete reference. A non-complete
introduction is:

<URL:http://www.postgresql.org/docs/9.0/static/planner-optimizer.html>

Basically, physical operators (seq scan, index scan, hash join, merge
join, nested loop, filter, set operation, etc) may require their input
to satisfy certain sort constraints (for example, both inputs of a
merge join need to be sorted on the join attribute(s)). If it happens
to be of lowest cost to explicitly sort the inputs right before
consuming them, that will be done. If there is a way to get the same
input in an already-ordered way (for example an index scan, or the
output of a merge join), so that the cost is less than the non-ordered
way + an explicit sort, then that already-ordered way will be chosen.

Super-basic example:

SELECT * FROM t ORDER BY a;

This may either perform a seq scan of table t and then do an explicit
sort, or perform a full index scan of an index on attribute a
(provided that such an index exists), in which case the explicit sort
is not needed because the index scan will deliver the rows in
already-sorted order. Which option is chosen depends on the cost: The
costs of both plans are calculated and the least costly plan is
chosen. See the (non-exhaustive) list of things that influence the
costs provided by Kevin to get a feeling for how many variables there
are that influence this choice.

Nicolas

So, invoking or not invoking sorting depends on different parameters of
the specific DBMS, does it?

This also means that it depends on the specific implementation of the
Planner and, as a consequence, *on the specific DBMS*?
I mean, different DBMS can chose differently on invoking sorting even if
they are executing the same query over the same set of data?

Fava.

Il 11/02/2011 22:49, Nicolas Barbier ha scritto:
> 2011/2/11 Kevin Grittner<Kevin(dot)Grittner(at)wicourts(dot)gov>:
>
>> "mac_man2008(at)yahoo(dot)it"<mac_man2008(at)yahoo(dot)it> wrote:
>>
>>> I need to know, from an algorithmic point of view, in which cases
>>> sorting is invoked.
> [..]
>
>> Are your really looking to categorize the types of queries where
>> sorting is *invoked*, or the ones where it is *considered*? Or
>> perhaps only those where it is *required*, since there are no
>> possible plans without sorting?
> Or, if you are seeking the exact rules that are used by the planner to
> determine all possible plans from which the one with minimum cost is
> chosen (and hence all ways in which sorts can be used), I think that
> the source code is the only complete reference. A non-complete
> introduction is:
>
> <URL:http://www.postgresql.org/docs/9.0/static/planner-optimizer.html>
>
> Basically, physical operators (seq scan, index scan, hash join, merge
> join, nested loop, filter, set operation, etc) may require their input
> to satisfy certain sort constraints (for example, both inputs of a
> merge join need to be sorted on the join attribute(s)). If it happens
> to be of lowest cost to explicitly sort the inputs right before
> consuming them, that will be done. If there is a way to get the same
> input in an already-ordered way (for example an index scan, or the
> output of a merge join), so that the cost is less than the non-ordered
> way + an explicit sort, then that already-ordered way will be chosen.
>
> Super-basic example:
>
> SELECT * FROM t ORDER BY a;
>
> This may either perform a seq scan of table t and then do an explicit
> sort, or perform a full index scan of an index on attribute a
> (provided that such an index exists), in which case the explicit sort
> is not needed because the index scan will deliver the rows in
> already-sorted order. Which option is chosen depends on the cost: The
> costs of both plans are calculated and the least costly plan is
> chosen. See the (non-exhaustive) list of things that influence the
> costs provided by Kevin to get a feeling for how many variables there
> are that influence this choice.
>
> Nicolas
>

2011/2/12 mac_man2008(at)yahoo(dot)it <mac_man2008(at)yahoo(dot)it>:
> So, invoking or not invoking sorting depends on different parameters of the
> specific DBMS, does it?
>
> This also means that it depends on the specific implementation of the
> Planner and, as a consequence, on the specific DBMS?
> I mean, different DBMS can chose differently on invoking sorting even if
> they are executing the same query over the same set of data?
>

exactly

Regards

Pavel Stehule

> Fava.
>
> Il 11/02/2011 22:49, Nicolas Barbier ha scritto:
>
> 2011/2/11 Kevin Grittner <Kevin(dot)Grittner(at)wicourts(dot)gov>:
>
> "mac_man2008(at)yahoo(dot)it" <mac_man2008(at)yahoo(dot)it> wrote:
>
> I need to know, from an algorithmic point of view, in which cases
> sorting is invoked.
>
> [..]
>
> Are your really looking to categorize the types of queries where
> sorting is *invoked*, or the ones where it is *considered*?  Or
> perhaps only those where it is *required*, since there are no
> possible plans without sorting?
>
> Or, if you are seeking the exact rules that are used by the planner to
> determine all possible plans from which the one with minimum cost is
> chosen (and hence all ways in which sorts can be used), I think that
> the source code is the only complete reference. A non-complete
> introduction is:
>
> <URL:http://www.postgresql.org/docs/9.0/static/planner-optimizer.html>
>
> Basically, physical operators (seq scan, index scan, hash join, merge
> join, nested loop, filter, set operation, etc) may require their input
> to satisfy certain sort constraints (for example, both inputs of a
> merge join need to be sorted on the join attribute(s)). If it happens
> to be of lowest cost to explicitly sort the inputs right before
> consuming them, that will be done. If there is a way to get the same
> input in an already-ordered way (for example an index scan, or the
> output of a merge join), so that the cost is less than the non-ordered
> way + an explicit sort, then that already-ordered way will be chosen.
>
> Super-basic example:
>
> SELECT * FROM t ORDER BY a;
>
> This may either perform a seq scan of table t and then do an explicit
> sort, or perform a full index scan of an index on attribute a
> (provided that such an index exists), in which case the explicit sort
> is not needed because the index scan will deliver the rows in
> already-sorted order. Which option is chosen depends on the cost: The
> costs of both plans are calculated and the least costly plan is
> chosen. See the (non-exhaustive) list of things that influence the
> costs provided by Kevin to get a feeling for how many variables there
> are that influence this choice.
>
> Nicolas
>
>
>

"mac_man2008(at)yahoo(dot)it" <mac_man2008(at)yahoo(dot)it> wrote:

> So, invoking or not invoking sorting depends on different
> parameters of the specific DBMS, does it?

In the right circumstances (where autovacuum or other maintenance
jobs happen to run in the background at the right moment), two
back-to-back runs on the same database with no data or configuration
changes could do this differently. You wouldn't see that too often,
but if the estimated costs of sorting versus non-sorting plans were
close, the random sampling of one statistics sampling run versus
another could cause a change.

-Kevin