Sort rows

Status

The DuckDB step

Variants

Order rows by columns

Order the rows by the values of one or more columns or expressions, each ascending or descending, with nulls first or last.

Move a row by hand

Move one row up, down, or to the top or bottom of the table.

Reverse row order

Turn the current row order upside down without comparing any values.

Shuffle rows

Put the rows into a random order.

What other tools call it

Meridian's classification; an independent blind rating agreed on 86.2% of 312 rows (exact class, version 2).

Background

When to use it

The most common uses of sorted sequences are making lookup or search efficient, making the merging of sequences efficient, and processing data in a defined order.^[1] Sorting is also often useful for canonicalising data and for producing human-readable output.^[3]

In PostgreSQL, rows returned without a sort step come in an order that depends on the scan and join plan types and the order on disk, and that order must not be relied on.^[4] In SQL, an ORDER BY placed in a subquery or a view definition, where a database system allows one, has no effect on the order of the final result.^[2] In DuckDB, WHERE, LIMIT and SELECT guarantee that the original row order is preserved, while JOIN, GROUP BY and UNION do not guarantee it.^[5] Sort as the last step of the work, after the joins and aggregations, rather than counting on an earlier sort to survive them. (Meridian's view)

In DuckDB, ORDER BY may not use a stable algorithm, so it does not guarantee that the original row order is preserved.^[5] In DuckDB, row_number() OVER () turns the original row order into an explicit column that operations which do not preserve row order can refer to.^[5] When the order rows arrived in matters, number them before sorting and add that number as the last sort key, so that rows tied on every other key come out the same way on every run. (Meridian's view)

The SQL standard's core functionality does not explicitly define a default sort order for nulls, and its SQL:2003 extension T611 lets nulls be sorted first or last with NULLS FIRST or NULLS LAST.^[2] In PostgreSQL, nulls sort as if larger than any non-null value by default, so NULLS FIRST is the default for DESC order and NULLS LAST otherwise.^[4] Write NULLS FIRST or NULLS LAST into any sort whose result will be compared with one from another database system. (Meridian's view)

In DuckDB, text is sorted by its binary UTF-8 values by default, which works well for ASCII text but can give an incorrect order for other languages.^[6] In DuckDB, collations such as NOCASE and NOACCENT change how text is compared, and a collation can be set on an expression, on a table column or as the database default.^[7] Choose the collation deliberately when people will read the sorted list, and keep the binary order when the sort only needs to be repeatable. (Meridian's view)

The method

Formally, the output of any sorting algorithm must be in monotonic order and must be a permutation of the input, a reordering that retains all of the original elements.^[3] When records are sorted on one or more of their components, each such component is called a sort key.^[1] A new sort key can be created from two or more sort keys by lexicographical order, the first being the primary sort key and the second the secondary sort key.^[1] In PostgreSQL, when ORDER BY names more than one expression, the later values are used to sort rows that are equal according to the earlier values.^[4] In PostgreSQL, the ordering options apply to each sort column independently, so ORDER BY x, y DESC means ORDER BY x ASC, y DESC.^[4] In PostgreSQL, ascending order puts smaller values first, as defined by the < operator, and descending order is determined with the > operator.^[4]

A sorting algorithm is stable if, whenever two records have the same key and one appears before the other in the original list, it also appears before the other in the sorted list.^[3] An unstable sorting algorithm can be made stable by deciding comparisons between otherwise equal keys on the order of the entries in the original input, which may require additional time and space.^[3] Stability is important for preserving order over several sorts of the same data, since with an unstable sort a later sort could scramble the order an earlier one produced.^[3] Among the authors of early sorting algorithms around 1951 was Betty Holberton, who worked on ENIAC and UNIVAC.^[3]

In DuckDB, ORDER BY is an output modifier, applied logically near the very end of the query, just before LIMIT or OFFSET if present.^[6] External sorting is required when the data being sorted does not fit into a computer's main memory and must instead reside in slower external memory, usually a disk drive.^[8] In Apache Hop, the Sort Rows transform starts to page data to disk when it finds less free memory than a set threshold, keeping its temporary files in a sort directory.^[9] In Apache Hop, the Sort Rows transform is not supported on the Beam engines, because a Beam pipeline spreads rows over many workers and the transform could only order the rows a single worker holds.^[9]

The opposite of sorting, rearranging a sequence of items in a random or meaningless order, is called shuffling.^[1] The Fisher–Yates shuffle produces an unbiased permutation of a finite sequence, in which every permutation is equally likely.^[10] The Fisher–Yates shuffle was published in 1938 by Ronald Fisher and Frank Yates in their book Statistical tables for biological, agricultural and medical research.^[10]

Compared with the alternatives

In Power Query M, Table.ReverseRows returns a table with the rows of the input table in reverse order.^[11] Reverse the rows only when their current order is itself meaningful; otherwise sort descending on a named column. (Meridian's view)

In OpenRefine, a sort is temporary and the rows keep their original numbering until Reorder rows permanently is chosen, which changes the row numbers.^[12] Treat a sort shown on screen and a sort written into the stored data as two different steps, and record which one a result depends on. (Meridian's view)

Sources

1. [1]Sorting - Wikipediasecondary source
2. [2]Order by - Wikipediasecondary source
3. [3]Sorting algorithm - Wikipediasecondary source
4. [4]PostgreSQL: Documentation: 18: 7.5. Sorting Rows (ORDER BY)documentation
5. [5]Order Preservation – DuckDBdocumentation
6. [6]ORDER BY Clause – DuckDBdocumentation
7. [7]Collations – DuckDBdocumentation
8. [8]External sorting - Wikipediasecondary source
9. [9]Sort Rows | Apache Hopdocumentation
10. [10]Fisher–Yates shuffle - Wikipediasecondary source
11. [11]Table.ReverseRows - PowerQuery M | Microsoft Learndocumentation
12. [12]Sort and view | OpenRefinedocumentation

Used in