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

2 files changed, 24 insertions, 22 deletions

diff --git a/src/backend/utils/adt/array_typanalyze.c b/src/backend/utils/adt/array_typanalyze.c
index c5008a0c169..e873d228592 100644
--- a/src/backend/utils/adt/array_typanalyze.c
+++ b/src/backend/utils/adt/array_typanalyze.c
@@ -86,9 +86,9 @@ static void prune_element_hashtable(HTAB *elements_tab, int b_current);
 static uint32 element_hash(const void *key, Size keysize);
 static int	element_match(const void *key1, const void *key2, Size keysize);
 static int	element_compare(const void *key1, const void *key2);
-static int	trackitem_compare_frequencies_desc(const void *e1, const void *e2);
-static int	trackitem_compare_element(const void *e1, const void *e2);
-static int	countitem_compare_count(const void *e1, const void *e2);
+static int	trackitem_compare_frequencies_desc(const void *e1, const void *e2, void *arg);
+static int	trackitem_compare_element(const void *e1, const void *e2, void *arg);
+static int	countitem_compare_count(const void *e1, const void *e2, void *arg);
 
 
 /*
@@ -502,8 +502,8 @@ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 		 */
 		if (num_mcelem < track_len)
 		{
-			qsort(sort_table, track_len, sizeof(TrackItem *),
-				  trackitem_compare_frequencies_desc);
+			qsort_interruptible(sort_table, track_len, sizeof(TrackItem *),
+								trackitem_compare_frequencies_desc, NULL);
 			/* reset minfreq to the smallest frequency we're keeping */
 			minfreq = sort_table[num_mcelem - 1]->frequency;
 		}
@@ -522,8 +522,8 @@ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 			 * the element type's default comparison function.  This permits
 			 * fast binary searches in selectivity estimation functions.
 			 */
-			qsort(sort_table, num_mcelem, sizeof(TrackItem *),
-				  trackitem_compare_element);
+			qsort_interruptible(sort_table, num_mcelem, sizeof(TrackItem *),
+								trackitem_compare_element, NULL);
 
 			/* Must copy the target values into anl_context */
 			old_context = MemoryContextSwitchTo(stats->anl_context);
@@ -599,8 +599,9 @@ compute_array_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 			{
 				sorted_count_items[j++] = count_item;
 			}
-			qsort(sorted_count_items, count_items_count,
-				  sizeof(DECountItem *), countitem_compare_count);
+			qsort_interruptible(sorted_count_items, count_items_count,
+								sizeof(DECountItem *),
+								countitem_compare_count, NULL);
 
 			/*
 			 * Prepare to fill stanumbers with the histogram, followed by the
@@ -751,10 +752,10 @@ element_compare(const void *key1, const void *key2)
 }
 
 /*
- * qsort() comparator for sorting TrackItems by frequencies (descending sort)
+ * Comparator for sorting TrackItems by frequencies (descending sort)
  */
 static int
-trackitem_compare_frequencies_desc(const void *e1, const void *e2)
+trackitem_compare_frequencies_desc(const void *e1, const void *e2, void *arg)
 {
 	const TrackItem *const *t1 = (const TrackItem *const *) e1;
 	const TrackItem *const *t2 = (const TrackItem *const *) e2;
@@ -763,10 +764,10 @@ trackitem_compare_frequencies_desc(const void *e1, const void *e2)
 }
 
 /*
- * qsort() comparator for sorting TrackItems by element values
+ * Comparator for sorting TrackItems by element values
  */
 static int
-trackitem_compare_element(const void *e1, const void *e2)
+trackitem_compare_element(const void *e1, const void *e2, void *arg)
 {
 	const TrackItem *const *t1 = (const TrackItem *const *) e1;
 	const TrackItem *const *t2 = (const TrackItem *const *) e2;
@@ -775,10 +776,10 @@ trackitem_compare_element(const void *e1, const void *e2)
 }
 
 /*
- * qsort() comparator for sorting DECountItems by count
+ * Comparator for sorting DECountItems by count
  */
 static int
-countitem_compare_count(const void *e1, const void *e2)
+countitem_compare_count(const void *e1, const void *e2, void *arg)
 {
 	const DECountItem *const *t1 = (const DECountItem *const *) e1;
 	const DECountItem *const *t2 = (const DECountItem *const *) e2;
diff --git a/src/backend/utils/adt/rangetypes_typanalyze.c b/src/backend/utils/adt/rangetypes_typanalyze.c
index 671fe6ddb7a..8e0d330f872 100644
--- a/src/backend/utils/adt/rangetypes_typanalyze.c
+++ b/src/backend/utils/adt/rangetypes_typanalyze.c
@@ -32,7 +32,7 @@
 #include "utils/rangetypes.h"
 #include "utils/multirangetypes.h"
 
-static int	float8_qsort_cmp(const void *a1, const void *a2);
+static int	float8_qsort_cmp(const void *a1, const void *a2, void *arg);
 static int	range_bound_qsort_cmp(const void *a1, const void *a2, void *arg);
 static void compute_range_stats(VacAttrStats *stats,
 								AnalyzeAttrFetchFunc fetchfunc, int samplerows,
@@ -93,7 +93,7 @@ multirange_typanalyze(PG_FUNCTION_ARGS)
  * Comparison function for sorting float8s, used for range lengths.
  */
 static int
-float8_qsort_cmp(const void *a1, const void *a2)
+float8_qsort_cmp(const void *a1, const void *a2, void *arg)
 {
 	const float8 *f1 = (const float8 *) a1;
 	const float8 *f2 = (const float8 *) a2;
@@ -280,10 +280,10 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 		if (non_empty_cnt >= 2)
 		{
 			/* Sort bound values */
-			qsort_arg(lowers, non_empty_cnt, sizeof(RangeBound),
-					  range_bound_qsort_cmp, typcache);
-			qsort_arg(uppers, non_empty_cnt, sizeof(RangeBound),
-					  range_bound_qsort_cmp, typcache);
+			qsort_interruptible(lowers, non_empty_cnt, sizeof(RangeBound),
+								range_bound_qsort_cmp, typcache);
+			qsort_interruptible(uppers, non_empty_cnt, sizeof(RangeBound),
+								range_bound_qsort_cmp, typcache);
 
 			num_hist = non_empty_cnt;
 			if (num_hist > num_bins)
@@ -345,7 +345,8 @@ compute_range_stats(VacAttrStats *stats, AnalyzeAttrFetchFunc fetchfunc,
 			 * Ascending sort of range lengths for further filling of
 			 * histogram
 			 */
-			qsort(lengths, non_empty_cnt, sizeof(float8), float8_qsort_cmp);
+			qsort_interruptible(lengths, non_empty_cnt, sizeof(float8),
+								float8_qsort_cmp, NULL);
 
 			num_hist = non_empty_cnt;
 			if (num_hist > num_bins)