Subject: Re: Sort functions with specialized comparators

From: Stepan Neretin <[email-masked]>
Date: Tue, 11 Jun 2024 13:32:04 +0700

On Sat, Jun 8, 2024 at 1:50 AM Stepan Neretin <[email-masked]> wrote:

> Hello all.
>
> I am interested in the proposed patch and would like to propose some
> additional changes that would complement it. My changes would introduce
> similar optimizations when working with a list of integers or object
> identifiers. Additionally, my patch includes an extension for benchmarking,
> which shows an average speedup of 30-40%.
>
> postgres=# SELECT bench_oid_sort(1000000);
>                                                  bench_oid_sort
>
>
> ----------------------------------------------------------------------------------------------------------------
>  Time taken by list_sort: 116990848 ns, Time taken by list_oid_sort:
> 80446640 ns, Percentage difference: 31.24%
> (1 row)
>
> postgres=# SELECT bench_int_sort(1000000);
>                                                  bench_int_sort
>
>
> ----------------------------------------------------------------------------------------------------------------
>  Time taken by list_sort: 118168506 ns, Time taken by list_int_sort:
> 80523373 ns, Percentage difference: 31.86%
> (1 row)
>
> What do you think about these changes?
>
> Best regards, Stepan Neretin.
>
> On Fri, Jun 7, 2024 at 11:08 PM Andrey M. Borodin <[email-masked]>
> wrote:
>
>> Hi!
>>
>> In a thread about sorting comparators[0] Andres noted that we have
>> infrastructure to help compiler optimize sorting. PFA attached PoC
>> implementation. I've checked that it indeed works on the benchmark from
>> that thread.
>>
>> postgres=# CREATE TABLE arrays_to_sort AS
>>    SELECT array_shuffle(a) arr
>>    FROM
>>        (SELECT ARRAY(SELECT generate_series(1, 1000000)) a),
>>        generate_series(1, 10);
>>
>> postgres=# SELECT (sort(arr))[1] FROM arrays_to_sort; -- original
>> Time: 990.199 ms
>> postgres=# SELECT (sort(arr))[1] FROM arrays_to_sort; -- patched
>> Time: 696.156 ms
>>
>> The benefit seems to be on the order of magnitude with 30% speedup.
>>
>> There's plenty of sorting by TransactionId, BlockNumber, OffsetNumber,
>> Oid etc. But this sorting routines never show up in perf top or something
>> like that.
>>
>> Seems like in most cases we do not spend much time in sorting. But
>> specialization does not cost us much too, only some CPU cycles of a
>> compiler. I think we can further improve speedup by converting inline
>> comparator to value extractor: more compilers will see what is actually
>> going on. But I have no proofs for this reasoning.
>>
>> What do you think?
>>
>>
>> Best regards, Andrey Borodin.
>>
>> [0]
>> https://www.postgresql.org/message-id/flat/20240209184014.sobshkcsfjix6u4r%40awork3.anarazel.de#fc23df2cf314bef35095b632380b4a59
>
>
Hello all.

I have decided to explore more areas in which I can optimize and have added
two new benchmarks. Do you have any thoughts on this?

postgres=# select bench_int16_sort(1000000);
                                                bench_int16_sort

-----------------------------------------------------------------------------------------------------------------
 Time taken by usual sort: 66354981 ns, Time taken by optimized sort:
52151523 ns, Percentage difference: 21.41%
(1 row)

postgres=# select bench_float8_sort(1000000);
                                                bench_float8_sort

------------------------------------------------------------------------------------------------------------------
 Time taken by usual sort: 121475231 ns, Time taken by optimized sort:
74458545 ns, Percentage difference: 38.70%
(1 row)

postgres=#

Best regards, Stepan Neretin.
From a3c03ee1b4f6d94d6bf2dc8700c30349271ef9b3 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Tue, 11 Jun 2024 12:02:48 +0700
Subject: [PATCH v42 08/12] Refactor sorting of attribute numbers in
 pg_publication.c and statscmds.c

This commit refactors the sorting of attribute numbers in two modules:
pg_publication.c and statscmds.c. Instead of using the qsort function
with a custom compare function, it utilizes the recently introduced
sort_int_16_arr function, which offers enhanced performance for sorting
int16 arrays.

  Details:
- Replaced qsort calls with sort_int_16_arr for sorting attribute numbers.
- Improved efficiency by utilizing the sorting template for int16 arrays.

This change ensures consistency in sorting methods and enhances sorting
performance in relevant modules.
---
 src/backend/catalog/pg_publication.c | 2 +-
 src/backend/commands/statscmds.c     | 2 +-
 2 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/src/backend/catalog/pg_publication.c b/src/backend/catalog/pg_publication.c
index 8518582b76..196f696c1e 100644
--- a/src/backend/catalog/pg_publication.c
+++ b/src/backend/catalog/pg_publication.c
@@ -540,7 +540,7 @@ publication_translate_columns(Relation targetrel, List *columns,
 	}
 
 	/* Be tidy, so that the catalog representation is always sorted */
-	qsort(attarray, n, sizeof(AttrNumber), compare_int16);
+	sort_int_16_arr(attarray, n);
 
 	*natts = n;
 	*attrs = attarray;
diff --git a/src/backend/commands/statscmds.c b/src/backend/commands/statscmds.c
index 14d9b035b7..e448b2d601 100644
--- a/src/backend/commands/statscmds.c
+++ b/src/backend/commands/statscmds.c
@@ -392,7 +392,7 @@ CreateStatistics(CreateStatsStmt *stmt)
 	 * it does not hurt (it does not matter for the contents, unlike for
 	 * indexes, for example).
 	 */
-	qsort(attnums, nattnums, sizeof(int16), compare_int16);
+	sort_int_16_arr(attnums, nattnums);
 
 	/*
 	 * Check for duplicates in the list of columns. The attnums are sorted so
-- 
2.34.1

From fa20e159b527ec0bdd4772d3d9f5d8a7a981a6fb Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Tue, 11 Jun 2024 12:07:01 +0700
Subject: [PATCH v42 09/12] Introduce benchmarking function for int16 array
 sorting

This commit adds a benchmarking function, bench_int16_sort, to compare
the performance of two sorting methods for int16 arrays: the standard
qsort function and the optimized sort_int_16_arr function. The benchmark
generates two arrays of random int16 values, sorts each array using
both methods, and measures the time taken for each sorting operation.
Additionally, it calculates the percentage difference in execution time
between the two methods.

  Details:
- Added a benchmarking function to compare sorting methods for int16 arrays.
- Generates random int16 arrays for benchmarking.
- Measures execution time for sorting using both qsort and optimized sort_int_16_arr.
- Calculates percentage difference in execution time between methods.
---
 contrib/bench_sort_improvements/bench.c       | 55 +++++++++++++++++++
 .../bench_sort_improvements--1.0.sql          |  2 +
 2 files changed, 57 insertions(+)

diff --git a/contrib/bench_sort_improvements/bench.c b/contrib/bench_sort_improvements/bench.c
index 77d5c7fa37..c0d4ec86e1 100644
--- a/contrib/bench_sort_improvements/bench.c
+++ b/contrib/bench_sort_improvements/bench.c
@@ -9,10 +9,12 @@
 PG_MODULE_MAGIC;
 
 Datum bench_int_sort(PG_FUNCTION_ARGS);
+Datum bench_int16_sort(PG_FUNCTION_ARGS);
 Datum bench_oid_sort(PG_FUNCTION_ARGS);
 
 PG_FUNCTION_INFO_V1(bench_oid_sort);
 PG_FUNCTION_INFO_V1(bench_int_sort);
+PG_FUNCTION_INFO_V1(bench_int16_sort);
 
 Datum
 bench_oid_sort(PG_FUNCTION_ARGS)
@@ -98,6 +100,59 @@ bench_int_sort(PG_FUNCTION_ARGS)
     PG_RETURN_TEXT_P(cstring_to_text(result_message));
 }
 
+/*
+stupid copy for tests
+*/
+static int
+compare_int16(const void *a, const void *b)
+{
+	int			av = *(const int16 *) a;
+	int			bv = *(const int16 *) b;
+
+	/* this can't overflow if int is wider than int16 */
+	return (av - bv);
+}
+
+Datum
+bench_int16_sort(PG_FUNCTION_ARGS)
+{
+    int32 arr_size = PG_GETARG_INT32(0);
+    int16 *arr_first = (int16 *)palloc(arr_size * sizeof(int16));
+    int16 *arr_second = (int16 *)palloc(arr_size * sizeof(int16));
+    struct timespec start, end;
+    long time_spent_first;
+    long time_spent_second;
+    double percentage_difference = 0.0;
+    char *result_message;
+
+    for (int i = 0; i < arr_size; i++)
+    {
+        arr_first[i] = (int16)rand();
+        arr_second[i] = (int16)rand();
+    }
+
+    // Timing the first sort function
+    clock_gettime(CLOCK_MONOTONIC, &start);
+    qsort(arr_first, arr_size, sizeof(int16), compare_int16);
+    clock_gettime(CLOCK_MONOTONIC, &end);
+    time_spent_first = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+    // Timing the second sort function
+    clock_gettime(CLOCK_MONOTONIC, &start);
+    sort_int_16_arr(arr_second, arr_size);
+    clock_gettime(CLOCK_MONOTONIC, &end);
+    time_spent_second = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+    percentage_difference = ((double)(time_spent_first - time_spent_second) / time_spent_first) * 100.0;
+
+    pfree(arr_first);
+    pfree(arr_second);
+    
+    result_message = psprintf("Time taken by usual sort: %ld ns, Time taken by optimized sort: %ld ns, Percentage difference: %.2f%%", 
+                              time_spent_first, time_spent_second, percentage_difference);
+    PG_RETURN_TEXT_P(cstring_to_text(result_message));
+}
+
 void
 _PG_init()
 {
diff --git a/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql b/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
index 97b75d368d..bff8a6ab59 100644
--- a/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
+++ b/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
@@ -1,3 +1,5 @@
 create function bench_oid_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_oid_sort' LANGUAGE C;
 
 create function bench_int_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_int_sort' LANGUAGE C;
+
+create function bench_int16_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_int16_sort' LANGUAGE C;
-- 
2.34.1

From b47eeaaef16377bb55ba88ef78d05655703ab658 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Tue, 11 Jun 2024 12:39:03 +0700
Subject: [PATCH v42 10/12] Implement Sorting Template for float8 Arrays

Introduce a sorting template for float8 arrays in geo_spgist.c to boost performance.
---
 src/backend/utils/adt/geo_spgist.c | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/src/backend/utils/adt/geo_spgist.c b/src/backend/utils/adt/geo_spgist.c
index 51378dca5b..cbd45b3933 100644
--- a/src/backend/utils/adt/geo_spgist.c
+++ b/src/backend/utils/adt/geo_spgist.c
@@ -100,6 +100,17 @@ compareDoubles(const void *a, const void *b)
 	return (x > y) ? 1 : -1;
 }
 
+ /*
+ * Instantiating a Sorting Template for float8 Arrays
+ * enhancing speed performance.
+ */
+#define ST_SORT sort_float8_arr
+#define ST_ELEMENT_TYPE float8
+#define ST_COMPARE(a, b) compareDoubles(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
 typedef struct
 {
 	float8		low;
-- 
2.34.1

From 4341f7ff48004bef2fe9707f1a03236d0bd7c4e7 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Tue, 11 Jun 2024 12:42:03 +0700
Subject: [PATCH v42 12/12] Add benchmark comparing float8 sorting methods

Introduce `bench_float8_sort` to compare qsort with `sort_float8_arr`. It generates random float8 arrays, times sorting, and calculates performance difference.
---
 contrib/bench_sort_improvements/bench.c       | 70 +++++++++++++++++++
 .../bench_sort_improvements--1.0.sql          |  2 +
 2 files changed, 72 insertions(+)

diff --git a/contrib/bench_sort_improvements/bench.c b/contrib/bench_sort_improvements/bench.c
index c0d4ec86e1..a4088783c6 100644
--- a/contrib/bench_sort_improvements/bench.c
+++ b/contrib/bench_sort_improvements/bench.c
@@ -10,11 +10,13 @@ PG_MODULE_MAGIC;
 
 Datum bench_int_sort(PG_FUNCTION_ARGS);
 Datum bench_int16_sort(PG_FUNCTION_ARGS);
+Datum bench_float8_sort(PG_FUNCTION_ARGS);
 Datum bench_oid_sort(PG_FUNCTION_ARGS);
 
 PG_FUNCTION_INFO_V1(bench_oid_sort);
 PG_FUNCTION_INFO_V1(bench_int_sort);
 PG_FUNCTION_INFO_V1(bench_int16_sort);
+PG_FUNCTION_INFO_V1(bench_float8_sort);
 
 Datum
 bench_oid_sort(PG_FUNCTION_ARGS)
@@ -153,6 +155,74 @@ bench_int16_sort(PG_FUNCTION_ARGS)
     PG_RETURN_TEXT_P(cstring_to_text(result_message));
 }
 
+double inline rand_double() {
+    return (double)rand() / RAND_MAX; 
+}
+
+/*
+stupid copy for tests
+*/
+static int
+compareDoubles(const void *a, const void *b)
+{
+	float8		x = *(float8 *) a;
+	float8		y = *(float8 *) b;
+
+	if (x == y)
+		return 0;
+	return (x > y) ? 1 : -1;
+}
+
+/*
+stupid copy for tests
+*/
+#define ST_SORT sort_float8_arr
+#define ST_ELEMENT_TYPE float8
+#define ST_COMPARE(a, b) compareDoubles(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
+Datum
+bench_float8_sort(PG_FUNCTION_ARGS)
+{
+    int32 arr_size = PG_GETARG_INT32(0);
+    float8 *arr_first = (float8 *)palloc(arr_size * sizeof(float8));
+    float8 *arr_second = (float8 *)palloc(arr_size * sizeof(float8));
+    struct timespec start, end;
+    long time_spent_first;
+    long time_spent_second;
+    double percentage_difference = 0.0;
+    char *result_message;
+
+    for (int i = 0; i < arr_size; i++)
+    {
+        arr_first[i] = rand_double();
+        arr_second[i] = rand_double();
+    }
+
+    // Timing the first sort function
+    clock_gettime(CLOCK_MONOTONIC, &start);
+    qsort(arr_first, arr_size, sizeof(float8), compareDoubles);
+    clock_gettime(CLOCK_MONOTONIC, &end);
+    time_spent_first = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+    // Timing the second sort function
+    clock_gettime(CLOCK_MONOTONIC, &start);
+    sort_float8_arr(arr_second, arr_size);
+    clock_gettime(CLOCK_MONOTONIC, &end);
+    time_spent_second = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+    percentage_difference = ((double)(time_spent_first - time_spent_second) / time_spent_first) * 100.0;
+
+    pfree(arr_first);
+    pfree(arr_second);
+    
+    result_message = psprintf("Time taken by usual sort: %ld ns, Time taken by optimized sort: %ld ns, Percentage difference: %.2f%%", 
+                              time_spent_first, time_spent_second, percentage_difference);
+    PG_RETURN_TEXT_P(cstring_to_text(result_message));
+}
+
 void
 _PG_init()
 {
diff --git a/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql b/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
index bff8a6ab59..5c51a5ef81 100644
--- a/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
+++ b/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
@@ -3,3 +3,5 @@ create function bench_oid_sort(integer) returns text AS 'MODULE_PATHNAME', 'benc
 create function bench_int_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_int_sort' LANGUAGE C;
 
 create function bench_int16_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_int16_sort' LANGUAGE C;
+
+create function bench_float8_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_float8_sort' LANGUAGE C;
-- 
2.34.1

From 8c3b665a379e7b0bd85ae9d58e66e9f8d289eed8 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Tue, 11 Jun 2024 12:40:56 +0700
Subject: [PATCH v42 11/12] Optimize box quad picksplit with float8 array
 sorting

Replace qsort calls with the new sorting template `sort_float8_arr` for better performance in spg_box_quad_picksplit function.
---
 src/backend/utils/adt/geo_spgist.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/src/backend/utils/adt/geo_spgist.c b/src/backend/utils/adt/geo_spgist.c
index cbd45b3933..b740e89623 100644
--- a/src/backend/utils/adt/geo_spgist.c
+++ b/src/backend/utils/adt/geo_spgist.c
@@ -472,10 +472,10 @@ spg_box_quad_picksplit(PG_FUNCTION_ARGS)
 		highYs[i] = box->high.y;
 	}
 
-	qsort(lowXs, in->nTuples, sizeof(float8), compareDoubles);
-	qsort(highXs, in->nTuples, sizeof(float8), compareDoubles);
-	qsort(lowYs, in->nTuples, sizeof(float8), compareDoubles);
-	qsort(highYs, in->nTuples, sizeof(float8), compareDoubles);
+	sort_float8_arr(lowXs, in->nTuples);
+	sort_float8_arr(highXs, in->nTuples);
+	sort_float8_arr(lowYs, in->nTuples);
+	sort_float8_arr(highYs, in->nTuples);
 
 	median = in->nTuples / 2;
 
-- 
2.34.1

From d36ac2636e639520f163475a7c08c0cf8b97b866 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Sat, 8 Jun 2024 00:32:44 +0700
Subject: [PATCH v42 05/12] Enhanced Sorting Efficiency for Integer Lists

Refactored the sorting of lists containing integers in the `expand_grouping_sets` function within the `parse_agg.c` file. Replaced the generic sorting function with a custom optimized function tailored for integer types. This change leverages a custom sort template to enhance performance specifically for integer types.

Details:
- Updated the sorting of each groupset individually within the `expand_grouping_sets` function by replacing the loop-based `list_sort` with a single call to `list_int_sort`.
- Updated the comparison function `list_int_cmp` to `int_cmp` within the `expand_grouping_sets` function.
- Updated the `expand_grouping_sets` function to use `sort_list_ints` in two locations where sorting is performed.

This refactor aims to improve sorting efficiency for integer lists in the context of expanding grouping sets within the `parse_agg.c` file, reducing processing time and enhancing overall system performance.
---
 src/backend/parser/parse_agg.c | 3 +--
 1 file changed, 1 insertion(+), 2 deletions(-)

diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c
index bee7d8346a..102131341a 100644
--- a/src/backend/parser/parse_agg.c
+++ b/src/backend/parser/parse_agg.c
@@ -1869,8 +1869,7 @@ expand_grouping_sets(List *groupingSets, bool groupDistinct, int limit)
 		List	   *prev;
 
 		/* Sort each groupset individually */
-		foreach(cell, result)
-			list_sort(lfirst(cell), list_int_cmp);
+		list_int_sort(result);
 
 		/* Now sort the list of groupsets by length and contents */
 		list_sort(result, cmp_list_len_contents_asc);
-- 
2.34.1

From abbca3581624b70709bfcfcaad2343a2d78df78b Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Tue, 11 Jun 2024 12:00:11 +0700
Subject: [PATCH v42 07/12] Consolidate and optimize int16 array sorting

This commit optimizes int16 array sorting by consolidating the
compare_int16 function into a single location and removing duplicate
definitions across multiple files. Additionally, it introduces a
sorting template to enhance sorting performance.

  Changes:
- Consolidated the compare_int16 function into a single location.
- Removed duplicate definitions of compare_int16.
- Introduced a sorting template for int16 arrays to improve performance.
---
 src/backend/catalog/pg_publication.c | 11 ----------
 src/backend/commands/statscmds.c     | 12 ----------
 src/backend/utils/adt/numutils.c     | 33 ++++++++++++++++++++++++++++
 src/include/utils/builtins.h         |  1 +
 4 files changed, 34 insertions(+), 23 deletions(-)

diff --git a/src/backend/catalog/pg_publication.c b/src/backend/catalog/pg_publication.c
index faf70ec8c7..8518582b76 100644
--- a/src/backend/catalog/pg_publication.c
+++ b/src/backend/catalog/pg_publication.c
@@ -476,17 +476,6 @@ publication_add_relation(Oid pubid, PublicationRelInfo *pri,
 	return myself;
 }
 
-/* qsort comparator for attnums */
-static int
-compare_int16(const void *a, const void *b)
-{
-	int			av = *(const int16 *) a;
-	int			bv = *(const int16 *) b;
-
-	/* this can't overflow if int is wider than int16 */
-	return (av - bv);
-}
-
 /*
  * Translate a list of column names to an array of attribute numbers
  * and a Bitmapset with them; verify that each attribute is appropriate
diff --git a/src/backend/commands/statscmds.c b/src/backend/commands/statscmds.c
index 1db3ef69d2..14d9b035b7 100644
--- a/src/backend/commands/statscmds.c
+++ b/src/backend/commands/statscmds.c
@@ -43,18 +43,6 @@ static char *ChooseExtendedStatisticName(const char *name1, const char *name2,
 										 const char *label, Oid namespaceid);
 static char *ChooseExtendedStatisticNameAddition(List *exprs);
 
-
-/* qsort comparator for the attnums in CreateStatistics */
-static int
-compare_int16(const void *a, const void *b)
-{
-	int			av = *(const int16 *) a;
-	int			bv = *(const int16 *) b;
-
-	/* this can't overflow if int is wider than int16 */
-	return (av - bv);
-}
-
 /*
  *		CREATE STATISTICS
  */
diff --git a/src/backend/utils/adt/numutils.c b/src/backend/utils/adt/numutils.c
index adc1e8a4cb..f538d1be2b 100644
--- a/src/backend/utils/adt/numutils.c
+++ b/src/backend/utils/adt/numutils.c
@@ -1312,3 +1312,36 @@ pg_ultostr(char *str, uint32 value)
 
 	return str + len;
 }
+
+/*
+ * compare_int16: Compare two int16 values.
+ *
+ * This function compares two int16 values passed as pointers. It first
+ * dereferences the pointers to obtain the actual int16 values, then
+ * subtracts one from the other to determine their relative ordering.
+ * Note:
+ *   - This function assumes that the underlying architecture represents
+ *     int16 values using a two's complement representation.
+ *   - It does not perform overflow checking, assuming that 'int' is
+ *     wider than 'int16'.
+ */
+static int
+compare_int16(const void *a, const void *b)
+{
+	int			av = *(const int16 *) a;
+	int			bv = *(const int16 *) b;
+
+	/* this can't overflow if int is wider than int16 */
+	return (av - bv);
+}
+
+ /* 
+ * Instantiating a Sorting Template for int16 Arrays
+ * enhancing speed performance.
+ */
+#define ST_SORT sort_int_16_arr
+#define ST_ELEMENT_TYPE int16
+#define ST_COMPARE(a, b) compare_int16(a, b)
+#define ST_SCOPE extern
+#define ST_DEFINE
+#include <lib/sort_template.h>
\ No newline at end of file
diff --git a/src/include/utils/builtins.h b/src/include/utils/builtins.h
index 359c570f23..8ddbb8b142 100644
--- a/src/include/utils/builtins.h
+++ b/src/include/utils/builtins.h
@@ -42,6 +42,7 @@ extern uint64 hex_decode_safe(const char *src, size_t len, char *dst,
 
 /* int.c */
 extern int2vector *buildint2vector(const int16 *int2s, int n);
+extern void sort_int_16_arr(int16 *arr, size_t n);
 
 /* name.c */
 extern void namestrcpy(Name name, const char *str);
-- 
2.34.1

From beb5b92d04075b0539f2a6965f58d6a63ae2898e Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Sat, 8 Jun 2024 00:14:18 +0700
Subject: [PATCH v42 04/12] Optimized Int List Sorting by using template
 sorting algorithm

This commit optimizes the sorting of integer lists by implementing a custom sort template algorithm. It introduces a specialized sorting function, `list_int_sort`, defined through macros and included from `sort_template.h`. The enhancement aims to improve performance by enabling direct comparison of integers and sorting the list in-place.

Changes:
- Defined macros `ST_SORT`, `ST_ELEMENT_TYPE`, `ST_COMPARE`, `ST_SCOPE`, and `ST_DEFINE` for the `list_int_sort` function.
- Included `sort_template.h` to leverage the template-based sorting mechanism.
- Implemented the `list_int_sort` function to efficiently sort integer lists.

This optimization is expected to provide better sorting efficiency for lists containing Ints, contributing to overall system performance improvements.
---
 src/backend/nodes/list.c    | 14 ++++++++++++++
 src/include/nodes/pg_list.h |  1 +
 2 files changed, 15 insertions(+)

diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index e10ce545ad..197ce1b8f4 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -1721,3 +1721,17 @@ list_oid_cmp(const ListCell *p1, const ListCell *p2)
 void list_oid_sort(List *data){
    sort_list_oids(list_head(data), list_length(data));
 }
+
+#define ST_SORT sort_list_ints
+#define ST_ELEMENT_TYPE ListCell
+#define ST_COMPARE(a, b) list_int_cmp(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
+/*
+ * Sort list with int type optimization.
+ */
+void list_int_sort(List *data){
+   sort_list_ints(list_head(data), list_length(data));
+}
\ No newline at end of file
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 88aa1ebea9..7757b1cdf0 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -680,6 +680,7 @@ extern pg_nodiscard List *list_copy_deep(const List *oldlist);
 typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
 extern void list_sort(List *list, list_sort_comparator cmp);
 extern void list_oid_sort(List *list);
+extern void list_int_sort(List *list);
 
 extern int	list_int_cmp(const ListCell *p1, const ListCell *p2);
 extern int	list_oid_cmp(const ListCell *p1, const ListCell *p2);
-- 
2.34.1

From 74bad4bbcff9ea4a9a68f91618c84854dab24701 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Sat, 8 Jun 2024 01:29:42 +0700
Subject: [PATCH v42 06/12] Implemented benchmarking for optimized sorting

This commit adds benchmarking functions to compare the performance of two list sorting operations: bench_int_sort and bench_oid_sort. These functions measure the execution time of sorting lists of integers and OIDs, respectively, using different algorithms (list_sort and custom sorting functions). Random lists of specified sizes are generated, sorted using both methods, and their execution times are recorded. The percentage difference in execution time between the two methods is also calculated. This commit aims to provide insights into the efficiency of the sorting algorithms used.
---
 contrib/Makefile                              |   1 +
 contrib/bench_sort_improvements/Makefile      |  20 ++++
 contrib/bench_sort_improvements/bench.c       | 105 ++++++++++++++++++
 .../bench_sort_improvements--1.0.sql          |   3 +
 .../bench_sort_improvements.control           |   5 +
 5 files changed, 134 insertions(+)
 create mode 100644 contrib/bench_sort_improvements/Makefile
 create mode 100644 contrib/bench_sort_improvements/bench.c
 create mode 100644 contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
 create mode 100644 contrib/bench_sort_improvements/bench_sort_improvements.control

diff --git a/contrib/Makefile b/contrib/Makefile
index abd780f277..a1ee9defc2 100644
--- a/contrib/Makefile
+++ b/contrib/Makefile
@@ -10,6 +10,7 @@ SUBDIRS = \
 		auto_explain	\
 		basic_archive	\
 		basebackup_to_shell	\
+		bench_sort_improvements \
 		bloom		\
 		btree_gin	\
 		btree_gist	\
diff --git a/contrib/bench_sort_improvements/Makefile b/contrib/bench_sort_improvements/Makefile
new file mode 100644
index 0000000000..46458ee76c
--- /dev/null
+++ b/contrib/bench_sort_improvements/Makefile
@@ -0,0 +1,20 @@
+MODULE_big = bench_sort_improvements
+
+OBJS = \
+	$(WIN32RES) \
+	bench.o
+
+EXTENSION = bench_sort_improvements
+
+DATA = bench_sort_improvements--1.0.sql
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = contrib/bench_sort_improvements
+top_builddir = ../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/contrib/bench_sort_improvements/bench.c b/contrib/bench_sort_improvements/bench.c
new file mode 100644
index 0000000000..77d5c7fa37
--- /dev/null
+++ b/contrib/bench_sort_improvements/bench.c
@@ -0,0 +1,105 @@
+#include "postgres.h"
+#include "fmgr.h"
+#include "utils/builtins.h"
+#include "nodes/pg_list.h"
+#include <limits.h>
+#include <time.h>
+
+
+PG_MODULE_MAGIC;
+
+Datum bench_int_sort(PG_FUNCTION_ARGS);
+Datum bench_oid_sort(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(bench_oid_sort);
+PG_FUNCTION_INFO_V1(bench_int_sort);
+
+Datum
+bench_oid_sort(PG_FUNCTION_ARGS)
+{
+    int32 list_size = PG_GETARG_INT32(0);
+    List *list_first = NIL;
+    List *list_second = NIL;
+    Oid random_oid;
+    struct timespec start, end;
+    long time_spent_first;
+    long time_spent_second;
+    double percentage_difference = 0.0;
+    char *result_message;
+
+    for (int i = 0; i < list_size; i++)
+    {
+        random_oid = (Oid) (random() % (UINT_MAX - 1) + 1); 
+        list_first = lappend_oid(list_first, random_oid);
+        list_second = lappend_oid(list_second, random_oid);
+    }
+
+    // Timing the first sort function
+    clock_gettime(CLOCK_MONOTONIC, &start);
+    list_sort(list_first, list_oid_cmp);
+    clock_gettime(CLOCK_MONOTONIC, &end);
+    time_spent_first = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+    // Timing the second sort function
+    clock_gettime(CLOCK_MONOTONIC, &start);
+    list_oid_sort(list_second);
+    clock_gettime(CLOCK_MONOTONIC, &end);
+    time_spent_second = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+    percentage_difference = ((double)(time_spent_first - time_spent_second) / time_spent_first) * 100.0;
+
+    list_free(list_first);
+    list_free(list_second);
+    
+    result_message = psprintf("Time taken by list_sort: %ld ns, Time taken by list_oid_sort: %ld ns, Percentage difference: %.2f%%", 
+                              time_spent_first, time_spent_second, percentage_difference);
+    PG_RETURN_TEXT_P(cstring_to_text(result_message));
+}
+
+Datum
+bench_int_sort(PG_FUNCTION_ARGS)
+{
+    int32 list_size = PG_GETARG_INT32(0);
+    List *list_first = NIL;
+    List *list_second = NIL;
+    int random_int;
+    struct timespec start, end;
+    long time_spent_first;
+    long time_spent_second;
+    double percentage_difference = 0.0;
+    char *result_message;
+
+    for (int i = 0; i < list_size; i++)
+    {
+        random_int = rand(); 
+        list_first = lappend_int(list_first, random_int); 
+        list_second = lappend_int(list_second, random_int); 
+    }
+
+    // Timing the first sort function
+    clock_gettime(CLOCK_MONOTONIC, &start);
+    list_sort(list_first, list_oid_cmp);
+    clock_gettime(CLOCK_MONOTONIC, &end);
+    time_spent_first = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+    // Timing the second sort function
+    clock_gettime(CLOCK_MONOTONIC, &start);
+    list_int_sort(list_second);
+    clock_gettime(CLOCK_MONOTONIC, &end);
+    time_spent_second = (end.tv_sec - start.tv_sec) * 1000000000L + (end.tv_nsec - start.tv_nsec);
+
+    percentage_difference = ((double)(time_spent_first - time_spent_second) / time_spent_first) * 100.0;
+
+    list_free(list_first);
+    list_free(list_second);
+    
+    result_message = psprintf("Time taken by list_sort: %ld ns, Time taken by list_int_sort: %ld ns, Percentage difference: %.2f%%", 
+                              time_spent_first, time_spent_second, percentage_difference);
+    PG_RETURN_TEXT_P(cstring_to_text(result_message));
+}
+
+void
+_PG_init()
+{
+    srand(time(NULL));
+}
\ No newline at end of file
diff --git a/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql b/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
new file mode 100644
index 0000000000..97b75d368d
--- /dev/null
+++ b/contrib/bench_sort_improvements/bench_sort_improvements--1.0.sql
@@ -0,0 +1,3 @@
+create function bench_oid_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_oid_sort' LANGUAGE C;
+
+create function bench_int_sort(integer) returns text AS 'MODULE_PATHNAME', 'bench_int_sort' LANGUAGE C;
diff --git a/contrib/bench_sort_improvements/bench_sort_improvements.control b/contrib/bench_sort_improvements/bench_sort_improvements.control
new file mode 100644
index 0000000000..7dc05056ac
--- /dev/null
+++ b/contrib/bench_sort_improvements/bench_sort_improvements.control
@@ -0,0 +1,5 @@
+# fuzzystrmatch extension
+comment = 'test extension'
+default_version = '1.0'
+module_pathname = '$libdir/bench_sort_improvements'
+relocatable = true
-- 
2.34.1

From d82427a4c1db68c59e1d5a35f25f0391a6ae68e6 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Sat, 8 Jun 2024 00:04:59 +0700
Subject: [PATCH v42 03/12] Enhanced Sorting Efficiency for Oid Lists

Refactored the sorting of lists containing Oids by replacing the generic function
with the custom optimized function. This change leverages a custom sort template
to enhance performance specifically for Oid types.

Details:
- Updated to use instead of.
- Updated to use instead of.
- Updated to use instead of in two locations.

This refactor aims to improve sorting efficiency for Oid lists, reducing
processing time and enhancing overall system performance.
---
 src/backend/catalog/heap.c           | 2 +-
 src/backend/catalog/pg_publication.c | 2 +-
 src/backend/utils/cache/relcache.c   | 4 ++--
 3 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/src/backend/catalog/heap.c b/src/backend/catalog/heap.c
index a122bbffce..88e4ada970 100644
--- a/src/backend/catalog/heap.c
+++ b/src/backend/catalog/heap.c
@@ -3303,7 +3303,7 @@ restart:
 	list_free(oids);
 
 	/* Now sort and de-duplicate the result list */
-	list_sort(result, list_oid_cmp);
+	list_oid_sort(result);
 	list_deduplicate_oid(result);
 
 	return result;
diff --git a/src/backend/catalog/pg_publication.c b/src/backend/catalog/pg_publication.c
index 0602398a54..faf70ec8c7 100644
--- a/src/backend/catalog/pg_publication.c
+++ b/src/backend/catalog/pg_publication.c
@@ -746,7 +746,7 @@ GetPublicationRelations(Oid pubid, PublicationPartOpt pub_partopt)
 	table_close(pubrelsrel, AccessShareLock);
 
 	/* Now sort and de-duplicate the result list */
-	list_sort(result, list_oid_cmp);
+	list_oid_sort(result);
 	list_deduplicate_oid(result);
 
 	return result;
diff --git a/src/backend/utils/cache/relcache.c b/src/backend/utils/cache/relcache.c
index 35dbb87ae3..21b3f3c92f 100644
--- a/src/backend/utils/cache/relcache.c
+++ b/src/backend/utils/cache/relcache.c
@@ -4873,7 +4873,7 @@ RelationGetIndexList(Relation relation)
 	table_close(indrel, AccessShareLock);
 
 	/* Sort the result list into OID order, per API spec. */
-	list_sort(result, list_oid_cmp);
+	list_oid_sort(result);
 
 	/* Now save a copy of the completed list in the relcache entry. */
 	oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
@@ -4965,7 +4965,7 @@ RelationGetStatExtList(Relation relation)
 	table_close(indrel, AccessShareLock);
 
 	/* Sort the result list into OID order, per API spec. */
-	list_sort(result, list_oid_cmp);
+	list_oid_sort(result);
 
 	/* Now save a copy of the completed list in the relcache entry. */
 	oldcxt = MemoryContextSwitchTo(CacheMemoryContext);
-- 
2.34.1

From 530911dd2e1a60209421551bc24b5d72628050e5 Mon Sep 17 00:00:00 2001
From: "Andrey M. Borodin" <[email-masked]>
Date: Sat, 18 May 2024 23:02:50 +0500
Subject: [PATCH v42 01/12] Use specialized sort facilities

---
 contrib/intarray/_int.h      | 12 ------------
 contrib/intarray/_int_gist.c |  2 +-
 contrib/intarray/_int_op.c   | 19 +++++++++----------
 contrib/intarray/_int_tool.c | 12 ------------
 src/include/port.h           |  2 ++
 src/port/qsort.c             | 35 +++++++++++++++++++++++++++++++++++
 6 files changed, 47 insertions(+), 35 deletions(-)

diff --git a/contrib/intarray/_int.h b/contrib/intarray/_int.h
index 0352cbd368..5225c9090a 100644
--- a/contrib/intarray/_int.h
+++ b/contrib/intarray/_int.h
@@ -176,16 +176,4 @@ bool		execconsistent(QUERYTYPE *query, ArrayType *array, bool calcnot);
 bool		gin_bool_consistent(QUERYTYPE *query, bool *check);
 bool		query_has_required_values(QUERYTYPE *query);
 
-int			compASC(const void *a, const void *b);
-int			compDESC(const void *a, const void *b);
-
-/* sort, either ascending or descending */
-#define QSORT(a, direction) \
-	do { \
-		int		_nelems_ = ARRNELEMS(a); \
-		if (_nelems_ > 1) \
-			qsort((void*) ARRPTR(a), _nelems_, sizeof(int32), \
-				  (direction) ? compASC : compDESC ); \
-	} while(0)
-
 #endif							/* ___INT_H__ */
diff --git a/contrib/intarray/_int_gist.c b/contrib/intarray/_int_gist.c
index a09b7fa812..d39e40c66a 100644
--- a/contrib/intarray/_int_gist.c
+++ b/contrib/intarray/_int_gist.c
@@ -150,7 +150,7 @@ g_int_union(PG_FUNCTION_ARGS)
 		ptr += nel;
 	}
 
-	QSORT(res, 1);
+	sort_int32_asc(ARRPTR(res), ARRNELEMS(res));
 	res = _int_unique(res);
 	*size = VARSIZE(res);
 	PG_RETURN_POINTER(res);
diff --git a/contrib/intarray/_int_op.c b/contrib/intarray/_int_op.c
index 5b164f6788..34d3aa183f 100644
--- a/contrib/intarray/_int_op.c
+++ b/contrib/intarray/_int_op.c
@@ -198,7 +198,6 @@ sort(PG_FUNCTION_ARGS)
 	text	   *dirstr = (fcinfo->nargs == 2) ? PG_GETARG_TEXT_PP(1) : NULL;
 	int32		dc = (dirstr) ? VARSIZE_ANY_EXHDR(dirstr) : 0;
 	char	   *d = (dirstr) ? VARDATA_ANY(dirstr) : NULL;
-	int			dir = -1;
 
 	CHECKARRVALID(a);
 	if (ARRNELEMS(a) < 2)
@@ -208,18 +207,18 @@ sort(PG_FUNCTION_ARGS)
 						   && (d[0] == 'A' || d[0] == 'a')
 						   && (d[1] == 'S' || d[1] == 's')
 						   && (d[2] == 'C' || d[2] == 'c')))
-		dir = 1;
+		sort_int32_asc(ARRPTR(a), ARRNELEMS(a));
 	else if (dc == 4
 			 && (d[0] == 'D' || d[0] == 'd')
 			 && (d[1] == 'E' || d[1] == 'e')
 			 && (d[2] == 'S' || d[2] == 's')
 			 && (d[3] == 'C' || d[3] == 'c'))
-		dir = 0;
-	if (dir == -1)
+		sort_int32_desc(ARRPTR(a), ARRNELEMS(a));
+	else
 		ereport(ERROR,
 				(errcode(ERRCODE_INVALID_PARAMETER_VALUE),
 				 errmsg("second parameter must be \"ASC\" or \"DESC\"")));
-	QSORT(a, dir);
+
 	PG_RETURN_POINTER(a);
 }
 
@@ -229,7 +228,7 @@ sort_asc(PG_FUNCTION_ARGS)
 	ArrayType  *a = PG_GETARG_ARRAYTYPE_P_COPY(0);
 
 	CHECKARRVALID(a);
-	QSORT(a, 1);
+	sort_int32_asc(ARRPTR(a), ARRNELEMS(a));
 	PG_RETURN_POINTER(a);
 }
 
@@ -239,7 +238,7 @@ sort_desc(PG_FUNCTION_ARGS)
 	ArrayType  *a = PG_GETARG_ARRAYTYPE_P_COPY(0);
 
 	CHECKARRVALID(a);
-	QSORT(a, 0);
+	sort_int32_desc(ARRPTR(a), ARRNELEMS(a));
 	PG_RETURN_POINTER(a);
 }
 
@@ -381,7 +380,7 @@ intset_union_elem(PG_FUNCTION_ARGS)
 
 	result = intarray_add_elem(a, PG_GETARG_INT32(1));
 	PG_FREE_IF_COPY(a, 0);
-	QSORT(result, 1);
+	sort_int32_asc(ARRPTR(result), ARRNELEMS(result));
 	PG_RETURN_POINTER(_int_unique(result));
 }
 
@@ -403,10 +402,10 @@ intset_subtract(PG_FUNCTION_ARGS)
 	CHECKARRVALID(a);
 	CHECKARRVALID(b);
 
-	QSORT(a, 1);
+	sort_int32_asc(ARRPTR(a), ARRNELEMS(a));
 	a = _int_unique(a);
 	ca = ARRNELEMS(a);
-	QSORT(b, 1);
+	sort_int32_asc(ARRPTR(b), ARRNELEMS(b));
 	b = _int_unique(b);
 	cb = ARRNELEMS(b);
 	result = new_intArrayType(ca);
diff --git a/contrib/intarray/_int_tool.c b/contrib/intarray/_int_tool.c
index c85280c842..e83c6aadc6 100644
--- a/contrib/intarray/_int_tool.c
+++ b/contrib/intarray/_int_tool.c
@@ -393,15 +393,3 @@ int_to_intset(int32 elem)
 	aa[0] = elem;
 	return result;
 }
