# Sorting and Grouping > Understand in-memory, external, and incremental sorting, hash aggregation, grouping sorted data, and window frames in PostgreSQL 18. --- LLMS index: [llms.txt](/en/llms.txt) --- ## 1. Sorting {#qpt-section-4-1} A B-tree index can produce rows in index order. When that order matches the query’s `ORDER BY`, PostgreSQL can sometimes avoid an explicit sort: ```sql EXPLAIN (costs off) SELECT * FROM flights ORDER BY flight_id; QUERY PLAN ------------------------------------------ Index Scan using flights_pkey on flights (1 row) ``` If the required ordering is not available from an access path, PostgreSQL needs two separate steps: obtain the rows and sort them. ```sql EXPLAIN (costs off) SELECT * FROM flights ORDER BY status; QUERY PLAN -------------------------- Sort Sort Key: status -> Seq Scan on flights (3 rows) ``` ### In-Memory Sort {#qpt-p71-in-memory-sort} In the simplest case, the data being sorted fits in the memory available to the sort operation under `work_mem`. PostgreSQL can then sort it in memory. `EXPLAIN ANALYZE` shows both the sort method and the amount of memory used: ```sql EXPLAIN (analyze, timing off, summary off, buffers off) SELECT * FROM seats ORDER BY seat_no; QUERY PLAN ------------------------------------------------------------ Sort (cost=121.13..125.48 rows=1741 width=15) (actual ... Sort Key: seat_no Sort Method: quicksort Memory: 103kB -> Seq Scan on seats (cost=0.00..27.41 rows=1741 wid... (4 rows) ``` A regular `Sort` node cannot return its first row until it has consumed and sorted its input. Its startup cost therefore includes the cost of reading the complete input. For a comparison sort, the typical amount of work grows on the order of \\(O(M \log M)\\), where M is the number of input rows. If the query needs only the first N rows of the sorted result, for example because of `LIMIT`, PostgreSQL can use a bounded top-N sort rather than fully sorting every row: ```sql EXPLAIN (analyze, timing off, summary off, buffers off) SELECT * FROM seats ORDER BY seat_no LIMIT 100; ``` ```text QUERY PLAN ------------------------------------------------------------ Limit (cost=93.95..94.20 rows=100 width=15) (actual ro... -> Sort (cost=93.95..98.30 rows=1741 width=15) (actu... Sort Key: seat_no Sort Method: top-N heapsort Memory: 30kB -> Seq Scan on seats (cost=0.00..27.41 rows=1741... (5 rows) ``` The estimated query cost is lower, and the sort uses less memory. A top-N heapsort needs work on the order of \\(O(M \log N)\\) rather than sorting all M rows completely. ### External Sort {#qpt-p72-external-sort} If the data set is too large to sort within the available memory, PostgreSQL uses an external sort. The sorter reads as much input as it can handle in memory, sorts that portion, and writes a sorted **run** to a temporary file. ![External sorting: input rows are sorted in work_mem and written as sorted runs to temporary files.](/images/qpt/p072-external-sort.svg) {#qpt-fig-4-1 num="4.1" caption="External Sort: Writing Sorted Runs" .book-original-figure .d-flex .flex-column .align-items-center width=413 height=268} The process repeats until all input has been turned into individually sorted runs. `temp_file_limit` limits the total space used at any one time by temporary files belonging to a PostgreSQL process. Explicit temporary tables are not counted against this limit. The sorted runs are then merged. Conceptually, the merge keeps track of the next candidate from each input run, selects the smallest or largest one, returns it, and advances that run. The implementation reads data in buffered blocks rather than literally one row at a time so that I/O remains efficient. ![Merging sorted runs from temporary files through work_mem.](/images/qpt/p073-external-merge.svg) {#qpt-fig-4-2 num="4.2" caption="External Sort: Merging Sorted Runs" .book-original-figure .d-flex .flex-column .align-items-center width=280 height=268} If memory is insufficient to merge all runs in one pass, PostgreSQL performs a multi-pass merge: groups of runs are merged into larger runs, which are then merged again until the final ordered stream can be produced. A large sort makes the use of temporary storage visible in `EXPLAIN ANALYZE`: ```sql EXPLAIN (analyze, timing off, summary off) SELECT * FROM bookings ORDER BY total_amount; QUERY PLAN ------------------------------------------------------------ Sort (cost=406880.90..413097.68 rows=2486710 width=21)... Sort Key: total_amount Sort Method: external merge Disk: 78176kB Buffers: shared read=15856, temp read=19539 written=19578 -> Seq Scan on bookings (cost=0.00..40723.10 rows=24... Buffers: shared read=15856 Planning: Buffers: shared hit=34 read=2 dirtied=1 (9 rows) ``` `Sort Method: external merge` tells us that the sort spilled to disk. The `Disk` value reports the temporary disk space used by the sort, while the temp buffer counters show temporary I/O. ### Incremental Sort {#qpt-p74-incremental-sort} Suppose a query requires ordering by \\(K_1,\ldots,K_m,\ldots,K_n\\) keys, but its input is already ordered by the first m keys. There is no need to sort the entire data set again. PostgreSQL can divide the input into consecutive groups that have equal values of the presorted prefix \\(K_1,\ldots,K_m\\) and sort those groups only by the remaining keys \\(K_{m+1},\ldots,K_n\\). This is **incremental sort**. Incremental sort can reduce memory requirements and the likelihood of spilling to disk because each sort works on a smaller portion of the input. It also has a latency advantage: PostgreSQL can begin returning rows after the first group has been sorted instead of waiting for the entire input to be sorted. ![Incremental sorting of pre-sorted groups and full-sort groups.](/images/qpt/p075-incremental-sort.svg) {#qpt-fig-4-3 num="4.3" caption="Incremental Sort" .book-original-figure .d-flex .flex-column .align-items-center width=422 height=244} The trade-off is additional overhead from identifying and processing many groups. PostgreSQL uses two strategies internally. Larger groups that share the same presorted prefix can be sorted individually. Small groups can be accumulated and fully sorted together to avoid excessive per-group overhead. Incremental sort can be disabled with `enable_incremental_sort`. Create an index on `bookings.total_amount`: ```sql CREATE INDEX ON bookings(total_amount); ``` Now increase `work_mem` and sort by `total_amount` and `book_date`: ```sql SET work_mem = '8 MB'; EXPLAIN (analyze, costs off, timing off, buffers off) SELECT * FROM bookings ORDER BY total_amount, book_date; ``` ```text QUERY PLAN ------------------------------------------------------------ Incremental Sort (actual rows=2486710.00 loops=1) Sort Key: total_amount, book_date Presorted Key: total_amount Full-sort Groups: 3132 Sort Method: quicksort Average Memory: 27kB Peak Memory: 27kB Pre-sorted Groups: 2449 Sort Method: quicksort Average Memory: 6442kB Peak Memory: 6464kB -> Index Scan using bookings_total_amount_idx on book... Index Searches: 1 Planning Time: 0.128 ms Execution Time: 934.215 ms (11 rows) ``` The index scan already provides rows ordered by `total_amount`, shown as `Presorted Key`. `Incremental Sort` only has to establish the remaining order by `book_date`. `Pre-sorted Groups` describes the larger groups that were processed using the existing `total_amount` order and sorted further by `book_date`. `Full-sort Groups` describes small groups that were combined and sorted as complete groups. In this example both groups fit entirely in memory and were quicksorted. Now reduce `work_mem`: ```sql SET work_mem = '128 kB'; ``` Run the query again: ```sql EXPLAIN (analyze, costs off, timing off, buffers off) SELECT * FROM bookings ORDER BY total_amount, book_date; ``` ```text QUERY PLAN ------------------------------------------------------------ Incremental Sort (actual rows=2486710.00 loops=1) Sort Key: total_amount, book_date Presorted Key: total_amount Full-sort Groups: 3132 Sort Method: quicksort Average Memory: 27kB Peak Memory: 27kB Pre-sorted Groups: 2449 Sort Method: external merge Average Disk: 2662kB Peak Disk: 2672kB -> Index Scan using bookings_total_amount_idx on book... Index Searches: 1 Planning Time: 0.044 ms Execution Time: 912.199 ms (11 rows) ``` With less memory, the large presorted groups are now handled with external merge, and `EXPLAIN` reports their temporary disk usage explicitly. Restore the setting and remove the demonstration index: ```text RESET work_mem; DROP INDEX bookings_total_amount_idx; ``` ### Building a B-tree {#qpt-p77-building-a-b-tree} PostgreSQL could in principle build a B-tree index by starting with an empty tree and inserting entries one by one as it scans the table. For a bulk index build, that would be inefficient. Instead, PostgreSQL forms the index entries, sorts them by index key, fills the leaf level in order, and then builds the upper levels until only the root remains. The sorting machinery is closely related to the sorting discussed above, but index creation uses `maintenance_work_mem` rather than ordinary `work_mem`. Maintenance operations are relatively infrequent, so it is often reasonable to give them a larger memory budget. B-tree index construction can also run in parallel. The number of workers is chosen in the same way as for parallel queries, depending on the table size, but is limited by `max_parallel_maintenance_workers`. For parallel index builds, `maintenance_work_mem` applies to the build as a whole rather than separately to every worker. ## 2. Grouping {#qpt-section-4-2} ### Where Grouping Appears {#qpt-p78-where-grouping-appears} SQL can divide rows into groups with `GROUP BY`. Aggregate functions are commonly used with those groups to compute one result per group. Window functions have a related concept through `PARTITION BY`, but unlike ordinary grouping, window functions do not collapse the rows of a partition into one result row. Grouping also appears implicitly when duplicates must be removed, for example with: `DISTINCT`; `UNION` without `ALL`; `INTERSECT` without `ALL`; `EXCEPT` without `ALL`. PostgreSQL can use different physical strategies for grouping and duplicate elimination. Two important ones are hashing and processing data in group-key order. The planner chooses among available alternatives based on estimated costs, memory, ordering already available from lower plan nodes, and other properties of the query. ### Hash Aggregation {#qpt-p79-hash-aggregation} A hash table uses a hash function to map values into a finite set of buckets. For a lookup: 1. Compute the hash value. 2. Use part of that value to choose a bucket. 3. Inspect entries in the bucket and use equality comparison to distinguish values whose hashes or bucket assignments collide. With a reasonable load factor and a good distribution, lookup is expected to take approximately constant time. A poor distribution or an overloaded hash table increases collision work. ![Hash buckets and counters for SELECT year, count(*) cnt FROM t GROUP BY year; with the original album rows.](/images/qpt/p079-hash-aggregation.svg) {#qpt-fig-4-4 num="4.4" caption="Hash Aggregation" .book-original-figure .d-flex .flex-column .align-items-center width=394 height=244} The plan node for hash-based aggregation is `HashAggregate`: ```sql EXPLAIN SELECT airplane_code, count(*) FROM seats GROUP BY airplane_code; QUERY PLAN ------------------------------------------------------------ HashAggregate (cost=36.12..36.20 rows=8 width=12) Group Key: airplane_code -> Seq Scan on seats (cost=0.00..27.41 rows=1741 wid... (3 rows) ``` The startup cost is significant because `HashAggregate` has to consume its input and build aggregation state before it can produce the final groups. `EXPLAIN ANALYZE` shows memory use: ```sql EXPLAIN (analyze, timing off, costs off, buffers off) SELECT airplane_code, count(*) FROM seats GROUP BY airplane_code; QUERY PLAN ------------------------------------------------------ HashAggregate (actual rows=8.00 loops=1) Group Key: airplane_code Batches: 1 Memory Usage: 32kB -> Seq Scan on seats (actual rows=1741.00 loops=1) Planning Time: 0.021 ms Execution Time: 0.424 ms (6 rows) ``` ### Grouping Sorted Data {#qpt-p80-grouping-sorted-data} Duplicate elimination and grouping can also exploit rows that arrive ordered by the grouping keys. ![Unique and GroupAggregate process the same sorted album rows, with the original SELECT statements.](/images/qpt/p081-grouping-sorted.svg) {#qpt-fig-4-5 num="4.5" caption="Grouping Sorted Data" .book-original-figure .d-flex .flex-column .align-items-center width=403 height=241} `Unique` removes adjacent duplicates. Because equal keys are next to one another, it only needs to compare the current value with the previous one. The `GroupAggregate` node returns aggregated data. In the example in the figure, the node builds a list of distinct values of the `year` field and counts how many times each value occurs in the data set. When the input already has the required order, `Unique` or `GroupAggregate` can be attractive because they need relatively little working memory and can process the stream incrementally. When the input must first be fully sorted, hash aggregation can often be cheaper, although the planner decides from the actual estimates rather than from a fixed rule. These nodes preserve group-key ordering, which can sometimes satisfy a later `ORDER BY` without another sort. Here is a `GroupAggregate` whose input order comes directly from an index: ```sql EXPLAIN (costs off) SELECT ticket_no, count(ticket_no) FROM segments GROUP BY ticket_no; QUERY PLAN ------------------------------------------------------ GroupAggregate Group Key: ticket_no -> Index Only Scan using segments_pkey on segments (3 rows) ``` A `DISTINCT` query can use `Unique`: ```sql EXPLAIN (costs off) SELECT DISTINCT ticket_no FROM segments ORDER BY ticket_no; QUERY PLAN ------------------------------------------------------ Unique -> Index Only Scan using segments_pkey on segments (2 rows) ``` The index already produces `ticket_no` in the order required by `ORDER BY`, and `Unique` preserves that order, so no additional `Sort` node is necessary. ### Window Functions {#qpt-p82-window-functions} Unlike ordinary aggregate functions, window functions compute a value for each output row rather than reducing a group to one row. After the function name, the `OVER` clause specifies a **window**: a rule that determines, for each result row, which set of rows the window function should process. Such a set is called a **frame**. ![The complete partition frame for OVER () compared with the growing frame for OVER (ORDER BY).](/images/qpt/p083-window-frames.svg) {#qpt-fig-4-6 num="4.6" caption="Window Frames with and without Ordering" .book-original-figure .d-flex .flex-column .align-items-center width=338 height=215} With `OVER ()`, there is no `PARTITION BY` and no `ORDER BY`. There is therefore one partition containing all rows, and the default frame is the entire partition. If the window definition contains an `ORDER BY` clause that orders the rows, the default window frame covers rows from the first row through the current row. Consider a running sum of booking amounts: ```sql EXPLAIN SELECT *, sum(total_amount) OVER (ORDER BY book_date) FROM bookings; QUERY PLAN ------------------------------------------------------------ WindowAgg (cost=406880.92..450398.33 rows=2486710 widt... Window: w1 AS (ORDER BY book_date) -> Sort (cost=406880.90..413097.68 rows=2486710 widt... Sort Key: book_date -> Seq Scan on bookings (cost=0.00..40723.10 row... (5 rows) ``` The window function is evaluated by `WindowAgg`. Here its child `Sort` establishes the order required by the window. The sort can use any suitable sort strategy. A small input can stay in memory: ```sql EXPLAIN (analyze, timing off, summary off, buffers off) SELECT *, count(*) OVER (ORDER BY seat_no) FROM seats; QUERY PLAN ------------------------------------------------------------ WindowAgg (cost=121.18..151.59 rows=1741 width=23) (ac... Window: w1 AS (ORDER BY seat_no) Storage: Memory Maximum Storage: 17kB -> Sort (cost=121.13..125.48 rows=1741 width=15) (ac... Sort Key: seat_no Sort Method: quicksort Memory: 103kB -> Seq Scan on seats (cost=0.00..27.41 rows=1741... (7 rows) ``` A large input may require an external sort: ```sql EXPLAIN (analyze, timing off, summary off, buffers off) SELECT *, sum(total_amount) OVER (ORDER BY book_date) FROM bookings; QUERY PLAN ------------------------------------------------------------ WindowAgg (cost=406880.92..450398.33 rows=2486710 widt... Window: w1 AS (ORDER BY book_date) Storage: Memory Maximum Storage: 17kB -> Sort (cost=406880.90..413097.68 rows=2486710 widt... Sort Key: book_date Sort Method: external merge Disk: 75760kB -> Seq Scan on bookings (cost=0.00..40723.10 row... (7 rows) ``` For nodes that use internal row storage, such as `WindowAgg`, `CTE Scan`, or `Recursive Union`, the `Storage` line shows the maximum amount of storage used and its type: `Memory` when the data fits in memory, or `Disk` when temporary files are used. ![Window frames within PARTITION BY groups, without and with ORDER BY.](/images/qpt/p085-partition-frames.svg) {#qpt-fig-4-7 num="4.7" caption="Window Frames within Partitions" .book-original-figure .d-flex .flex-column .align-items-center width=418 height=214} `PARTITION BY` divides the input into independent groups of rows. For each group, the frame boundaries change within that group. Unless specified otherwise, the frame occupies the entire group. If the window definition also contains `ORDER BY`, the rows are processed in the corresponding order. In this case, the frame covers the rows from the first to the current one. Unlike regular `GROUP BY`, `PARTITION BY` always employs sorting: the plan is chosen so that the `WindowAgg` node receives a set of rows sorted first by the `PARTITION BY` keys and then by the `ORDER BY` keys. Hashing is not used even when there is no `ORDER BY` clause.