pg.ddx.io pgsql-general@postgresql.org mailing list archive
help / color / mirror / Atom feed From: Martin Kalcher <martin.kalcher@aboutsource.net>
To: Tom Lane <tgl@sss.pgh.pa.us>
To: John Naylor <john.naylor@enterprisedb.com>
Cc: Thomas Munro <thomas.munro@gmail.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: [PATCH] Introduce array_shuffle() and array_sample()
Date: Mon, 18 Jul 2022 21:03:35 +0200
Message-ID: <1708d95a-629e-5ac5-deab-d20a8d0b2b0e@aboutsource.net> (raw )
In-Reply-To: <687490.1658152096@sss.pgh.pa.us >
References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net >
<CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com >
<b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net >
<4073858.1658027909@sss.pgh.pa.us >
<4077925.1658029046@sss.pgh.pa.us >
<CA+hUKGLcjrJ9Q2OZAKHN-SQyq_m5QDv8d3WKHYq5HW8Lyozu4w@mail.gmail.com >
<5ef15c6f-e108-53af-3d82-587fac394f1a@aboutsource.net >
<463181.1658097987@sss.pgh.pa.us >
<5b7a1ee9-f942-2502-3a0c-e9fc12511139@aboutsource.net >
<469954.1658100033@sss.pgh.pa.us >
<f36445ec-aad9-0531-39f8-ca3a3bb4860e@aboutsource.net >
<CAFBsxsG_PK3BkhMcfeLmwDS+FBDZKAaUtfrb6KjU79FZ-3H46A@mail.gmail.com >
<687490.1658152096@sss.pgh.pa.us >
Thanks for all your feedback and help. I got a patch that i consider
ready for review. It introduces two new functions:
array_shuffle(anyarray) -> anyarray
array_sample(anyarray, integer) -> anyarray
array_shuffle() shuffles an array (obviously). array_sample() picks n
random elements from an array.
Is someone interested in looking at it? What are the next steps?
Martin
Attachments:
0001-Introduce-array_shuffle-and-array_sample.patch (text/x-patch, 9.0K) download
From 5498bb2d9f1fab4cad56cd0d3a6eeafa24a26c8e Mon Sep 17 00:00:00 2001
From: Martin Kalcher <martin.kalcher@aboutsource.net>
Date: Sun, 17 Jul 2022 18:06:04 +0200
Subject: [PATCH] Introduce array_shuffle() and array_sample()
* array_shuffle() shuffles to elements of an array.
* array_sample() chooses n elements from an array by random.
Shuffling of arrays can already be accomplished with SQL
using unnest() and array_agg(order by random()). But that is
very slow compared to the new functions.
---
doc/src/sgml/func.sgml | 34 ++++++
src/backend/utils/adt/arrayfuncs.c | 163 +++++++++++++++++++++++++++
src/include/catalog/pg_proc.dat | 6 +
src/test/regress/expected/arrays.out | 30 +++++
src/test/regress/sql/arrays.sql | 11 ++
5 files changed, 244 insertions(+)
diff --git a/doc/src/sgml/func.sgml b/doc/src/sgml/func.sgml
index b6783b7ad0..c676031b4a 100644
--- a/doc/src/sgml/func.sgml
+++ b/doc/src/sgml/func.sgml
@@ -19395,6 +19395,40 @@ SELECT NULLIF(value, '(none)') ...
</para></entry>
</row>
+ <row>
+ <entry role="func_table_entry"><para role="func_signature">
+ <indexterm>
+ <primary>array_sample</primary>
+ </indexterm>
+ <function>array_sample</function> ( <parameter>array</parameter> <type>anyarray</type>, <parameter>n</parameter> <type>integer</type> )
+ <returnvalue>anyarray</returnvalue>
+ </para>
+ <para>
+ Returns <parameter>n</parameter> randomly chosen elements from <parameter>array</parameter>.
+ </para>
+ <para>
+ <literal>array_sample(ARRAY[1,2,3,4,5,6], 3)</literal>
+ <returnvalue>{4,5,1}</returnvalue>
+ </para></entry>
+ </row>
+
+ <row>
+ <entry role="func_table_entry"><para role="func_signature">
+ <indexterm>
+ <primary>array_shuffle</primary>
+ </indexterm>
+ <function>array_shuffle</function> ( <type>anyarray</type> )
+ <returnvalue>anyarray</returnvalue>
+ </para>
+ <para>
+ Shuffles the elements of the array.
+ </para>
+ <para>
+ <literal>array_shuffle(ARRAY[1,2,3,4,5,6])</literal>
+ <returnvalue>{4,5,1,3,2,6}</returnvalue>
+ </para></entry>
+ </row>
+
<row>
<entry role="func_table_entry"><para role="func_signature">
<indexterm id="function-array-to-string">
diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c
index fb167f226a..a6769a8ebf 100644
--- a/src/backend/utils/adt/arrayfuncs.c
+++ b/src/backend/utils/adt/arrayfuncs.c
@@ -6872,3 +6872,166 @@ trim_array(PG_FUNCTION_ARGS)
PG_RETURN_DATUM(result);
}
+
+/*
+ * Shuffle the elements of an array.
+ */
+Datum
+array_shuffle(PG_FUNCTION_ARGS)
+{
+ ArrayType *array,
+ *result;
+ int16 elmlen;
+ bool elmbyval;
+ char elmalign;
+ Oid elmtyp;
+ TypeCacheEntry *typentry;
+ Datum *elms,
+ elm;
+ bool *nuls,
+ nul;
+ int nelms,
+ i,
+ j;
+
+ array = PG_GETARG_ARRAYTYPE_P(0);
+ nelms = ArrayGetNItems(ARR_NDIM(array), ARR_DIMS(array));
+
+ /* There is no point in shuffling arrays with less then two elements. */
+ if (nelms < 2)
+ PG_RETURN_ARRAYTYPE_P(array);
+
+ elmtyp = ARR_ELEMTYPE(array);
+ typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+
+ if (typentry == NULL || typentry->type_id != elmtyp)
+ {
+ typentry = lookup_type_cache(elmtyp, 0);
+ fcinfo->flinfo->fn_extra = (void *) typentry;
+ }
+ elmlen = typentry->typlen;
+ elmbyval = typentry->typbyval;
+ elmalign = typentry->typalign;
+
+ deconstruct_array(array, elmtyp, elmlen, elmbyval, elmalign,
+ &elms, &nuls, &nelms);
+
+ /* Shuffle elements and nulls using Fisher-Yates shuffle algorithm. */
+ for (i = nelms - 1; i > 0; i--)
+ {
+ j = random() % (i + 1);
+ elm = elms[i];
+ nul = nuls[i];
+ elms[i] = elms[j];
+ nuls[i] = nuls[j];
+ elms[j] = elm;
+ nuls[j] = nul;
+ }
+
+ result = construct_md_array(elms, nuls,
+ ARR_NDIM(array), ARR_DIMS(array), ARR_LBOUND(array),
+ elmtyp, elmlen, elmbyval, elmalign);
+
+ pfree(elms);
+ pfree(nuls);
+ PG_FREE_IF_COPY(array, 0);
+
+ PG_RETURN_ARRAYTYPE_P(result);
+}
+
+/*
+ * Choose N random elements from an array.
+ */
+Datum
+array_sample(PG_FUNCTION_ARGS)
+{
+ ArrayType *array,
+ *result;
+ int16 elmlen;
+ bool elmbyval;
+ char elmalign;
+ Oid elmtyp;
+ TypeCacheEntry *typentry;
+ Datum *elms,
+ elm;
+ bool *nuls,
+ nul;
+ int nelms,
+ rnelms,
+ rdims[1],
+ rlbs[1],
+ i,
+ j;
+
+ array = PG_GETARG_ARRAYTYPE_P(0);
+ nelms = ArrayGetNItems(ARR_NDIM(array), ARR_DIMS(array));
+ elmtyp = ARR_ELEMTYPE(array);
+ rnelms = PG_GETARG_INT32(1);
+
+ if (rnelms < 0)
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("second parameter must not be negative")));
+
+ /* Return an empty array if the requested sample size is zero. */
+ if (rnelms == 0)
+ {
+ PG_FREE_IF_COPY(array, 0);
+ PG_RETURN_ARRAYTYPE_P(construct_empty_array(elmtyp));
+ }
+
+ /*
+ * Return the original array if the requested sample size is greater than
+ * or equal to its own size.
+ */
+ if (rnelms >= nelms)
+ PG_RETURN_ARRAYTYPE_P(array);
+
+ typentry = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
+
+ if (typentry == NULL || typentry->type_id != elmtyp)
+ {
+ typentry = lookup_type_cache(elmtyp, 0);
+ fcinfo->flinfo->fn_extra = (void *) typentry;
+ }
+ elmlen = typentry->typlen;
+ elmbyval = typentry->typbyval;
+ elmalign = typentry->typalign;
+
+ deconstruct_array(array, elmtyp, elmlen, elmbyval, elmalign,
+ &elms, &nuls, &nelms);
+
+ /*
+ * Move rnelms (requested sample size) randomly-chosen elements to the
+ * beginning of the array, using the Fisher-Yates shuffle algorithm.
+ */
+ for (i = 0; i < rnelms; i++)
+ {
+ /* random j such that i <= j < nelms */
+ j = (random() % (nelms - i)) + i;
+ elm = elms[i];
+ nul = nuls[i];
+ elms[i] = elms[j];
+ nuls[i] = nuls[j];
+ elms[j] = elm;
+ nuls[j] = nul;
+ }
+
+ /*
+ * Construct a new array from the first rnelms (requested sample size)
+ * elements of the shuffled array. Even though we are constructing a
+ * one-dimensional array, we cannot use construct_array(), because it does
+ * not support NULL elements.
+ */
+ rdims[0] = rnelms;
+ rlbs[0] = 1;
+
+ result = construct_md_array(elms, nuls, 1, rdims, rlbs,
+ elmtyp, elmlen, elmbyval, elmalign);
+
+ pfree(elms);
+ pfree(nuls);
+ PG_FREE_IF_COPY(array, 0);
+
+ PG_RETURN_ARRAYTYPE_P(result);
+}
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 2e41f4d9e8..f51af5ee9f 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1681,6 +1681,12 @@
proname => 'arraycontjoinsel', provolatile => 's', prorettype => 'float8',
proargtypes => 'internal oid internal int2 internal',
prosrc => 'arraycontjoinsel' },
+{ oid => '8464', descr => 'shuffle array',
+ proname => 'array_shuffle', proisstrict => 't', prorettype => 'anyarray',
+ proargtypes => 'anyarray', prosrc => 'array_shuffle' },
+{ oid => '8465', descr => 'take samples from array',
+ proname => 'array_sample', proisstrict => 't', prorettype => 'anyarray',
+ proargtypes => 'anyarray int4', prosrc => 'array_sample' },
{ oid => '764', descr => 'large object import',
proname => 'lo_import', provolatile => 'v', proparallel => 'u',
diff --git a/src/test/regress/expected/arrays.out b/src/test/regress/expected/arrays.out
index ce6f3a65f9..4994e6ac62 100644
--- a/src/test/regress/expected/arrays.out
+++ b/src/test/regress/expected/arrays.out
@@ -2445,3 +2445,33 @@ SELECT trim_array(ARRAY[1, 2, 3], -1); -- fail
ERROR: number of elements to trim must be between 0 and 3
SELECT trim_array(ARRAY[1, 2, 3], 10); -- fail
ERROR: number of elements to trim must be between 0 and 3
+-- array_shuffle
+SELECT array_agg(a order by a)
+FROM
+(SELECT unnest(array_shuffle('{NULL,1,2,3,4,5}'::int[]))) v(a);
+ array_agg
+------------------
+ {1,2,3,4,5,NULL}
+(1 row)
+
+-- array_sample
+SELECT cardinality(array_sample('{NULL,1,2,3,4,5}'::int[], 3));
+ cardinality
+-------------
+ 3
+(1 row)
+
+SELECT array_sample('{1,2,3,4,5}'::int[], 3) <@ '{1,2,3,4,5}'::int[];
+ ?column?
+----------
+ t
+(1 row)
+
+SELECT array_sample('{1,2,3,4,5}'::int[], 10);
+ array_sample
+--------------
+ {1,2,3,4,5}
+(1 row)
+
+SELECT array_sample('{1,2,3,4,5}'::int[], -1); -- fail
+ERROR: second parameter must not be negative
diff --git a/src/test/regress/sql/arrays.sql b/src/test/regress/sql/arrays.sql
index f774faf856..0234aafa06 100644
--- a/src/test/regress/sql/arrays.sql
+++ b/src/test/regress/sql/arrays.sql
@@ -754,3 +754,14 @@ FROM
SELECT trim_array(ARRAY[1, 2, 3], -1); -- fail
SELECT trim_array(ARRAY[1, 2, 3], 10); -- fail
+
+-- array_shuffle
+SELECT array_agg(a order by a)
+FROM
+(SELECT unnest(array_shuffle('{NULL,1,2,3,4,5}'::int[]))) v(a);
+
+-- array_sample
+SELECT cardinality(array_sample('{NULL,1,2,3,4,5}'::int[], 3));
+SELECT array_sample('{1,2,3,4,5}'::int[], 3) <@ '{1,2,3,4,5}'::int[];
+SELECT array_sample('{1,2,3,4,5}'::int[], 10);
+SELECT array_sample('{1,2,3,4,5}'::int[], -1); -- fail
--
2.37.1
view thread (51+ messages) latest in thread
Message-ID: <1708d95a-629e-5ac5-deab-d20a8d0b2b0e@aboutsource.net>
Permalink: ../1708d95a-629e-5ac5-deab-d20a8d0b2b0e@aboutsource.net/
Also on: postgresql.org/message-id/1708d95a-629e-5ac5-deab-d20a8d0b2b0e@aboutsource.net
copy link · copy postgr.es · copy git am
reply Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-general@postgresql.org
Cc: martin.kalcher@aboutsource.net, tgl@sss.pgh.pa.us, john.naylor@enterprisedb.com, thomas.munro@gmail.com, pgsql-hackers@lists.postgresql.org
Subject: Re: [PATCH] Introduce array_shuffle() and array_sample()
In-Reply-To: <1708d95a-629e-5ac5-deab-d20a8d0b2b0e@aboutsource.net>
References: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net> <CA+hUKGJFYY6s4nxDRz+PTLNYeUkZJJn_7+iMJoaQeRp5hKz0aQ@mail.gmail.com> <b8f44b53-02d6-0be4-42df-cb6f737e6267@aboutsource.net> <4073858.1658027909@sss.pgh.pa.us> <4077925.1658029046@sss.pgh.pa.us> <CA+hUKGLcjrJ9Q2OZAKHN-SQyq_m5QDv8d3WKHYq5HW8Lyozu4w@mail.gmail.com> <5ef15c6f-e108-53af-3d82-587fac394f1a@aboutsource.net> <463181.1658097987@sss.pgh.pa.us> <5b7a1ee9-f942-2502-3a0c-e9fc12511139@aboutsource.net> <469954.1658100033@sss.pgh.pa.us> <f36445ec-aad9-0531-39f8-ca3a3bb4860e@aboutsource.net> <CAFBsxsG_PK3BkhMcfeLmwDS+FBDZKAaUtfrb6KjU79FZ-3H46A@mail.gmail.com> <687490.1658152096@sss.pgh.pa.us> <1708d95a-629e-5ac5-deab-d20a8d0b2b0e@aboutsource.net>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox