Re: Sorting. When?

So, invoking or not invoking sorting depends on different parameters of the specific DBMS, does it?<br /><br /> This
alsomeans that it depends on the specific implementation of the Planner and, as a consequence, <b>on the specific
DBMS</b>?<br/> I mean, different DBMS can chose differently on invoking sorting even if they are executing the same
queryover the same set of data?<br /><br /> Fava.<br /><br /> Il 11/02/2011 22:49, Nicolas Barbier ha scritto:
<blockquotecite="mid:AANLkTimd-aUg-Zhu5kcxBRdSn7vi5KOaYOtMOmZwRd4p@mail.gmail.com" type="cite"><pre wrap="">2011/2/11
KevinGrittner <a class="moz-txt-link-rfc2396E"
href="mailto:Kevin.Grittner@wicourts.gov"><Kevin.Grittner@wicourts.gov></a>:

</pre><blockquote type="cite"><pre wrap=""><a class="moz-txt-link-rfc2396E"
href="mailto:mac_man2008@yahoo.it">"mac_man2008@yahoo.it"</a><a class="moz-txt-link-rfc2396E"
href="mailto:mac_man2008@yahoo.it"><mac_man2008@yahoo.it></a>wrote:
 

</pre><blockquote type="cite"><pre wrap="">I need to know, from an algorithmic point of view, in which cases
sorting is invoked.
</pre></blockquote></blockquote><pre wrap="">
[..]

</pre><blockquote type="cite"><pre wrap="">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?
</pre></blockquote><pre wrap="">
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:

<a class="moz-txt-link-rfc1738"
href="http://www.postgresql.org/docs/9.0/static/planner-optimizer.html"><URL:http://www.postgresql.org/docs/9.0/static/planner-optimizer.html></a>

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

</pre></blockquote><br />