Skip to content

Commit af72b08

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 5e7608e commit af72b08

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
@@ -99,7 +99,7 @@ static VacAttrStats *examine_attribute(Relation onerel, int attnum,
9999
static int acquire_sample_rows(Relation onerel, int elevel,
100100
HeapTuple *rows, int targrows,
101101
double *totalrows, double *totaldeadrows);
102-
static int compare_rows(const void *a, const void *b);
102+
static int compare_rows(const void *a, const void *b, void *arg);
103103
static int acquire_inherited_sample_rows(Relation onerel, int elevel,
104104
HeapTuple *rows, int targrows,
105105
double *totalrows, double *totaldeadrows);
@@ -1324,7 +1324,8 @@ acquire_sample_rows(Relation onerel, int elevel,
13241324
* tuples are already sorted.
13251325
*/
13261326
if (numrows == targrows)
1327-
qsort((void *) rows, numrows, sizeof(HeapTuple), compare_rows);
1327+
qsort_interruptible((void *) rows, numrows, sizeof(HeapTuple),
1328+
compare_rows, NULL);
13281329

13291330
/*
13301331
* Estimate total numbers of live and dead rows in relation, extrapolating
@@ -1360,10 +1361,10 @@ acquire_sample_rows(Relation onerel, int elevel,
13601361
}
13611362

13621363
/*
1363-
* qsort comparator for sorting rows[] array
1364+
* Comparator for sorting rows[] array
13641365
*/
13651366
static int
1366-
compare_rows(const void *a, const void *b)
1367+
compare_rows(const void *a, const void *b, void *arg)
13671368
{
13681369
HeapTuple ha = *(const HeapTuple *) a;
13691370
HeapTuple hb = *(const HeapTuple *) b;
@@ -1857,7 +1858,7 @@ static void compute_scalar_stats(VacAttrStatsP stats,
18571858
int samplerows,
18581859
double totalrows);
18591860
static int compare_scalars(const void *a, const void *b, void *arg);
1860-
static int compare_mcvs(const void *a, const void *b);
1861+
static int compare_mcvs(const void *a, const void *b, void *arg);
18611862
static int analyze_mcv_list(int *mcv_counts,
18621863
int num_mcv,
18631864
double stadistinct,
@@ -2494,8 +2495,8 @@ compute_scalar_stats(VacAttrStatsP stats,
24942495
/* Sort the collected values */
24952496
cxt.ssup = &ssup;
24962497
cxt.tupnoLink = tupnoLink;
2497-
qsort_arg((void *) values, values_cnt, sizeof(ScalarItem),
2498-
compare_scalars, (void *) &cxt);
2498+
qsort_interruptible((void *) values, values_cnt, sizeof(ScalarItem),
2499+
compare_scalars, (void *) &cxt);
24992500

25002501
/*
25012502
* Now scan the values in order, find the most common ones, and also
@@ -2739,8 +2740,8 @@ compute_scalar_stats(VacAttrStatsP stats,
27392740
deltafrac;
27402741

27412742
/* Sort the MCV items into position order to speed next loop */
2742-
qsort((void *) track, num_mcv,
2743-
sizeof(ScalarMCVItem), compare_mcvs);
2743+
qsort_interruptible((void *) track, num_mcv, sizeof(ScalarMCVItem),
2744+
compare_mcvs, NULL);
27442745

27452746
/*
27462747
* Collapse out the MCV items from the values[] array.
@@ -2903,7 +2904,7 @@ compute_scalar_stats(VacAttrStatsP stats,
29032904
}
29042905

29052906
/*
2906-
* qsort_arg comparator for sorting ScalarItems
2907+
* Comparator for sorting ScalarItems
29072908
*
29082909
* Aside from sorting the items, we update the tupnoLink[] array
29092910
* whenever two ScalarItems are found to contain equal datums. The array
@@ -2940,10 +2941,10 @@ compare_scalars(const void *a, const void *b, void *arg)
29402941
}
29412942

29422943
/*
2943-
* qsort comparator for sorting ScalarMCVItems by position
2944+
* Comparator for sorting ScalarMCVItems by position
29442945
*/
29452946
static int
2946-
compare_mcvs(const void *a, const void *b)
2947+
compare_mcvs(const void *a, const void *b, void *arg)
29472948
{
29482949
int da = ((const ScalarMCVItem *) a)->first;
29492950
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
@@ -1133,8 +1133,8 @@ build_sorted_items(StatsBuildData *data, int *nitems,
11331133
}
11341134

11351135
/* do the sort, using the multi-sort */
1136-
qsort_arg((void *) items, nrows, sizeof(SortItem),
1137-
multi_sort_compare, mss);
1136+
qsort_interruptible((void *) items, nrows, sizeof(SortItem),
1137+
multi_sort_compare, mss);
11381138

11391139
return items;
11401140
}

‎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
@@ -695,8 +695,8 @@ statext_mcv_serialize(MCVList *mcvlist, VacAttrStats **stats)
695695

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

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

701701
/*
702702
* 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
@@ -488,8 +488,8 @@ ndistinct_for_combination(double totalrows, StatsBuildData *data,
488488
}
489489

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

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

‎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
@@ -508,6 +508,9 @@ typedef int (*qsort_arg_comparator) (const void *a, const void *b, void *arg);
508508
extern void qsort_arg(void *base, size_t nel, size_t elsize,
509509
qsort_arg_comparator cmp, void *arg);
510510

511+
extern void qsort_interruptible(void *base, size_t nel, size_t elsize,
512+
qsort_arg_comparator cmp, void *arg);
513+
511514
extern void *bsearch_arg(const void *key, const void *base,
512515
size_t nmemb, size_t size,
513516
int (*compar) (const void *, const void *, void *),

0 commit comments

Comments
 (0)