Skip to content

Commit e64cdab

Browse files
tglsfdctglsfdc
committed
Invent qsort_interruptible().
Justin Pryzby reported that some scenarios could cause gathering of extended statistics to spend many seconds in an un-cancelable qsort() operation. To fix, invent qsort_interruptible(), which is just like qsort_arg() except that it will also do CHECK_FOR_INTERRUPTS every so often. This bloats the backend by a couple of kB, which seems like a good investment. (We considered just enabling CHECK_FOR_INTERRUPTS in the existing qsort and qsort_arg functions, but there are some callers for which that'd demonstrably be unsafe. Opt-in seems like a better way.) For now, just apply qsort_interruptible() in statistics collection. There's probably more places where it could be useful, but we can always change other call sites as we find problems. Back-patch to v14. Before that we didn't have extended stats on expressions, so that the problem was less severe. Also, this patch depends on the sort_template infrastructure introduced in v14. Tom Lane and Justin Pryzby Discussion: https://postgr.es/m/20220509000108.GQ28830@telsasoft.com
1 parent 9200723 commit e64cdab

File tree

10 files changed

+80
-55
lines changed

10 files changed

+80
-55
lines changed

‎src/backend/commands/analyze.c

Lines changed: 13 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -100,7 +100,7 @@ static VacAttrStats *examine_attribute(Relation onerel, int attnum,
100100
static int acquire_sample_rows(Relation onerel, int elevel,
101101
HeapTuple *rows, int targrows,
102102
double *totalrows, double *totaldeadrows);
103-
static int compare_rows(const void *a, const void *b);
103+
static int compare_rows(const void *a, const void *b, void *arg);
104104
static int acquire_inherited_sample_rows(Relation onerel, int elevel,
105105
HeapTuple *rows, int targrows,
106106
double *totalrows, double *totaldeadrows);
@@ -1306,7 +1306,8 @@ acquire_sample_rows(Relation onerel, int elevel,
13061306
* tuples are already sorted.
13071307
*/
13081308
if (numrows == targrows)
1309-
qsort((void *) rows, numrows, sizeof(HeapTuple), compare_rows);
1309+
qsort_interruptible((void *) rows, numrows, sizeof(HeapTuple),
1310+
compare_rows, NULL);
13101311

13111312
/*
13121313
* Estimate total numbers of live and dead rows in relation, extrapolating
@@ -1342,10 +1343,10 @@ acquire_sample_rows(Relation onerel, int elevel,
13421343
}
13431344

13441345
/*
1345-
* qsort comparator for sorting rows[] array
1346+
* Comparator for sorting rows[] array
13461347
*/
13471348
static int
1348-
compare_rows(const void *a, const void *b)
1349+
compare_rows(const void *a, const void *b, void *arg)
13491350
{
13501351
HeapTuple ha = *(const HeapTuple *) a;
13511352
HeapTuple hb = *(const HeapTuple *) b;
@@ -1836,7 +1837,7 @@ static void compute_scalar_stats(VacAttrStatsP stats,
18361837
int samplerows,
18371838
double totalrows);
18381839
static int compare_scalars(const void *a, const void *b, void *arg);
1839-
static int compare_mcvs(const void *a, const void *b);
1840+
static int compare_mcvs(const void *a, const void *b, void *arg);
18401841
static int analyze_mcv_list(int *mcv_counts,
18411842
int num_mcv,
18421843
double stadistinct,
@@ -2473,8 +2474,8 @@ compute_scalar_stats(VacAttrStatsP stats,
24732474
/* Sort the collected values */
24742475
cxt.ssup = &ssup;
24752476
cxt.tupnoLink = tupnoLink;
2476-
qsort_arg((void *) values, values_cnt, sizeof(ScalarItem),
2477-
compare_scalars, (void *) &cxt);
2477+
qsort_interruptible((void *) values, values_cnt, sizeof(ScalarItem),
2478+
compare_scalars, (void *) &cxt);
24782479

24792480
/*
24802481
* Now scan the values in order, find the most common ones, and also
@@ -2718,8 +2719,8 @@ compute_scalar_stats(VacAttrStatsP stats,
27182719
deltafrac;
27192720

27202721
/* Sort the MCV items into position order to speed next loop */
2721-
qsort((void *) track, num_mcv,
2722-
sizeof(ScalarMCVItem), compare_mcvs);
2722+
qsort_interruptible((void *) track, num_mcv, sizeof(ScalarMCVItem),
2723+
compare_mcvs, NULL);
27232724

27242725
/*
27252726
* Collapse out the MCV items from the values[] array.
@@ -2882,7 +2883,7 @@ compute_scalar_stats(VacAttrStatsP stats,
28822883
}
28832884

28842885
/*
2885-
* qsort_arg comparator for sorting ScalarItems
2886+
* Comparator for sorting ScalarItems
28862887
*
28872888
* Aside from sorting the items, we update the tupnoLink[] array
28882889
* whenever two ScalarItems are found to contain equal datums. The array
@@ -2919,10 +2920,10 @@ compare_scalars(const void *a, const void *b, void *arg)
29192920
}
29202921

29212922
/*
2922-
* qsort comparator for sorting ScalarMCVItems by position
2923+
* Comparator for sorting ScalarMCVItems by position
29232924
*/
29242925
static int
2925-
compare_mcvs(const void *a, const void *b)
2926+
compare_mcvs(const void *a, const void *b, void *arg)
29262927
{
29272928
int da = ((const ScalarMCVItem *) a)->first;
29282929
int db = ((const ScalarMCVItem *) b)->first;

‎src/backend/statistics/extended_stats.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1129,8 +1129,8 @@ build_sorted_items(StatsBuildData *data, int *nitems,
11291129
}
11301130

11311131
/* do the sort, using the multi-sort */
1132-
qsort_arg((void *) items, nrows, sizeof(SortItem),
1133-
multi_sort_compare, mss);
1132+
qsort_interruptible((void *) items, nrows, sizeof(SortItem),
1133+
multi_sort_compare, mss);
11341134

11351135
return items;
11361136
}

‎src/backend/statistics/mcv.c

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -404,7 +404,7 @@ count_distinct_groups(int numrows, SortItem *items, MultiSortSupport mss)
404404
* order.
405405
*/
406406
static int
407-
compare_sort_item_count(const void *a, const void *b)
407+
compare_sort_item_count(const void *a, const void *b, void *arg)
408408
{
409409
SortItem *ia = (SortItem *) a;
410410
SortItem *ib = (SortItem *) b;
@@ -457,8 +457,8 @@ build_distinct_groups(int numrows, SortItem *items, MultiSortSupport mss,
457457
Assert(j + 1 == ngroups);
458458

459459
/* Sort the distinct groups by frequency (in descending order). */
460-
pg_qsort((void *) groups, ngroups, sizeof(SortItem),
461-
compare_sort_item_count);
460+
qsort_interruptible((void *) groups, ngroups, sizeof(SortItem),
461+
compare_sort_item_count, NULL);
462462

463463
*ndistinct = ngroups;
464464
return groups;
@@ -528,8 +528,8 @@ build_column_frequencies(SortItem *groups, int ngroups,
528528
}
529529

530530
/* sort the values, deduplicate */
531-
qsort_arg((void *) result[dim], ngroups, sizeof(SortItem),
532-
sort_item_compare, ssup);
531+
qsort_interruptible((void *) result[dim], ngroups, sizeof(SortItem),
532+
sort_item_compare, ssup);
533533

534534
/*
535535
* Identify distinct values, compute frequency (there might be
@@ -696,8 +696,8 @@ statext_mcv_serialize(MCVList *mcvlist, VacAttrStats **stats)
696696

697697
PrepareSortSupportFromOrderingOp(typentry->lt_opr, &ssup[dim]);
698698

699-
qsort_arg(values[dim], counts[dim], sizeof(Datum),
700-
compare_scalars_simple, &ssup[dim]);
699+
qsort_interruptible(values[dim], counts[dim], sizeof(Datum),
700+
compare_scalars_simple, &ssup[dim]);
701701

702702
/*
703703
* Walk through the array and eliminate duplicate values, but keep the

‎src/backend/statistics/mvdistinct.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -489,8 +489,8 @@ ndistinct_for_combination(double totalrows, StatsBuildData *data,
489489
}
490490

491491
/* We can sort the array now ... */
492-
qsort_arg((void *) items, numrows, sizeof(SortItem),
493-
multi_sort_compare, mss);
492+
qsort_interruptible((void *) items, numrows, sizeof(SortItem),
493+
multi_sort_compare, mss);
494494

495495
/* ... and count the number of distinct combinations */
496496

‎src/backend/tsearch/ts_typanalyze.c

Lines changed: 12 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -44,8 +44,10 @@ static void prune_lexemes_hashtable(HTAB *lexemes_tab, int b_current);
4444
static uint32 lexeme_hash(const void *key, Size keysize);
4545
static int lexeme_match(const void *key1, const void *key2, Size keysize);
4646
static int lexeme_compare(const void *key1, const void *key2);
47-
static int trackitem_compare_frequencies_desc(const void *e1, const void *e2);
48-
static int trackitem_compare_lexemes(const void *e1, const void *e2);
47+
static int trackitem_compare_frequencies_desc(const void *e1, const void *e2,
48+
void *arg);
49+
static int trackitem_compare_lexemes(const void *e1, const void *e2,
50+
void *arg);
4951

5052

5153
/*
@@ -347,8 +349,8 @@ compute_tsvector_stats(VacAttrStats *stats,
347349
*/
348350
if (num_mcelem < track_len)
349351
{
350-
qsort(sort_table, track_len, sizeof(TrackItem *),
351-
trackitem_compare_frequencies_desc);
352+
qsort_interruptible(sort_table, track_len, sizeof(TrackItem *),
353+
trackitem_compare_frequencies_desc, NULL);
352354
/* reset minfreq to the smallest frequency we're keeping */
353355
minfreq = sort_table[num_mcelem - 1]->frequency;
354356
}
@@ -376,8 +378,8 @@ compute_tsvector_stats(VacAttrStats *stats,
376378
* presorted we can employ binary search for that. See
377379
* ts_selfuncs.c for a real usage scenario.
378380
*/
379-
qsort(sort_table, num_mcelem, sizeof(TrackItem *),
380-
trackitem_compare_lexemes);
381+
qsort_interruptible(sort_table, num_mcelem, sizeof(TrackItem *),
382+
trackitem_compare_lexemes, NULL);
381383

382384
/* Must copy the target values into anl_context */
383385
old_context = MemoryContextSwitchTo(stats->anl_context);
@@ -510,10 +512,10 @@ lexeme_compare(const void *key1, const void *key2)
510512
}
511513

512514
/*
513-
* qsort() comparator for sorting TrackItems on frequencies (descending sort)
515+
* Comparator for sorting TrackItems on frequencies (descending sort)
514516
*/
515517
static int
516-
trackitem_compare_frequencies_desc(const void *e1, const void *e2)
518+
trackitem_compare_frequencies_desc(const void *e1, const void *e2, void *arg)
517519
{
518520
const TrackItem *const *t1 = (const TrackItem *const *) e1;
519521
const TrackItem *const *t2 = (const TrackItem *const *) e2;
@@ -522,10 +524,10 @@ trackitem_compare_frequencies_desc(const void *e1, const void *e2)
522524
}
523525

524526
/*
525-
* qsort() comparator for sorting TrackItems on lexemes
527+
* Comparator for sorting TrackItems on lexemes
526528
*/
527529
static int
528-
trackitem_compare_lexemes(const void *e1, const void *e2)
530+
trackitem_compare_lexemes(const void *e1, const void *e2, void *arg)
529531
{
530532
const TrackItem *const *t1 = (const TrackItem *const *) e1;
531533
const TrackItem *const *t2 = (const TrackItem *const *) e2;

‎src/backend/utils/adt/array_typanalyze.c

Lines changed: 16 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -86,9 +86,9 @@ static void prune_element_hashtable(HTAB *elements_tab, int b_current);
8686
static uint32 element_hash(const void *key, Size keysize);
8787
static int element_match(const void *key1, const void *key2, Size keysize);
8888
static int element_compare(const void *key1, const void *key2);
89-
static int trackitem_compare_frequencies_desc(const void *e1, const void *e2);
90-
static int trackitem_compare_element(const void *e1, const void *e2);
91-
static int countitem_compare_count(const void *e1, const void *e2);
89+
static int trackitem_compare_frequencies_desc(const void *e1, const void *e2, void *arg);
90+
static int trackitem_compare_element(const void *e1, const void *e2, void *arg);
91+
static int countitem_compare_count(const void *e1, const void *e2, void *arg);
9292

9393

9494
/*
@@ -502,8 +502,8 @@ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
502502
*/
503503
if (num_mcelem < track_len)
504504
{
505-
qsort(sort_table, track_len, sizeof(TrackItem *),
506-
trackitem_compare_frequencies_desc);
505+
qsort_interruptible(sort_table, track_len, sizeof(TrackItem *),
506+
trackitem_compare_frequencies_desc, NULL);
507507
/* reset minfreq to the smallest frequency we're keeping */
508508
minfreq = sort_table[num_mcelem - 1]->frequency;
509509
}
@@ -522,8 +522,8 @@ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
522522
* the element type's default comparison function. This permits
523523
* fast binary searches in selectivity estimation functions.
524524
*/
525-
qsort(sort_table, num_mcelem, sizeof(TrackItem *),
526-
trackitem_compare_element);
525+
qsort_interruptible(sort_table, num_mcelem, sizeof(TrackItem *),
526+
trackitem_compare_element, NULL);
527527

528528
/* Must copy the target values into anl_context */
529529
old_context = MemoryContextSwitchTo(stats->anl_context);
@@ -599,8 +599,9 @@ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
599599
{
600600
sorted_count_items[j++] = count_item;
601601
}
602-
qsort(sorted_count_items, count_items_count,
603-
sizeof(DECountItem *), countitem_compare_count);
602+
qsort_interruptible(sorted_count_items, count_items_count,
603+
sizeof(DECountItem *),
604+
countitem_compare_count, NULL);
604605

605606
/*
606607
* Prepare to fill stanumbers with the histogram, followed by the
@@ -751,10 +752,10 @@ element_compare(const void *key1, const void *key2)
751752
}
752753

753754
/*
754-
* qsort() comparator for sorting TrackItems by frequencies (descending sort)
755+
* Comparator for sorting TrackItems by frequencies (descending sort)
755756
*/
756757
static int
757-
trackitem_compare_frequencies_desc(const void *e1, const void *e2)
758+
trackitem_compare_frequencies_desc(const void *e1, const void *e2, void *arg)
758759
{
759760
const TrackItem *const *t1 = (const TrackItem *const *) e1;
760761
const TrackItem *const *t2 = (const TrackItem *const *) e2;
@@ -763,10 +764,10 @@ trackitem_compare_frequencies_desc(const void *e1, const void *e2)
763764
}
764765

765766
/*
766-
* qsort() comparator for sorting TrackItems by element values
767+
* Comparator for sorting TrackItems by element values
767768
*/
768769
static int
769-
trackitem_compare_element(const void *e1, const void *e2)
770+
trackitem_compare_element(const void *e1, const void *e2, void *arg)
770771
{
771772
const TrackItem *const *t1 = (const TrackItem *const *) e1;
772773
const TrackItem *const *t2 = (const TrackItem *const *) e2;
@@ -775,10 +776,10 @@ trackitem_compare_element(const void *e1, const void *e2)
775776
}
776777

777778
/*
778-
* qsort() comparator for sorting DECountItems by count
779+
* Comparator for sorting DECountItems by count
779780
*/
780781
static int
781-
countitem_compare_count(const void *e1, const void *e2)
782+
countitem_compare_count(const void *e1, const void *e2, void *arg)
782783
{
783784
const DECountItem *const *t1 = (const DECountItem *const *) e1;
784785
const DECountItem *const *t2 = (const DECountItem *const *) e2;

‎src/backend/utils/adt/rangetypes_typanalyze.c

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -32,7 +32,7 @@
3232
#include "utils/rangetypes.h"
3333
#include "utils/multirangetypes.h"
3434

35-
static int float8_qsort_cmp(const void *a1, const void *a2);
35+
static int float8_qsort_cmp(const void *a1, const void *a2, void *arg);
3636
static int range_bound_qsort_cmp(const void *a1, const void *a2, void *arg);
3737
static void compute_range_stats(VacAttrStats *stats,
3838
AnalyzeAttrFetchFunc fetchfunc, int samplerows,
@@ -93,7 +93,7 @@ multirange_typanalyze(PG_FUNCTION_ARGS)
9393
* Comparison function for sorting float8s, used for range lengths.
9494
*/
9595
static int
96-
float8_qsort_cmp(const void *a1, const void *a2)
96+
float8_qsort_cmp(const void *a1, const void *a2, void *arg)
9797
{
9898
const float8 *f1 = (const float8 *) a1;
9999
const float8 *f2 = (const float8 *) a2;
@@ -280,10 +280,10 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
280280
if (non_empty_cnt >= 2)
281281
{
282282
/* Sort bound values */
283-
qsort_arg(lowers, non_empty_cnt, sizeof(RangeBound),
284-
range_bound_qsort_cmp, typcache);
285-
qsort_arg(uppers, non_empty_cnt, sizeof(RangeBound),
286-
range_bound_qsort_cmp, typcache);
283+
qsort_interruptible(lowers, non_empty_cnt, sizeof(RangeBound),
284+
range_bound_qsort_cmp, typcache);
285+
qsort_interruptible(uppers, non_empty_cnt, sizeof(RangeBound),
286+
range_bound_qsort_cmp, typcache);
287287

288288
num_hist = non_empty_cnt;
289289
if (num_hist > num_bins)
@@ -345,7 +345,8 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
345345
* Ascending sort of range lengths for further filling of
346346
* histogram
347347
*/
348-
qsort(lengths, non_empty_cnt, sizeof(float8), float8_qsort_cmp);
348+
qsort_interruptible(lengths, non_empty_cnt, sizeof(float8),
349+
float8_qsort_cmp, NULL);
349350

350351
num_hist = non_empty_cnt;
351352
if (num_hist > num_bins)

‎src/backend/utils/sort/Makefile

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,7 @@ override CPPFLAGS := -I. -I$(srcdir) $(CPPFLAGS)
1616

1717
OBJS = \
1818
logtape.o \
19+
qsort_interruptible.o \
1920
sharedtuplestore.o \
2021
sortsupport.o \
2122
tuplesort.o \

‎src/backend/utils/sort/qsort_interruptible.c

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
/*
2+
* qsort_interruptible.c: qsort_arg that includes CHECK_FOR_INTERRUPTS
3+
*/
4+
5+
#include "postgres.h"
6+
#include "miscadmin.h"
7+
8+
#define ST_SORT qsort_interruptible
9+
#define ST_ELEMENT_TYPE_VOID
10+
#define ST_COMPARATOR_TYPE_NAME qsort_arg_comparator
11+
#define ST_COMPARE_RUNTIME_POINTER
12+
#define ST_COMPARE_ARG_TYPE void
13+
#define ST_SCOPE
14+
#define ST_DEFINE
15+
#define ST_CHECK_FOR_INTERRUPTS
16+
#include "lib/sort_template.h"

‎src/include/port.h

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -499,6 +499,9 @@ typedef int (*qsort_arg_comparator) (const void *a, const void *b, void *arg);
499499
extern void qsort_arg(void *base, size_t nel, size_t elsize,
500500
qsort_arg_comparator cmp, void *arg);
501501

502+
extern void qsort_interruptible(void *base, size_t nel, size_t elsize,
503+
qsort_arg_comparator cmp, void *arg);
504+
502505
extern void *bsearch_arg(const void *key, const void *base,
503506
size_t nmemb, size_t size,
504507
int (*compar) (const void *, const void *, void *),

0 commit comments

Comments
 (0)