-
-int
-compASC(const void *a, const void *b)
-{
-	return pg_cmp_s32(*(const int32 *) a, *(const int32 *) b);
-}
-
-int
-compDESC(const void *a, const void *b)
-{
-	return pg_cmp_s32(*(const int32 *) b, *(const int32 *) a);
-}
diff --git a/src/include/port.h b/src/include/port.h
index ae115d2d97..b48194cb00 100644
--- a/src/include/port.h
+++ b/src/include/port.h
@@ -445,6 +445,8 @@ extern bool pg_get_user_home_dir(uid_t user_id, char *buffer, size_t buflen);
 extern void pg_qsort(void *base, size_t nel, size_t elsize,
 					 int (*cmp) (const void *, const void *));
 extern int	pg_qsort_strcmp(const void *a, const void *b);
+extern void sort_int32_asc(int32 *base, size_t nel);
+extern void sort_int32_desc(int32 *base, size_t nel);
 
 #define qsort(a,b,c,d) pg_qsort(a,b,c,d)
 
diff --git a/src/port/qsort.c b/src/port/qsort.c
index 7879e6cd56..5175c8a6dd 100644
--- a/src/port/qsort.c
+++ b/src/port/qsort.c
@@ -20,3 +20,38 @@ pg_qsort_strcmp(const void *a, const void *b)
 {
 	return strcmp(*(const char *const *) a, *(const char *const *) b);
 }
+
+static inline int
+sort_int32_asc_cmp(int32* a, int32* b)
+{
+	if (*a < *b)
+		return -1;
+	if (*a > *b)
+		return 1;
+	return 0;
+}
+
+#define ST_SORT sort_int32_asc
+#define ST_ELEMENT_TYPE int32
+#define ST_COMPARE sort_int32_asc_cmp
+#define ST_SCOPE
+#define ST_DECLARE
+#define ST_DEFINE
+#include "lib/sort_template.h"
+
+static inline int
+sort_int32_desc_cmp(int32* a, int32* b)
+{
+	if (*a < *b)
+		return 1;
+	if (*a > *b)
+		return -1;
+	return 0;
+}
+#define ST_SORT sort_int32_desc
+#define ST_ELEMENT_TYPE int32
+#define ST_COMPARE sort_int32_desc_cmp
+#define ST_SCOPE
+#define ST_DECLARE
+#define ST_DEFINE
+#include "lib/sort_template.h"
-- 
2.34.1

From 32f967a10a2dd6a9f68aa85717ab11ab83f03298 Mon Sep 17 00:00:00 2001
From: Stepan Neretin <[email-masked]>
Date: Sat, 8 Jun 2024 00:04:42 +0700
Subject: [PATCH v42 02/12] Optimized Oid List Sorting by using template
 sorting algorithm

Optimized the sorting of lists containing Oids by utilizing a custom sort template. This enhancement introduces a specialized sorting function sort_list_oids defined through macros and included from sort_template.h. The new function improves performance by directly comparing Oids and sorting the list in-place.

Changes:
- Defined ST_SORT, ST_ELEMENT_TYPE, ST_COMPARE, ST_SCOPE, and ST_DEFINE macros for sort_list_oids.
- Included sort_template.h to leverage the template-based sorting mechanism.
- Implemented list_oid_sort function to sort lists with Oid type.

This optimization is expected to provide better sorting efficiency for lists containing Oids, contributing to overall system performance improvements.
---
 src/backend/nodes/list.c    | 14 ++++++++++++++
 src/include/nodes/pg_list.h |  1 +
 2 files changed, 15 insertions(+)

diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index e2615ab105..e10ce545ad 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -1707,3 +1707,17 @@ list_oid_cmp(const ListCell *p1, const ListCell *p2)
 
 	return pg_cmp_u32(v1, v2);
 }
+
+#define ST_SORT sort_list_oids
+#define ST_ELEMENT_TYPE ListCell
+#define ST_COMPARE(a, b) list_oid_cmp(a, b)
+#define ST_SCOPE static
+#define ST_DEFINE
+#include <lib/sort_template.h>
+
+/*
+ * Sort list with Oid type optimization.
+ */
+void list_oid_sort(List *data){
+   sort_list_oids(list_head(data), list_length(data));
+}
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 52df93759f..88aa1ebea9 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -679,6 +679,7 @@ extern pg_nodiscard List *list_copy_deep(const List *oldlist);
 
 typedef int (*list_sort_comparator) (const ListCell *a, const ListCell *b);
 extern void list_sort(List *list, list_sort_comparator cmp);
+extern void list_oid_sort(List *list);
 
 extern int	list_int_cmp(const ListCell *p1, const ListCell *p2);
 extern int	list_oid_cmp(const ListCell *p1, const ListCell *p2);
-- 
2.34.1