| blob | 545e301e4827298308adc3e90f5ea63ec714cf13 |
1 -- When we have to sort the entire table, incremental sort will
2 -- be slower than plain sort, so it should not be used.
3 explain (costs off)
4 select * from (select * from tenk1 order by four) t order by four, ten;
5 QUERY PLAN
6 -----------------------------------
7 Sort
8 Sort Key: tenk1.four, tenk1.ten
9 -> Sort
10 Sort Key: tenk1.four
11 -> Seq Scan on tenk1
12 (5 rows)
14 -- When there is a LIMIT clause, incremental sort is beneficial because
15 -- it only has to sort some of the groups, and not the entire table.
16 explain (costs off)
17 select * from (select * from tenk1 order by four) t order by four, ten
18 limit 1;
19 QUERY PLAN
20 -----------------------------------------
21 Limit
22 -> Incremental Sort
23 Sort Key: tenk1.four, tenk1.ten
24 Presorted Key: tenk1.four
25 -> Sort
26 Sort Key: tenk1.four
27 -> Seq Scan on tenk1
28 (7 rows)
30 -- When work_mem is not enough to sort the entire table, incremental sort
31 -- may be faster if individual groups still fit into work_mem.
32 set work_mem to '2MB';
33 explain (costs off)
34 select * from (select * from tenk1 order by four) t order by four, ten;
35 QUERY PLAN
36 -----------------------------------
37 Incremental Sort
38 Sort Key: tenk1.four, tenk1.ten
39 Presorted Key: tenk1.four
40 -> Sort
41 Sort Key: tenk1.four
42 -> Seq Scan on tenk1
43 (6 rows)
45 reset work_mem;
46 create table t(a integer, b integer);
47 create or replace function explain_analyze_without_memory(query text)
48 returns table (out_line text) language plpgsql
49 as
50 $$
51 declare
52 line text;
53 begin
54 for line in
55 execute 'explain (analyze, costs off, summary off, timing off) ' || query
56 loop
57 out_line := regexp_replace(line, '\d+kB', 'NNkB', 'g');
58 return next;
59 end loop;
60 end;
61 $$;
62 create or replace function explain_analyze_inc_sort_nodes(query text)
63 returns jsonb language plpgsql
64 as
65 $$
66 declare
67 elements jsonb;
68 element jsonb;
69 matching_nodes jsonb := '[]'::jsonb;
70 begin
71 execute 'explain (analyze, costs off, summary off, timing off, format ''json'') ' || query into strict elements;
72 while jsonb_array_length(elements) > 0 loop
73 element := elements->0;
74 elements := elements - 0;
75 case jsonb_typeof(element)
76 when 'array' then
77 if jsonb_array_length(element) > 0 then
78 elements := elements || element;
79 end if;
80 when 'object' then
81 if element ? 'Plan' then
82 elements := elements || jsonb_build_array(element->'Plan');
83 element := element - 'Plan';
84 else
85 if element ? 'Plans' then
86 elements := elements || jsonb_build_array(element->'Plans');
87 element := element - 'Plans';
88 end if;
89 if (element->>'Node Type')::text = 'Incremental Sort' then
90 matching_nodes := matching_nodes || element;
91 end if;
92 end if;
93 end case;
94 end loop;
95 return matching_nodes;
96 end;
97 $$;
98 create or replace function explain_analyze_inc_sort_nodes_without_memory(query text)
99 returns jsonb language plpgsql
100 as
101 $$
102 declare
103 nodes jsonb := '[]'::jsonb;
104 node jsonb;
105 group_key text;
106 space_key text;
107 begin
108 for node in select * from jsonb_array_elements(explain_analyze_inc_sort_nodes(query)) t loop
109 for group_key in select unnest(array['Full-sort Groups', 'Pre-sorted Groups']::text[]) t loop
110 for space_key in select unnest(array['Sort Space Memory', 'Sort Space Disk']::text[]) t loop
111 node := jsonb_set(node, array[group_key, space_key, 'Average Sort Space Used'], '"NN"', false);
112 node := jsonb_set(node, array[group_key, space_key, 'Peak Sort Space Used'], '"NN"', false);
113 end loop;
114 end loop;
115 nodes := nodes || node;
116 end loop;
117 return nodes;
118 end;
119 $$;
120 create or replace function explain_analyze_inc_sort_nodes_verify_invariants(query text)
121 returns bool language plpgsql
122 as
123 $$
124 declare
125 node jsonb;
126 group_stats jsonb;
127 group_key text;
128 space_key text;
129 begin
130 for node in select * from jsonb_array_elements(explain_analyze_inc_sort_nodes(query)) t loop
131 for group_key in select unnest(array['Full-sort Groups', 'Pre-sorted Groups']::text[]) t loop
132 group_stats := node->group_key;
133 for space_key in select unnest(array['Sort Space Memory', 'Sort Space Disk']::text[]) t loop
134 if (group_stats->space_key->'Peak Sort Space Used')::bigint < (group_stats->space_key->'Peak Sort Space Used')::bigint then
135 raise exception '% has invalid max space < average space', group_key;
136 end if;
137 end loop;
138 end loop;
139 end loop;
140 return true;
141 end;
142 $$;
143 -- A single large group tested around each mode transition point.
144 insert into t(a, b) select i/100 + 1, i + 1 from generate_series(0, 999) n(i);
145 analyze t;
146 explain (costs off) select * from (select * from t order by a) s order by a, b limit 31;
147 QUERY PLAN
148 ---------------------------------
149 Limit
150 -> Incremental Sort
151 Sort Key: t.a, t.b
152 Presorted Key: t.a
153 -> Sort
154 Sort Key: t.a
155 -> Seq Scan on t
156 (7 rows)
158 select * from (select * from t order by a) s order by a, b limit 31;
159 a | b
160 ---+----
161 1 | 1
162 1 | 2
163 1 | 3
164 1 | 4
165 1 | 5
166 1 | 6
167 1 | 7
168 1 | 8
169 1 | 9
170 1 | 10
171 1 | 11
172 1 | 12
173 1 | 13
174 1 | 14
175 1 | 15
176 1 | 16
177 1 | 17
178 1 | 18
179 1 | 19
180 1 | 20
181 1 | 21
182 1 | 22
183 1 | 23
184 1 | 24
185 1 | 25
186 1 | 26
187 1 | 27
188 1 | 28
189 1 | 29
190 1 | 30
191 1 | 31
192 (31 rows)
194 explain (costs off) select * from (select * from t order by a) s order by a, b limit 32;
195 QUERY PLAN
196 ---------------------------------
197 Limit
198 -> Incremental Sort
199 Sort Key: t.a, t.b
200 Presorted Key: t.a
201 -> Sort
202 Sort Key: t.a
203 -> Seq Scan on t
204 (7 rows)
206 select * from (select * from t order by a) s order by a, b limit 32;
207 a | b
208 ---+----
209 1 | 1
210 1 | 2
211 1 | 3
212 1 | 4
213 1 | 5
214 1 | 6
215 1 | 7
216 1 | 8
217 1 | 9
218 1 | 10
219 1 | 11
220 1 | 12
221 1 | 13
222 1 | 14
223 1 | 15
224 1 | 16
225 1 | 17
226 1 | 18
227 1 | 19
228 1 | 20
229 1 | 21
230 1 | 22
231 1 | 23
232 1 | 24
233 1 | 25
234 1 | 26
235 1 | 27
236 1 | 28
237 1 | 29
238 1 | 30
239 1 | 31
240 1 | 32
241 (32 rows)
243 explain (costs off) select * from (select * from t order by a) s order by a, b limit 33;
244 QUERY PLAN
245 ---------------------------------
246 Limit
247 -> Incremental Sort
248 Sort Key: t.a, t.b
249 Presorted Key: t.a
250 -> Sort
251 Sort Key: t.a
252 -> Seq Scan on t
253 (7 rows)
255 select * from (select * from t order by a) s order by a, b limit 33;
256 a | b
257 ---+----
258 1 | 1
259 1 | 2
260 1 | 3
261 1 | 4
262 1 | 5
263 1 | 6
264 1 | 7
265 1 | 8
266 1 | 9
267 1 | 10
268 1 | 11
269 1 | 12
270 1 | 13
271 1 | 14
272 1 | 15
273 1 | 16
274 1 | 17
275 1 | 18
276 1 | 19
277 1 | 20
278 1 | 21
279 1 | 22
280 1 | 23
281 1 | 24
282 1 | 25
283 1 | 26
284 1 | 27
285 1 | 28
286 1 | 29
287 1 | 30
288 1 | 31
289 1 | 32
290 1 | 33
291 (33 rows)
293 explain (costs off) select * from (select * from t order by a) s order by a, b limit 65;
294 QUERY PLAN
295 ---------------------------------
296 Limit
297 -> Incremental Sort
298 Sort Key: t.a, t.b
299 Presorted Key: t.a
300 -> Sort
301 Sort Key: t.a
302 -> Seq Scan on t
303 (7 rows)
305 select * from (select * from t order by a) s order by a, b limit 65;
306 a | b
307 ---+----
308 1 | 1
309 1 | 2
310 1 | 3
311 1 | 4
312 1 | 5
313 1 | 6
314 1 | 7
315 1 | 8
316 1 | 9
317 1 | 10
318 1 | 11
319 1 | 12
320 1 | 13
321 1 | 14
322 1 | 15
323 1 | 16
324 1 | 17
325 1 | 18
326 1 | 19
327 1 | 20
328 1 | 21
329 1 | 22
330 1 | 23
331 1 | 24
332 1 | 25
333 1 | 26
334 1 | 27
335 1 | 28
336 1 | 29
337 1 | 30
338 1 | 31
339 1 | 32
340 1 | 33
341 1 | 34
342 1 | 35
343 1 | 36
344 1 | 37
345 1 | 38
346 1 | 39
347 1 | 40
348 1 | 41
349 1 | 42
350 1 | 43
351 1 | 44
352 1 | 45
353 1 | 46
354 1 | 47
355 1 | 48
356 1 | 49
357 1 | 50
358 1 | 51
359 1 | 52
360 1 | 53
361 1 | 54
362 1 | 55
363 1 | 56
364 1 | 57
365 1 | 58
366 1 | 59
367 1 | 60
368 1 | 61
369 1 | 62
370 1 | 63
371 1 | 64
372 1 | 65
373 (65 rows)
375 explain (costs off) select * from (select * from t order by a) s order by a, b limit 66;
376 QUERY PLAN
377 ---------------------------------
378 Limit
379 -> Incremental Sort
380 Sort Key: t.a, t.b
381 Presorted Key: t.a
382 -> Sort
383 Sort Key: t.a
384 -> Seq Scan on t
385 (7 rows)
387 select * from (select * from t order by a) s order by a, b limit 66;
388 a | b
389 ---+----
390 1 | 1
391 1 | 2
392 1 | 3
393 1 | 4
394 1 | 5
395 1 | 6
396 1 | 7
397 1 | 8
398 1 | 9
399 1 | 10
400 1 | 11
401 1 | 12
402 1 | 13
403 1 | 14
404 1 | 15
405 1 | 16
406 1 | 17
407 1 | 18
408 1 | 19
409 1 | 20
410 1 | 21
411 1 | 22
412 1 | 23
413 1 | 24
414 1 | 25
415 1 | 26
416 1 | 27
417 1 | 28
418 1 | 29
419 1 | 30
420 1 | 31
421 1 | 32
422 1 | 33
423 1 | 34
424 1 | 35
425 1 | 36
426 1 | 37
427 1 | 38
428 1 | 39
429 1 | 40
430 1 | 41
431 1 | 42
432 1 | 43
433 1 | 44
434 1 | 45
435 1 | 46
436 1 | 47
437 1 | 48
438 1 | 49
439 1 | 50
440 1 | 51
441 1 | 52
442 1 | 53
443 1 | 54
444 1 | 55
445 1 | 56
446 1 | 57
447 1 | 58
448 1 | 59
449 1 | 60
450 1 | 61
451 1 | 62
452 1 | 63
453 1 | 64
454 1 | 65
455 1 | 66
456 (66 rows)
458 delete from t;
459 -- An initial large group followed by a small group.
460 insert into t(a, b) select i/50 + 1, i + 1 from generate_series(0, 999) n(i);
461 analyze t;
462 explain (costs off) select * from (select * from t order by a) s order by a, b limit 55;
463 QUERY PLAN
464 ---------------------------------
465 Limit
466 -> Incremental Sort
467 Sort Key: t.a, t.b
468 Presorted Key: t.a
469 -> Sort
470 Sort Key: t.a
471 -> Seq Scan on t
472 (7 rows)
474 select * from (select * from t order by a) s order by a, b limit 55;
475 a | b
476 ---+----
477 1 | 1
478 1 | 2
479 1 | 3
480 1 | 4
481 1 | 5
482 1 | 6
483 1 | 7
484 1 | 8
485 1 | 9
486 1 | 10
487 1 | 11
488 1 | 12
489 1 | 13
490 1 | 14
491 1 | 15
492 1 | 16
493 1 | 17
494 1 | 18
495 1 | 19
496 1 | 20
497 1 | 21
498 1 | 22
499 1 | 23
500 1 | 24
501 1 | 25
502 1 | 26
503 1 | 27
504 1 | 28
505 1 | 29
506 1 | 30
507 1 | 31
508 1 | 32
509 1 | 33
510 1 | 34
511 1 | 35
512 1 | 36
513 1 | 37
514 1 | 38
515 1 | 39
516 1 | 40
517 1 | 41
518 1 | 42
519 1 | 43
520 1 | 44
521 1 | 45
522 1 | 46
523 1 | 47
524 1 | 48
525 1 | 49
526 1 | 50
527 2 | 51
528 2 | 52
529 2 | 53
530 2 | 54
531 2 | 55
532 (55 rows)
534 -- Test EXPLAIN ANALYZE with only a fullsort group.
535 select explain_analyze_without_memory('select * from (select * from t order by a) s order by a, b limit 55');
536 explain_analyze_without_memory
537 ---------------------------------------------------------------------------------------------------------------
538 Limit (actual rows=55 loops=1)
539 -> Incremental Sort (actual rows=55 loops=1)
540 Sort Key: t.a, t.b
541 Presorted Key: t.a
542 Full-sort Groups: 2 Sort Methods: top-N heapsort, quicksort Average Memory: NNkB Peak Memory: NNkB
543 -> Sort (actual rows=101 loops=1)
544 Sort Key: t.a
545 Sort Method: quicksort Memory: NNkB
546 -> Seq Scan on t (actual rows=1000 loops=1)
547 (9 rows)
549 select jsonb_pretty(explain_analyze_inc_sort_nodes_without_memory('select * from (select * from t order by a) s order by a, b limit 55'));
550 jsonb_pretty
551 -------------------------------------------------
552 [ +
553 { +
554 "Sort Key": [ +
555 "t.a", +
556 "t.b" +
557 ], +
558 "Node Type": "Incremental Sort", +
559 "Actual Rows": 55, +
560 "Actual Loops": 1, +
561 "Async Capable": false, +
562 "Presorted Key": [ +
563 "t.a" +
564 ], +
565 "Parallel Aware": false, +
566 "Full-sort Groups": { +
567 "Group Count": 2, +
568 "Sort Methods Used": [ +
569 "top-N heapsort", +
570 "quicksort" +
571 ], +
572 "Sort Space Memory": { +
573 "Peak Sort Space Used": "NN", +
574 "Average Sort Space Used": "NN"+
575 } +
576 }, +
577 "Parent Relationship": "Outer" +
578 } +
579 ]
580 (1 row)
582 select explain_analyze_inc_sort_nodes_verify_invariants('select * from (select * from t order by a) s order by a, b limit 55');
583 explain_analyze_inc_sort_nodes_verify_invariants
584 --------------------------------------------------
585 t
586 (1 row)
588 delete from t;
589 -- An initial small group followed by a large group.
590 insert into t(a, b) select (case when i < 5 then i else 9 end), i from generate_series(1, 1000) n(i);
591 analyze t;
592 explain (costs off) select * from (select * from t order by a) s order by a, b limit 70;
593 QUERY PLAN
594 ---------------------------------
595 Limit
596 -> Incremental Sort
597 Sort Key: t.a, t.b
598 Presorted Key: t.a
599 -> Sort
600 Sort Key: t.a
601 -> Seq Scan on t
602 (7 rows)
604 select * from (select * from t order by a) s order by a, b limit 70;
605 a | b
606 ---+----
607 1 | 1
608 2 | 2
609 3 | 3
610 4 | 4
611 9 | 5
612 9 | 6
613 9 | 7
614 9 | 8
615 9 | 9
616 9 | 10
617 9 | 11
618 9 | 12
619 9 | 13
620 9 | 14
621 9 | 15
622 9 | 16
623 9 | 17
624 9 | 18
625 9 | 19
626 9 | 20
627 9 | 21
628 9 | 22
629 9 | 23
630 9 | 24
631 9 | 25
632 9 | 26
633 9 | 27
634 9 | 28
635 9 | 29
636 9 | 30
637 9 | 31
638 9 | 32
639 9 | 33
640 9 | 34
641 9 | 35
642 9 | 36
643 9 | 37
644 9 | 38
645 9 | 39
646 9 | 40
647 9 | 41
648 9 | 42
649 9 | 43
650 9 | 44
651 9 | 45
652 9 | 46
653 9 | 47
654 9 | 48
655 9 | 49
656 9 | 50
657 9 | 51
658 9 | 52
659 9 | 53
660 9 | 54
661 9 | 55
662 9 | 56
663 9 | 57
664 9 | 58
665 9 | 59
666 9 | 60
667 9 | 61
668 9 | 62
669 9 | 63
670 9 | 64
671 9 | 65
672 9 | 66
673 9 | 67
674 9 | 68
675 9 | 69
676 9 | 70
677 (70 rows)
679 -- Checks case where we hit a group boundary at the last tuple of a batch.
680 -- Because the full sort state is bounded, we scan 64 tuples (the mode
681 -- transition point) but only retain 5. Thus when we transition modes, all
682 -- tuples in the full sort state have different prefix keys.
683 explain (costs off) select * from (select * from t order by a) s order by a, b limit 5;
684 QUERY PLAN
685 ---------------------------------
686 Limit
687 -> Incremental Sort
688 Sort Key: t.a, t.b
689 Presorted Key: t.a
690 -> Sort
691 Sort Key: t.a
692 -> Seq Scan on t
693 (7 rows)
695 select * from (select * from t order by a) s order by a, b limit 5;
696 a | b
697 ---+---
698 1 | 1
699 2 | 2
700 3 | 3
701 4 | 4
702 9 | 5
703 (5 rows)
705 -- Test rescan.
706 begin;
707 -- We force the planner to choose a plan with incremental sort on the right side
708 -- of a nested loop join node. That way we trigger the rescan code path.
709 set local enable_hashjoin = off;
710 set local enable_mergejoin = off;
711 set local enable_material = off;
712 set local enable_sort = off;
713 explain (costs off) select * from t left join (select * from (select * from t order by a) v order by a, b) s on s.a = t.a where t.a in (1, 2);
714 QUERY PLAN
715 ------------------------------------------------
716 Nested Loop Left Join
717 Join Filter: (t_1.a = t.a)
718 -> Seq Scan on t
719 Filter: (a = ANY ('{1,2}'::integer[]))
720 -> Incremental Sort
721 Sort Key: t_1.a, t_1.b
722 Presorted Key: t_1.a
723 -> Sort
724 Sort Key: t_1.a
725 -> Seq Scan on t t_1
726 (10 rows)
728 select * from t left join (select * from (select * from t order by a) v order by a, b) s on s.a = t.a where t.a in (1, 2);
729 a | b | a | b
730 ---+---+---+---
731 1 | 1 | 1 | 1
732 2 | 2 | 2 | 2
733 (2 rows)
735 rollback;
736 -- Test EXPLAIN ANALYZE with both fullsort and presorted groups.
737 select explain_analyze_without_memory('select * from (select * from t order by a) s order by a, b limit 70');
738 explain_analyze_without_memory
739 ----------------------------------------------------------------------------------------------------------------
740 Limit (actual rows=70 loops=1)
741 -> Incremental Sort (actual rows=70 loops=1)
742 Sort Key: t.a, t.b
743 Presorted Key: t.a
744 Full-sort Groups: 1 Sort Method: quicksort Average Memory: NNkB Peak Memory: NNkB
745 Pre-sorted Groups: 5 Sort Methods: top-N heapsort, quicksort Average Memory: NNkB Peak Memory: NNkB
746 -> Sort (actual rows=1000 loops=1)
747 Sort Key: t.a
748 Sort Method: quicksort Memory: NNkB
749 -> Seq Scan on t (actual rows=1000 loops=1)
750 (10 rows)
752 select jsonb_pretty(explain_analyze_inc_sort_nodes_without_memory('select * from (select * from t order by a) s order by a, b limit 70'));
753 jsonb_pretty
754 -------------------------------------------------
755 [ +
756 { +
757 "Sort Key": [ +
758 "t.a", +
759 "t.b" +
760 ], +
761 "Node Type": "Incremental Sort", +
762 "Actual Rows": 70, +
763 "Actual Loops": 1, +
764 "Async Capable": false, +
765 "Presorted Key": [ +
766 "t.a" +
767 ], +
768 "Parallel Aware": false, +
769 "Full-sort Groups": { +
770 "Group Count": 1, +
771 "Sort Methods Used": [ +
772 "quicksort" +
773 ], +
774 "Sort Space Memory": { +
775 "Peak Sort Space Used": "NN", +
776 "Average Sort Space Used": "NN"+
777 } +
778 }, +
779 "Pre-sorted Groups": { +
780 "Group Count": 5, +
781 "Sort Methods Used": [ +
782 "top-N heapsort", +
783 "quicksort" +
784 ], +
785 "Sort Space Memory": { +
786 "Peak Sort Space Used": "NN", +
787 "Average Sort Space Used": "NN"+
788 } +
789 }, +
790 "Parent Relationship": "Outer" +
791 } +
792 ]
793 (1 row)
795 select explain_analyze_inc_sort_nodes_verify_invariants('select * from (select * from t order by a) s order by a, b limit 70');
796 explain_analyze_inc_sort_nodes_verify_invariants
797 --------------------------------------------------
798 t
799 (1 row)
801 delete from t;
802 -- Small groups of 10 tuples each tested around each mode transition point.
803 insert into t(a, b) select i / 10, i from generate_series(1, 1000) n(i);
804 analyze t;
805 explain (costs off) select * from (select * from t order by a) s order by a, b limit 31;
806 QUERY PLAN
807 ---------------------------------
808 Limit
809 -> Incremental Sort
810 Sort Key: t.a, t.b
811 Presorted Key: t.a
812 -> Sort
813 Sort Key: t.a
814 -> Seq Scan on t
815 (7 rows)
817 select * from (select * from t order by a) s order by a, b limit 31;
818 a | b
819 ---+----
820 0 | 1
821 0 | 2
822 0 | 3
823 0 | 4
824 0 | 5
825 0 | 6
826 0 | 7
827 0 | 8
828 0 | 9
829 1 | 10
830 1 | 11
831 1 | 12
832 1 | 13
833 1 | 14
834 1 | 15
835 1 | 16
836 1 | 17
837 1 | 18
838 1 | 19
839 2 | 20
840 2 | 21
841 2 | 22
842 2 | 23
843 2 | 24
844 2 | 25
845 2 | 26
846 2 | 27
847 2 | 28
848 2 | 29
849 3 | 30
850 3 | 31
851 (31 rows)
853 explain (costs off) select * from (select * from t order by a) s order by a, b limit 32;
854 QUERY PLAN
855 ---------------------------------
856 Limit
857 -> Incremental Sort
858 Sort Key: t.a, t.b
859 Presorted Key: t.a
860 -> Sort
861 Sort Key: t.a
862 -> Seq Scan on t
863 (7 rows)
865 select * from (select * from t order by a) s order by a, b limit 32;
866 a | b
867 ---+----
868 0 | 1
869 0 | 2
870 0 | 3
871 0 | 4
872 0 | 5
873 0 | 6
874 0 | 7
875 0 | 8
876 0 | 9
877 1 | 10
878 1 | 11
879 1 | 12
880 1 | 13
881 1 | 14
882 1 | 15
883 1 | 16
884 1 | 17
885 1 | 18
886 1 | 19
887 2 | 20
888 2 | 21
889 2 | 22
890 2 | 23
891 2 | 24
892 2 | 25
893 2 | 26
894 2 | 27
895 2 | 28
896 2 | 29
897 3 | 30
898 3 | 31
899 3 | 32
900 (32 rows)
902 explain (costs off) select * from (select * from t order by a) s order by a, b limit 33;
903 QUERY PLAN
904 ---------------------------------
905 Limit
906 -> Incremental Sort
907 Sort Key: t.a, t.b
908 Presorted Key: t.a
909 -> Sort
910 Sort Key: t.a
911 -> Seq Scan on t
912 (7 rows)
914 select * from (select * from t order by a) s order by a, b limit 33;
915 a | b
916 ---+----
917 0 | 1
918 0 | 2
919 0 | 3
920 0 | 4
921 0 | 5
922 0 | 6
923 0 | 7
924 0 | 8
925 0 | 9
926 1 | 10
927 1 | 11
928 1 | 12
929 1 | 13
930 1 | 14
931 1 | 15
932 1 | 16
933 1 | 17
934 1 | 18
935 1 | 19
936 2 | 20
937 2 | 21
938 2 | 22
939 2 | 23
940 2 | 24
941 2 | 25
942 2 | 26
943 2 | 27
944 2 | 28
945 2 | 29
946 3 | 30
947 3 | 31
948 3 | 32
949 3 | 33
950 (33 rows)
952 explain (costs off) select * from (select * from t order by a) s order by a, b limit 65;
953 QUERY PLAN
954 ---------------------------------
955 Limit
956 -> Incremental Sort
957 Sort Key: t.a, t.b
958 Presorted Key: t.a
959 -> Sort
960 Sort Key: t.a
961 -> Seq Scan on t
962 (7 rows)
964 select * from (select * from t order by a) s order by a, b limit 65;
965 a | b
966 ---+----
967 0 | 1
968 0 | 2
969 0 | 3
970 0 | 4
971 0 | 5
972 0 | 6
973 0 | 7
974 0 | 8
975 0 | 9
976 1 | 10
977 1 | 11
978 1 | 12
979 1 | 13
980 1 | 14
981 1 | 15
982 1 | 16
983 1 | 17
984 1 | 18
985 1 | 19
986 2 | 20
987 2 | 21
988 2 | 22
989 2 | 23
990 2 | 24
991 2 | 25
992 2 | 26
993 2 | 27
994 2 | 28
995 2 | 29
996 3 | 30
997 3 | 31
998 3 | 32
999 3 | 33
1000 3 | 34
1001 3 | 35
1002 3 | 36
1003 3 | 37
1004 3 | 38
1005 3 | 39
1006 4 | 40
1007 4 | 41
1008 4 | 42
1009 4 | 43
1010 4 | 44
1011 4 | 45
1012 4 | 46
1013 4 | 47
1014 4 | 48
1015 4 | 49
1016 5 | 50
1017 5 | 51
1018 5 | 52
1019 5 | 53
1020 5 | 54
1021 5 | 55
1022 5 | 56
1023 5 | 57
1024 5 | 58
1025 5 | 59
1026 6 | 60
1027 6 | 61
1028 6 | 62
1029 6 | 63
1030 6 | 64
1031 6 | 65
1032 (65 rows)
1034 explain (costs off) select * from (select * from t order by a) s order by a, b limit 66;
1035 QUERY PLAN
1036 ---------------------------------
1037 Limit
1038 -> Incremental Sort
1039 Sort Key: t.a, t.b
1040 Presorted Key: t.a
1041 -> Sort
1042 Sort Key: t.a
1043 -> Seq Scan on t
1044 (7 rows)
1046 select * from (select * from t order by a) s order by a, b limit 66;
1047 a | b
1048 ---+----
1049 0 | 1
1050 0 | 2
1051 0 | 3
1052 0 | 4
1053 0 | 5
1054 0 | 6
1055 0 | 7
1056 0 | 8
1057 0 | 9
1058 1 | 10
1059 1 | 11
1060 1 | 12
1061 1 | 13
1062 1 | 14
1063 1 | 15
1064 1 | 16
1065 1 | 17
1066 1 | 18
1067 1 | 19
1068 2 | 20
1069 2 | 21
1070 2 | 22
1071 2 | 23
1072 2 | 24
1073 2 | 25
1074 2 | 26
1075 2 | 27
1076 2 | 28
1077 2 | 29
1078 3 | 30
1079 3 | 31
1080 3 | 32
1081 3 | 33
1082 3 | 34
1083 3 | 35
1084 3 | 36
1085 3 | 37
1086 3 | 38
1087 3 | 39
1088 4 | 40
1089 4 | 41
1090 4 | 42
1091 4 | 43
1092 4 | 44
1093 4 | 45
1094 4 | 46
1095 4 | 47
1096 4 | 48
1097 4 | 49
1098 5 | 50
1099 5 | 51
1100 5 | 52
1101 5 | 53
1102 5 | 54
1103 5 | 55
1104 5 | 56
1105 5 | 57
1106 5 | 58
1107 5 | 59
1108 6 | 60
1109 6 | 61
1110 6 | 62
1111 6 | 63
1112 6 | 64
1113 6 | 65
1114 6 | 66
1115 (66 rows)
1117 delete from t;
1118 -- Small groups of only 1 tuple each tested around each mode transition point.
1119 insert into t(a, b) select i, i from generate_series(1, 1000) n(i);
1120 analyze t;
1121 explain (costs off) select * from (select * from t order by a) s order by a, b limit 31;
1122 QUERY PLAN
1123 ---------------------------------
1124 Limit
1125 -> Incremental Sort
1126 Sort Key: t.a, t.b
1127 Presorted Key: t.a
1128 -> Sort
1129 Sort Key: t.a
1130 -> Seq Scan on t
1131 (7 rows)
1133 select * from (select * from t order by a) s order by a, b limit 31;
1134 a | b
1135 ----+----
1136 1 | 1
1137 2 | 2
1138 3 | 3
1139 4 | 4
1140 5 | 5
1141 6 | 6
1142 7 | 7
1143 8 | 8
1144 9 | 9
1145 10 | 10
1146 11 | 11
1147 12 | 12
1148 13 | 13
1149 14 | 14
1150 15 | 15
1151 16 | 16
1152 17 | 17
1153 18 | 18
1154 19 | 19
1155 20 | 20
1156 21 | 21
1157 22 | 22
1158 23 | 23
1159 24 | 24
1160 25 | 25
1161 26 | 26
1162 27 | 27
1163 28 | 28
1164 29 | 29
1165 30 | 30
1166 31 | 31
1167 (31 rows)
1169 explain (costs off) select * from (select * from t order by a) s order by a, b limit 32;
1170 QUERY PLAN
1171 ---------------------------------
1172 Limit
1173 -> Incremental Sort
1174 Sort Key: t.a, t.b
1175 Presorted Key: t.a
1176 -> Sort
1177 Sort Key: t.a
1178 -> Seq Scan on t
1179 (7 rows)
1181 select * from (select * from t order by a) s order by a, b limit 32;
1182 a | b
1183 ----+----
1184 1 | 1
1185 2 | 2
1186 3 | 3
1187 4 | 4
1188 5 | 5
1189 6 | 6
1190 7 | 7
1191 8 | 8
1192 9 | 9
1193 10 | 10
1194 11 | 11
1195 12 | 12
1196 13 | 13
1197 14 | 14
1198 15 | 15
1199 16 | 16
1200 17 | 17
1201 18 | 18
1202 19 | 19
1203 20 | 20
1204 21 | 21
1205 22 | 22
1206 23 | 23
1207 24 | 24
1208 25 | 25
1209 26 | 26
1210 27 | 27
1211 28 | 28
1212 29 | 29
1213 30 | 30
1214 31 | 31
1215 32 | 32
1216 (32 rows)
1218 explain (costs off) select * from (select * from t order by a) s order by a, b limit 33;
1219 QUERY PLAN
1220 ---------------------------------
1221 Limit
1222 -> Incremental Sort
1223 Sort Key: t.a, t.b
1224 Presorted Key: t.a
1225 -> Sort
1226 Sort Key: t.a
1227 -> Seq Scan on t
1228 (7 rows)
1230 select * from (select * from t order by a) s order by a, b limit 33;
1231 a | b
1232 ----+----
1233 1 | 1
1234 2 | 2
1235 3 | 3
1236 4 | 4
1237 5 | 5
1238 6 | 6
1239 7 | 7
1240 8 | 8
1241 9 | 9
1242 10 | 10
1243 11 | 11
1244 12 | 12
1245 13 | 13
1246 14 | 14
1247 15 | 15
1248 16 | 16
1249 17 | 17
1250 18 | 18
1251 19 | 19
1252 20 | 20
1253 21 | 21
1254 22 | 22
1255 23 | 23
1256 24 | 24
1257 25 | 25
1258 26 | 26
1259 27 | 27
1260 28 | 28
1261 29 | 29
1262 30 | 30
1263 31 | 31
1264 32 | 32
1265 33 | 33
1266 (33 rows)
1268 explain (costs off) select * from (select * from t order by a) s order by a, b limit 65;
1269 QUERY PLAN
1270 ---------------------------------
1271 Limit
1272 -> Incremental Sort
1273 Sort Key: t.a, t.b
1274 Presorted Key: t.a
1275 -> Sort
1276 Sort Key: t.a
1277 -> Seq Scan on t
1278 (7 rows)
1280 select * from (select * from t order by a) s order by a, b limit 65;
1281 a | b
1282 ----+----
1283 1 | 1
1284 2 | 2
1285 3 | 3
1286 4 | 4
1287 5 | 5
1288 6 | 6
1289 7 | 7
1290 8 | 8
1291 9 | 9
1292 10 | 10
1293 11 | 11
1294 12 | 12
1295 13 | 13
1296 14 | 14
1297 15 | 15
1298 16 | 16
1299 17 | 17
1300 18 | 18
1301 19 | 19
1302 20 | 20
1303 21 | 21
1304 22 | 22
1305 23 | 23
1306 24 | 24
1307 25 | 25
1308 26 | 26
1309 27 | 27
1310 28 | 28
1311 29 | 29
1312 30 | 30
1313 31 | 31
1314 32 | 32
1315 33 | 33
1316 34 | 34
1317 35 | 35
1318 36 | 36
1319 37 | 37
1320 38 | 38
1321 39 | 39
1322 40 | 40
1323 41 | 41
1324 42 | 42
1325 43 | 43
1326 44 | 44
1327 45 | 45
1328 46 | 46
1329 47 | 47
1330 48 | 48
1331 49 | 49
1332 50 | 50
1333 51 | 51
1334 52 | 52
1335 53 | 53
1336 54 | 54
1337 55 | 55
1338 56 | 56
1339 57 | 57
1340 58 | 58
1341 59 | 59
1342 60 | 60
1343 61 | 61
1344 62 | 62
1345 63 | 63
1346 64 | 64
1347 65 | 65
1348 (65 rows)
1350 explain (costs off) select * from (select * from t order by a) s order by a, b limit 66;
1351 QUERY PLAN
1352 ---------------------------------
1353 Limit
1354 -> Incremental Sort
1355 Sort Key: t.a, t.b
1356 Presorted Key: t.a
1357 -> Sort
1358 Sort Key: t.a
1359 -> Seq Scan on t
1360 (7 rows)
1362 select * from (select * from t order by a) s order by a, b limit 66;
1363 a | b
1364 ----+----
1365 1 | 1
1366 2 | 2
1367 3 | 3
1368 4 | 4
1369 5 | 5
1370 6 | 6
1371 7 | 7
1372 8 | 8
1373 9 | 9
1374 10 | 10
1375 11 | 11
1376 12 | 12
1377 13 | 13
1378 14 | 14
1379 15 | 15
1380 16 | 16
1381 17 | 17
1382 18 | 18
1383 19 | 19
1384 20 | 20
1385 21 | 21
1386 22 | 22
1387 23 | 23
1388 24 | 24
1389 25 | 25
1390 26 | 26
1391 27 | 27
1392 28 | 28
1393 29 | 29
1394 30 | 30
1395 31 | 31
1396 32 | 32
1397 33 | 33
1398 34 | 34
1399 35 | 35
1400 36 | 36
1401 37 | 37
1402 38 | 38
1403 39 | 39
1404 40 | 40
1405 41 | 41
1406 42 | 42
1407 43 | 43
1408 44 | 44
1409 45 | 45
1410 46 | 46
1411 47 | 47
1412 48 | 48
1413 49 | 49
1414 50 | 50
1415 51 | 51
1416 52 | 52
1417 53 | 53
1418 54 | 54
1419 55 | 55
1420 56 | 56
1421 57 | 57
1422 58 | 58
1423 59 | 59
1424 60 | 60
1425 61 | 61
1426 62 | 62
1427 63 | 63
1428 64 | 64
1429 65 | 65
1430 66 | 66
1431 (66 rows)
1433 delete from t;
1434 drop table t;
1435 -- Incremental sort vs. parallel queries
1436 set min_parallel_table_scan_size = '1kB';
1437 set min_parallel_index_scan_size = '1kB';
1438 set parallel_setup_cost = 0;
1439 set parallel_tuple_cost = 0;
1440 set max_parallel_workers_per_gather = 2;
1441 create table t (a int, b int, c int);
1442 insert into t select mod(i,10),mod(i,10),i from generate_series(1,10000) s(i);
1443 create index on t (a);
1444 analyze t;
1445 set enable_incremental_sort = off;
1446 explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1;
1447 QUERY PLAN
1448 ------------------------------------------------------
1449 Limit
1450 -> Sort
1451 Sort Key: a, b, (sum(c))
1452 -> Finalize HashAggregate
1453 Group Key: a, b
1454 -> Gather
1455 Workers Planned: 2
1456 -> Partial HashAggregate
1457 Group Key: a, b
1458 -> Parallel Seq Scan on t
1459 (10 rows)
1461 set enable_incremental_sort = on;
1462 explain (costs off) select a,b,sum(c) from t group by 1,2 order by 1,2,3 limit 1;
1463 QUERY PLAN
1464 ----------------------------------------------------------------------
1465 Limit
1466 -> Incremental Sort
1467 Sort Key: a, b, (sum(c))
1468 Presorted Key: a, b
1469 -> GroupAggregate
1470 Group Key: a, b
1471 -> Gather Merge
1472 Workers Planned: 2
1473 -> Incremental Sort
1474 Sort Key: a, b
1475 Presorted Key: a
1476 -> Parallel Index Scan using t_a_idx on t
1477 (12 rows)
1479 -- Incremental sort vs. set operations with varno 0
1480 set enable_hashagg to off;
1481 explain (costs off) select * from t union select * from t order by 1,3;
1482 QUERY PLAN
1483 ----------------------------------------------------------
1484 Incremental Sort
1485 Sort Key: t.a, t.c
1486 Presorted Key: t.a
1487 -> Unique
1488 -> Sort
1489 Sort Key: t.a, t.b, t.c
1490 -> Append
1491 -> Gather
1492 Workers Planned: 2
1493 -> Parallel Seq Scan on t
1494 -> Gather
1495 Workers Planned: 2
1496 -> Parallel Seq Scan on t t_1
1497 (13 rows)
1499 -- Full sort, not just incremental sort can be pushed below a gather merge path
1500 -- by generate_useful_gather_paths.
1501 explain (costs off) select distinct a,b from t;
1502 QUERY PLAN
1503 ------------------------------------------
1504 Unique
1505 -> Gather Merge
1506 Workers Planned: 2
1507 -> Sort
1508 Sort Key: a, b
1509 -> Parallel Seq Scan on t
1510 (6 rows)
1512 drop table t;
1513 -- Sort pushdown can't go below where expressions are part of the rel target.
1514 -- In particular this is interesting for volatile expressions which have to
1515 -- go above joins since otherwise we'll incorrectly use expression evaluations
1516 -- across multiple rows.
1517 set enable_hashagg=off;
1518 set enable_seqscan=off;
1519 set enable_incremental_sort = off;
1520 set parallel_tuple_cost=0;
1521 set parallel_setup_cost=0;
1522 set min_parallel_table_scan_size = 0;
1523 set min_parallel_index_scan_size = 0;
1524 -- Parallel sort below join.
1525 explain (costs off) select distinct sub.unique1, stringu1
1526 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
1527 QUERY PLAN
1528 --------------------------------------------------------------------------
1529 Unique
1530 -> Nested Loop
1531 -> Gather Merge
1532 Workers Planned: 2
1533 -> Sort
1534 Sort Key: tenk1.unique1, tenk1.stringu1
1535 -> Parallel Index Scan using tenk1_unique1 on tenk1
1536 -> Function Scan on generate_series
1537 (8 rows)
1539 explain (costs off) select sub.unique1, stringu1
1540 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
1541 order by 1, 2;
1542 QUERY PLAN
1543 --------------------------------------------------------------------
1544 Nested Loop
1545 -> Gather Merge
1546 Workers Planned: 2
1547 -> Sort
1548 Sort Key: tenk1.unique1, tenk1.stringu1
1549 -> Parallel Index Scan using tenk1_unique1 on tenk1
1550 -> Function Scan on generate_series
1551 (7 rows)
1553 -- Parallel sort but with expression that can be safely generated at the base rel.
1554 explain (costs off) select distinct sub.unique1, md5(stringu1)
1555 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
1556 QUERY PLAN
1557 ----------------------------------------------------------------------------------------
1558 Unique
1559 -> Nested Loop
1560 -> Gather Merge
1561 Workers Planned: 2
1562 -> Sort
1563 Sort Key: tenk1.unique1, (md5((tenk1.stringu1)::text)) COLLATE "C"
1564 -> Parallel Index Scan using tenk1_unique1 on tenk1
1565 -> Function Scan on generate_series
1566 (8 rows)
1568 explain (costs off) select sub.unique1, md5(stringu1)
1569 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
1570 order by 1, 2;
1571 QUERY PLAN
1572 ----------------------------------------------------------------------------------
1573 Nested Loop
1574 -> Gather Merge
1575 Workers Planned: 2
1576 -> Sort
1577 Sort Key: tenk1.unique1, (md5((tenk1.stringu1)::text)) COLLATE "C"
1578 -> Parallel Index Scan using tenk1_unique1 on tenk1
1579 -> Function Scan on generate_series
1580 (7 rows)
1582 -- Parallel sort with an aggregate that can be safely generated in parallel,
1583 -- but we can't sort by partial aggregate values.
1584 explain (costs off) select count(*)
1585 from tenk1 t1
1586 join tenk1 t2 on t1.unique1 = t2.unique2
1587 join tenk1 t3 on t2.unique1 = t3.unique1
1588 order by count(*);
1589 QUERY PLAN
1590 -----------------------------------------------------------------------------------------------
1591 Sort
1592 Sort Key: (count(*))
1593 -> Finalize Aggregate
1594 -> Gather
1595 Workers Planned: 2
1596 -> Partial Aggregate
1597 -> Parallel Hash Join
1598 Hash Cond: (t2.unique1 = t3.unique1)
1599 -> Parallel Hash Join
1600 Hash Cond: (t1.unique1 = t2.unique2)
1601 -> Parallel Index Only Scan using tenk1_unique1 on tenk1 t1
1602 -> Parallel Hash
1603 -> Parallel Index Scan using tenk1_unique2 on tenk1 t2
1604 -> Parallel Hash
1605 -> Parallel Index Only Scan using tenk1_unique1 on tenk1 t3
1606 (15 rows)
1608 -- Parallel sort but with expression (correlated subquery) that
1609 -- is prohibited in parallel plans.
1610 explain (costs off) select distinct
1611 unique1,
1612 (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
1613 from tenk1 t, generate_series(1, 1000);
1614 QUERY PLAN
1615 ---------------------------------------------------------------------------------
1616 Unique
1617 -> Sort
1618 Sort Key: t.unique1, ((SubPlan 1))
1619 -> Gather
1620 Workers Planned: 2
1621 -> Nested Loop
1622 -> Parallel Index Only Scan using tenk1_unique1 on tenk1 t
1623 -> Function Scan on generate_series
1624 SubPlan 1
1625 -> Index Only Scan using tenk1_unique1 on tenk1
1626 Index Cond: (unique1 = t.unique1)
1627 (11 rows)
1629 explain (costs off) select
1630 unique1,
1631 (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
1632 from tenk1 t, generate_series(1, 1000)
1633 order by 1, 2;
1634 QUERY PLAN
1635 ---------------------------------------------------------------------------
1636 Sort
1637 Sort Key: t.unique1, ((SubPlan 1))
1638 -> Gather
1639 Workers Planned: 2
1640 -> Nested Loop
1641 -> Parallel Index Only Scan using tenk1_unique1 on tenk1 t
1642 -> Function Scan on generate_series
1643 SubPlan 1
1644 -> Index Only Scan using tenk1_unique1 on tenk1
1645 Index Cond: (unique1 = t.unique1)
1646 (10 rows)
1648 -- Parallel sort but with expression not available until the upper rel.
1649 explain (costs off) select distinct sub.unique1, stringu1 || random()::text
1650 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub;
1651 QUERY PLAN
1652 ---------------------------------------------------------------------------------------------
1653 Unique
1654 -> Sort
1655 Sort Key: tenk1.unique1, (((tenk1.stringu1)::text || (random())::text)) COLLATE "C"
1656 -> Gather
1657 Workers Planned: 2
1658 -> Nested Loop
1659 -> Parallel Index Scan using tenk1_unique1 on tenk1
1660 -> Function Scan on generate_series
1661 (8 rows)
1663 explain (costs off) select sub.unique1, stringu1 || random()::text
1664 from tenk1, lateral (select tenk1.unique1 from generate_series(1, 1000)) as sub
1665 order by 1, 2;
1666 QUERY PLAN
1667 ---------------------------------------------------------------------------------------
1668 Sort
1669 Sort Key: tenk1.unique1, (((tenk1.stringu1)::text || (random())::text)) COLLATE "C"
1670 -> Gather
1671 Workers Planned: 2
1672 -> Nested Loop
1673 -> Parallel Index Scan using tenk1_unique1 on tenk1
1674 -> Function Scan on generate_series
1675 (7 rows)
1677 -- Disallow pushing down sort when pathkey is an SRF.
1678 explain (costs off) select unique1 from tenk1 order by unnest('{1,2}'::int[]);
1679 QUERY PLAN
1680 -------------------------------------------------------------------------
1681 Sort
1682 Sort Key: (unnest('{1,2}'::integer[]))
1683 -> Gather
1684 Workers Planned: 2
1685 -> ProjectSet
1686 -> Parallel Index Only Scan using tenk1_unique1 on tenk1
1687 (6 rows)