Cost-based ORDER BY sort avoidance

Usually, sorting requires an extra step to put the data into the right order. This extra step can be avoided for data that are already in the right order.

For example, if a single-table query has an ORDER BY on a single column, and there is an index on that column, sorting can be avoided if Derby uses the index as the access path.

Where possible, Derby's query compiler transforms an SQL statement internally into one that avoids this extra step. For information about internal transformations, see Sort avoidance. This transformation, if it occurs, happens before optimization. After any such transformations are made, the optimizer can do its part to help avoid a separate sorting step by choosing an already sorted access path. It compares the cost of using that path with the cost of sorting. Derby does this for statements that use an ORDER BY clause in the following situations:

• The statements involve tables with indexes that are in the correct order.
• The statements involve scans of unique indexes that are guaranteed to return only one row per scan.

ORDER BY specifies a priority of ordering of columns in a result set. For example, ORDER BY X, Y means that column X has a more significant ordering than column Y.

The situations that allow Derby to avoid a separate ordering step for statements with ORDER BY clauses are:

• Index scans, which provide the correct order.

  -- covering index
  SELECT flight_id FROM Flights ORDER BY flight_id

• The rows from a table when fetched through an index scan.

  -- if Derby  uses the index on orig_airport
  -- to access the data, it can avoid the sort
  -- required by the final ORDER BY
  SELECT orig_airport, miles
  FROM FLIGHTS
  WHERE orig_airport < 'DDD'
  ORDER BY orig_airport

• The rows from a join when ordered by the indexed column or columns in the outer table.

  -- if Derby chooses Cities as the outer table, it
  -- can avoid a separate sorting step
  SELECT * FROM cities, countries
  WHERE cities.country_ISO_code = countries.country_ISO_code
  AND cities.country_ISO_code < 'DD'
  ORDER BY cities.country_ISO_code

• Result sets that are guaranteed to return a single row. They are ordered on all of their columns (for example, if there are equality conditions on all the columns in a unique index, all the columns returned for that table can be considered ordered, with any priority of ordering of the columns).

  -- query will only return one row, so that row is
  -- "in order" for ANY column
  SELECT miles
  FROM Flights
  WHERE flight_id = 'US1381' AND segment_number = 2
  ORDER BY miles

• Any column in a result set that has an equality comparison with a constant. The column is considered ordered with no priority to its ordering.

  -- The comparison of segment_number
  -- to a constant means that it is always correctly
  -- ordered. Using the index on (flight_id, segment_number)
  -- as the access path means
  -- that the ordering will be correct for the ORDER BY
  -- clause in this query. The same thing would be true if
  -- flight_id were compared to a constant instead.
  SELECT segment_number, flight_id
  FROM Flights
  WHERE segment_number=2
  ORDER BY segment_number, flight_id

  And because of transitive closure, this means that even more complex statements can avoid sorting. For example:

  -- transitive closure means that Derby will
  -- add this clause:
  -- AND countries.country_ISO_code = 'CL', which means
  -- that the ordering column is now compared to a constant,
  -- and sorting can be avoided.
  SELECT * FROM cities, countries
  WHERE cities.country_ISO_code = 'CL'
  AND cities.country_ISO_code = countries.country_ISO_code
  ORDER BY countries.country_ISO_code

  For more information about transitive closure and other statement transformations, see Internal language transformations.