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