2011/2/11 Kevin Grittner <kevin.gritt...@wicourts.gov>: > "mac_man2...@yahoo.it" <mac_man2...@yahoo.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 -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers