pg.ddx.io pgsql-general@postgresql.org mailing list archive
help / color / mirror / Atom feedProposal to introduce a shuffle function to intarray extension
25+ messages / 6 participants
[nested] [flat]
Commits from this thread:
2023-04-07 888f2ea0a8 Add array_sample() and array_shuffle() functions.
* Proposal to introduce a shuffle function to intarray extension
@ 2022-07-15 08:36 Martin Kalcher <martin.kalcher@aboutsource.net>
0 siblings, 2 replies; 25+ messages in thread
From: Martin Kalcher @ 2022-07-15 08:36 UTC (permalink / raw)
To: pgsql-general@lists.postgresql.org
Dear list,
i am dealing with an application that processes fairly large arrays of
integers. It makes heavy use of the intarray extension, which works
great in most cases. However, there are two requirements that cannot be
addressed by the extension and are rather slow with plain SQL. Both can
be met with shuffling:
- Taking n random members from an integer array
- Splitting an array into n chunks, where each member is assigned to a
random chunk
Shuffling is currently implemented by unnesting the array, ordering the
members by random() and aggregating them again.
create table numbers (arr int[]);
insert into numbers (arr)
select array_agg(i)
from generate_series(1, 4000000) i;
select arr[1:3]::text || ' ... ' || arr[3999998:4000000]::text
from (
select array_agg(n order by random()) arr
from (
select unnest(arr) n from numbers
) plain
) shuffled;
---------------------------------------------------------
{2717290,3093757,2426384} ... {3011871,1402540,1613647}
Time: 2348.961 ms (00:02.349)
I wrote a small extension (see source code below) to see how much we can
gain, when the shuffling is implemented in C and the results speak for
themselves:
select arr[1:3]::text || ' ... ' || arr[3999998:4000000]::text
from (
select shuffle(arr) arr from numbers
) shuffled;
----------------------------------------------------
{1313971,3593627,86630} ... {50764,430410,3901128}
Time: 132.151 ms
I would like to see a function like this inside the intarray extension.
Is there any way to get to this point? How is the process to deal with
such proposals?
Best regards,
Martin Kalcher
Source code of extension mentioned above:
#include "postgres.h"
#include "port.h"
#include "utils/array.h"
PG_MODULE_MAGIC;
PG_FUNCTION_INFO_V1(shuffle);
void _shuffle(int32 *a, int len);
Datum
shuffle(PG_FUNCTION_ARGS)
{
ArrayType *a = PG_GETARG_ARRAYTYPE_P_COPY(0);
int len;
if (array_contains_nulls(a))
ereport(ERROR,
(errcode(ERRCODE_NULL_VALUE_NOT_ALLOWED),
errmsg("array must not contain nulls")));
len = ArrayGetNItems(ARR_NDIM(a), ARR_DIMS(a));
if (len > 1)
_shuffle((int32 *) ARR_DATA_PTR(a), len);
PG_RETURN_POINTER(a);
}
void
_shuffle(int32 *a, int len) {
int i, j;
int32 tmp;
for (i = len - 1; i > 0; i--) {
j = random() % (i + 1);
tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-16 16:53 Mladen Gogala <gogala.mladen@gmail.com>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
1 sibling, 1 reply; 25+ messages in thread
From: Mladen Gogala @ 2022-07-16 16:53 UTC (permalink / raw)
To: pgsql-general@lists.postgresql.org
On 7/15/22 04:36, Martin Kalcher wrote:
> Dear list,
>
> i am dealing with an application that processes fairly large arrays of
> integers. It makes heavy use of the intarray extension, which works
> great in most cases. However, there are two requirements that cannot
> be addressed by the extension and are rather slow with plain SQL. Both
> can be met with shuffling:
>
> - Taking n random members from an integer array
> - Splitting an array into n chunks, where each member is assigned to a
> random chunk
>
> Shuffling is currently implemented by unnesting the array, ordering
> the members by random() and aggregating them again.
Martin, have you considered PL/Python and NumPy module?
--
Mladen Gogala
Database Consultant
Tel: (347) 321-1217
https://dbwhisperer.wordpress.com
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-16 20:21 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Mladen Gogala <gogala.mladen@gmail.com>
0 siblings, 1 reply; 25+ messages in thread
From: Martin Kalcher @ 2022-07-16 20:21 UTC (permalink / raw)
To: Mladen Gogala <gogala.mladen@gmail.com>; pgsql-general@lists.postgresql.org
Am 16.07.22 um 18:53 schrieb Mladen Gogala:
> On 7/15/22 04:36, Martin Kalcher wrote:
>> Dear list,
>>
>> i am dealing with an application that processes fairly large arrays of
>> integers. It makes heavy use of the intarray extension, which works
>> great in most cases. However, there are two requirements that cannot
>> be addressed by the extension and are rather slow with plain SQL. Both
>> can be met with shuffling:
>>
>> - Taking n random members from an integer array
>> - Splitting an array into n chunks, where each member is assigned to a
>> random chunk
>>
>> Shuffling is currently implemented by unnesting the array, ordering
>> the members by random() and aggregating them again.
>
>
> Martin, have you considered PL/Python and NumPy module?
Hey Mladen,
thank you for your advice. Unfortunately the performance of shuffling
with NumPy is about the same as with SQL.
create function numpy_shuffle(arr int[])
returns int[]
as $$
import numpy
numpy.random.shuffle(arr)
return arr
$$ language 'plpython3u';
select arr[1:3]::text || ' ... ' || arr[3999998:4000000]::text
from (
select numpy_shuffle(arr) arr from numbers
) shuffled;
-------------------------------------------------------
{674026,3306457,1727170} ... {343875,3825484,1235246}
Time: 2315.431 ms (00:02.315)
Am i doing something wrong?
Martin
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-16 21:30 Mladen Gogala <gogala.mladen@gmail.com>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
0 siblings, 0 replies; 25+ messages in thread
From: Mladen Gogala @ 2022-07-16 21:30 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; pgsql-general@lists.postgresql.org
On 7/16/22 16:21, Martin Kalcher wrote:
> Hey Mladen,
>
> thank you for your advice. Unfortunately the performance of shuffling
> with NumPy is about the same as with SQL.
>
> create function numpy_shuffle(arr int[])
> returns int[]
> as $$
> import numpy
> numpy.random.shuffle(arr)
> return arr
> $$ language 'plpython3u';
>
> select arr[1:3]::text || ' ... ' || arr[3999998:4000000]::text
> from (
> select numpy_shuffle(arr) arr from numbers
> ) shuffled;
>
> -------------------------------------------------------
> {674026,3306457,1727170} ... {343875,3825484,1235246}
>
> Time: 2315.431 ms (00:02.315)
>
> Am i doing something wrong?
>
> Martin
Hi Martin,
No, you're doing everything right. I have no solution for you. You may
need to do some C programming or throw a stronger hardware at the
problem. The performance of your processors may be the problem. Good luck!
--
Mladen Gogala
Database Consultant
Tel: (347) 321-1217
https://dbwhisperer.wordpress.com
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-16 21:56 Thomas Munro <thomas.munro@gmail.com>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
1 sibling, 1 reply; 25+ messages in thread
From: Thomas Munro @ 2022-07-16 21:56 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Fri, Jul 15, 2022 at 8:36 PM Martin Kalcher
<martin.kalcher@aboutsource.net> wrote:
> I would like to see a function like this inside the intarray extension.
> Is there any way to get to this point? How is the process to deal with
> such proposals?
Hi Martin,
I'm redirecting this to the pgsql-hackers@ mailing list, where we talk
about code. For the archives, Martin's initial message to -general
was:
https://www.postgresql.org/message-id/9d160a44-7675-51e8-60cf-6d64b76db831%40aboutsource.net
The first question is whether such a thing belongs in an external
extension, or in the contrib/intarray module. The latter seems like a
reasonable thing to want to me. The first step towards that will be
to get your code into .patch format, as in git format-patch or git
diff, that can be applied to the master branch.
https://wiki.postgresql.org/wiki/Submitting_a_Patch
Some initial feedback from me: I'd recommend adding a couple of
comments to the code, like the algorithm name for someone who wants to
read more about it (I think it's a Fisher-Yates shuffle?). You'll
need to have the contrib/intarrays/intarray--1.5--1.6.sql file that
creates the function. You might want to add something to
control/intarray/sql/_int.sql that invokes the function when you run
make check in there (but doesn't display the results, since that'd be
unstable across machines?), just to have 'code coverage' (I mean, it'd
prove it doesn't crash at least). Once details are settled, you'd
also want to add documentation in doc/src/sgml/intarray.sgml. I
understand that this is a specialised int[] shuffle, but I wonder if
someone would ever want to have a general array shuffle, and how that
would work, in terms of naming convention etc.
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 02:25 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Thomas Munro <thomas.munro@gmail.com>
0 siblings, 2 replies; 25+ messages in thread
From: Martin Kalcher @ 2022-07-17 02:25 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 16.07.22 um 23:56 schrieb Thomas Munro:
> On Fri, Jul 15, 2022 at 8:36 PM Martin Kalcher
> <martin.kalcher@aboutsource.net> wrote:
>> I would like to see a function like this inside the intarray extension.
>> Is there any way to get to this point? How is the process to deal with
>> such proposals?
>
> Hi Martin,
>
> I'm redirecting this to the pgsql-hackers@ mailing list, where we talk
> about code. For the archives, Martin's initial message to -general
> was:
>
> https://www.postgresql.org/message-id/9d160a44-7675-51e8-60cf-6d64b76db831%40aboutsource.net
>
> The first question is whether such a thing belongs in an external
> extension, or in the contrib/intarray module. The latter seems like a
> reasonable thing to want to me. The first step towards that will be
> to get your code into .patch format, as in git format-patch or git
> diff, that can be applied to the master branch.
>
> https://wiki.postgresql.org/wiki/Submitting_a_Patch
>
> Some initial feedback from me: I'd recommend adding a couple of
> comments to the code, like the algorithm name for someone who wants to
> read more about it (I think it's a Fisher-Yates shuffle?). You'll
> need to have the contrib/intarrays/intarray--1.5--1.6.sql file that
> creates the function. You might want to add something to
> control/intarray/sql/_int.sql that invokes the function when you run
> make check in there (but doesn't display the results, since that'd be
> unstable across machines?), just to have 'code coverage' (I mean, it'd
> prove it doesn't crash at least). Once details are settled, you'd
> also want to add documentation in doc/src/sgml/intarray.sgml. I
> understand that this is a specialised int[] shuffle, but I wonder if
> someone would ever want to have a general array shuffle, and how that
> would work, in terms of naming convention etc.
Hello Thomas,
Thank you for pointing me towards the correct list.
I do not feel qualified to answer the question wether this belongs in an
external extension or in contrib/intarray. That reason i would like to
see it in contrib/intarray is, that it is lot easier for me to get our
operations team to upgrade our database system, because of new features
we need, than to get them to install a self-maintained extension on our
database servers.
Thank you for your feedback. I tried to address all your points and made
a first patch. Some points are still open:
- Documentation is postponed until further feedback.
- I am not shure about the naming. intarray has generic names like
sort() and uniq() and specialised names like icount(). I guess in case
someone wants to have a general array shuffle it could be accomplished
with function overloading. Or am i wrong here?
- I added a second function sample(), because it is a lot faster to take
some elements from an array than to shuffle the whole array and
slice it. This function can be removed if it is not wanted. The
important one is shuffle().
Martin
Attachments:
0001-Introduce-shuffle-and-sample-to-intarray-extension.patch (text/x-patch, 7.8K) download
From 2c6c28755416556597188c323604ec975faffa25 Mon Sep 17 00:00:00 2001
From: Martin Kalcher <martin.kalcher@aboutsource.net>
Date: Sun, 17 Jul 2022 01:53:05 +0200
Subject: [PATCH] Introduce shuffle() and sample() to intarray extension
* shuffle(arr) returns an array with the elements of the provided array
in random order
* sample(arr, n) returns an array with n randomly-chosen elements from
the provided array
---
contrib/intarray/Makefile | 4 +-
contrib/intarray/_int.h | 2 +
contrib/intarray/_int_op.c | 35 +++++++++++++++
contrib/intarray/_int_tool.c | 57 +++++++++++++++++++++++++
contrib/intarray/expected/_int.out | 36 ++++++++++++++++
contrib/intarray/intarray--1.5--1.6.sql | 16 +++++++
contrib/intarray/intarray.control | 2 +-
contrib/intarray/sql/_int.sql | 6 +++
8 files changed, 155 insertions(+), 3 deletions(-)
create mode 100644 contrib/intarray/intarray--1.5--1.6.sql
diff --git a/contrib/intarray/Makefile b/contrib/intarray/Makefile
index 3817c1669a..1a79c359ed 100644
--- a/contrib/intarray/Makefile
+++ b/contrib/intarray/Makefile
@@ -12,8 +12,8 @@ OBJS = \
_intbig_gist.o
EXTENSION = intarray
-DATA = intarray--1.4--1.5.sql intarray--1.3--1.4.sql intarray--1.2--1.3.sql \
- intarray--1.2.sql intarray--1.1--1.2.sql \
+DATA = intarray--1.5--1.6.sql intarray--1.4--1.5.sql intarray--1.3--1.4.sql \
+ intarray--1.2--1.3.sql intarray--1.2.sql intarray--1.1--1.2.sql \
intarray--1.0--1.1.sql
PGFILEDESC = "intarray - functions and operators for arrays of integers"
diff --git a/contrib/intarray/_int.h b/contrib/intarray/_int.h
index 304c29525c..eaa7a09ae8 100644
--- a/contrib/intarray/_int.h
+++ b/contrib/intarray/_int.h
@@ -123,6 +123,8 @@ bool inner_int_overlap(ArrayType *a, ArrayType *b);
bool inner_int_contains(ArrayType *a, ArrayType *b);
ArrayType *inner_int_union(ArrayType *a, ArrayType *b);
ArrayType *inner_int_inter(ArrayType *a, ArrayType *b);
+void inner_int_shuffle(ArrayType *a);
+ArrayType *inner_int_sample(ArrayType *a, int n);
void rt__int_size(ArrayType *a, float *size);
void gensign(BITVECP sign, int *a, int len, int siglen);
diff --git a/contrib/intarray/_int_op.c b/contrib/intarray/_int_op.c
index 5b164f6788..8c4edf6ddf 100644
--- a/contrib/intarray/_int_op.c
+++ b/contrib/intarray/_int_op.c
@@ -167,6 +167,8 @@ PG_FUNCTION_INFO_V1(sort);
PG_FUNCTION_INFO_V1(sort_asc);
PG_FUNCTION_INFO_V1(sort_desc);
PG_FUNCTION_INFO_V1(uniq);
+PG_FUNCTION_INFO_V1(shuffle);
+PG_FUNCTION_INFO_V1(sample);
PG_FUNCTION_INFO_V1(idx);
PG_FUNCTION_INFO_V1(subarray);
PG_FUNCTION_INFO_V1(intarray_push_elem);
@@ -255,6 +257,39 @@ uniq(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(a);
}
+Datum
+shuffle(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = PG_GETARG_ARRAYTYPE_P_COPY(0);
+
+ CHECKARRVALID(a);
+ inner_int_shuffle(a);
+ PG_RETURN_POINTER(a);
+}
+
+Datum
+sample(PG_FUNCTION_ARGS)
+{
+ ArrayType *a = PG_GETARG_ARRAYTYPE_P_COPY(0);
+ ArrayType *r;
+
+ int n = PG_GETARG_INT32(1);
+
+ CHECKARRVALID(a);
+
+ if (n >= ARRNELEMS(a))
+ PG_RETURN_POINTER(a);
+
+ if (n < 0)
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("second parameter must not be negative")));
+
+ r = inner_int_sample(a, n);
+ PG_FREE_IF_COPY(a, 0);
+ PG_RETURN_POINTER(r);
+}
+
Datum
idx(PG_FUNCTION_ARGS)
{
diff --git a/contrib/intarray/_int_tool.c b/contrib/intarray/_int_tool.c
index 8ed4d63fc3..b26c910deb 100644
--- a/contrib/intarray/_int_tool.c
+++ b/contrib/intarray/_int_tool.c
@@ -179,6 +179,63 @@ inner_int_inter(ArrayType *a, ArrayType *b)
return resize_intArrayType(r, k);
}
+void
+inner_int_shuffle(ArrayType *a)
+{
+ int *d = ARRPTR(a);
+ int n = ARRNELEMS(a);
+ int i, tmp;
+
+ /*
+ * Shuffling is done using the Fisher-Yates shuffle algorithm:
+ * Iterate through the array and swap the current head with a
+ * randomly-chosen element from behind the current head (possibly
+ * the head itself).
+ */
+ while (n > 1)
+ {
+ i = random() % n;
+ tmp = d[i];
+ d[i] = *d;
+ *d = tmp;
+ d++;
+ n--;
+ }
+}
+
+ArrayType *
+inner_int_sample(ArrayType *a, int n)
+{
+ ArrayType *r;
+ int *da,
+ *dr;
+ int na = ARRNELEMS(a);
+
+ n = Min(na, n);
+ r = new_intArrayType(n);
+ da = ARRPTR(a),
+ dr = ARRPTR(r);
+
+ /*
+ * Choosing samples is done using a variant of the "inside-out"
+ * Fisher-Yates shuffle algorithm:
+ * Iterate through the source array, move a randomly-chosen
+ * element from behind the current head (or the head itself) to
+ * the destination array and replace it with the current head.
+ */
+ while (n > 0)
+ {
+ int i = random() % na;
+ *dr = da[i];
+ da[i] = *da;
+ dr++;
+ n--;
+ da++;
+ na--;
+ }
+ return r;
+}
+
void
rt__int_size(ArrayType *a, float *size)
{
diff --git a/contrib/intarray/expected/_int.out b/contrib/intarray/expected/_int.out
index a09d40efa1..cffa683ffe 100644
--- a/contrib/intarray/expected/_int.out
+++ b/contrib/intarray/expected/_int.out
@@ -85,6 +85,42 @@ SELECT subarray('{1234234,-30,-30,234234,-30}',0,-1);
{1234234,-30,-30,234234}
(1 row)
+SELECT sort(shuffle('{1234234,-30,-30,234234,-30}'));
+ sort
+------------------------------
+ {-30,-30,-30,234234,1234234}
+(1 row)
+
+SELECT shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}') != shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}');
+ ?column?
+----------
+ t
+(1 row)
+
+SELECT icount(sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6));
+ icount
+--------
+ 6
+(1 row)
+
+SELECT icount(uniq(sort(sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6))));
+ icount
+--------
+ 6
+(1 row)
+
+SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) <@ '{1,2,3,4,5,6,7,8,9,10,11,12}';
+ ?column?
+----------
+ t
+(1 row)
+
+SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) != sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6);
+ ?column?
+----------
+ t
+(1 row)
+
SELECT #'{1234234,234234}'::int[];
?column?
----------
diff --git a/contrib/intarray/intarray--1.5--1.6.sql b/contrib/intarray/intarray--1.5--1.6.sql
new file mode 100644
index 0000000000..5d5ef8ee01
--- /dev/null
+++ b/contrib/intarray/intarray--1.5--1.6.sql
@@ -0,0 +1,16 @@
+/* contrib/intarray/intarray--1.5--1.6.sql */
+
+-- complain if script is sourced in psql, rather than via ALTER EXTENSION
+\echo Use "ALTER EXTENSION intarray UPDATE TO '1.6'" to load this file. \quit
+
+-- Add shuffle functions
+
+CREATE FUNCTION shuffle(_int4)
+RETURNS _int4
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
+
+CREATE FUNCTION sample(_int4, int4)
+RETURNS _int4
+AS 'MODULE_PATHNAME'
+LANGUAGE C STRICT;
diff --git a/contrib/intarray/intarray.control b/contrib/intarray/intarray.control
index c3ff753e2c..6ae8881f15 100644
--- a/contrib/intarray/intarray.control
+++ b/contrib/intarray/intarray.control
@@ -1,6 +1,6 @@
# intarray extension
comment = 'functions, operators, and index support for 1-D arrays of integers'
-default_version = '1.5'
+default_version = '1.6'
module_pathname = '$libdir/_int'
relocatable = true
trusted = true
diff --git a/contrib/intarray/sql/_int.sql b/contrib/intarray/sql/_int.sql
index b26fc57e4d..3eb15d5c08 100644
--- a/contrib/intarray/sql/_int.sql
+++ b/contrib/intarray/sql/_int.sql
@@ -18,6 +18,12 @@ SELECT idx('{1234234,-30,-30,234234,-30}',-30);
SELECT subarray('{1234234,-30,-30,234234,-30}',2,3);
SELECT subarray('{1234234,-30,-30,234234,-30}',-1,1);
SELECT subarray('{1234234,-30,-30,234234,-30}',0,-1);
+SELECT sort(shuffle('{1234234,-30,-30,234234,-30}'));
+SELECT shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}') != shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}');
+SELECT icount(sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6));
+SELECT icount(uniq(sort(sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6))));
+SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) <@ '{1,2,3,4,5,6,7,8,9,10,11,12}';
+SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) != sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6);
SELECT #'{1234234,234234}'::int[];
SELECT '{123,623,445}'::int[] + 1245;
--
2.37.1
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 03:18 Tom Lane <tgl@sss.pgh.pa.us>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
1 sibling, 2 replies; 25+ messages in thread
From: Tom Lane @ 2022-07-17 03:18 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Martin Kalcher <martin.kalcher@aboutsource.net> writes:
> Am 16.07.22 um 23:56 schrieb Thomas Munro:
>> I understand that this is a specialised int[] shuffle, but I wonder if
>> someone would ever want to have a general array shuffle, and how that
>> would work, in terms of naming convention etc.
> - I am not shure about the naming. intarray has generic names like
> sort() and uniq() and specialised names like icount(). I guess in case
> someone wants to have a general array shuffle it could be accomplished
> with function overloading. Or am i wrong here?
I suppose this is exactly the point Thomas was wondering about: if we
use a generic function name for this, will it cause problems for someone
trying to add a generic function later?
We can investigate that question with a couple of toy functions:
regression=# create function foo(int[]) returns text as 'select ''int[] version''' language sql;
CREATE FUNCTION
regression=# create function foo(anyarray) returns text as 'select ''anyarray version''' language sql;
CREATE FUNCTION
regression=# select foo('{1,2,3}');
ERROR: function foo(unknown) is not unique
LINE 1: select foo('{1,2,3}');
^
HINT: Could not choose a best candidate function. You might need to add explicit type casts.
OK, that's not too surprising: with an unknown input there's just not
anything that the parser can use to disambiguate. But this happens
with just about any overloaded name, so I don't think it's a showstopper.
regression=# select foo('{1,2,3}'::int[]);
foo
---------------
int[] version
(1 row)
regression=# select foo('{1,2,3}'::int8[]);
foo
------------------
anyarray version
(1 row)
Good, that's more or less the minimum functionality we should expect.
regression=# select foo('{1,2,3}'::int2[]);
ERROR: function foo(smallint[]) is not unique
LINE 1: select foo('{1,2,3}'::int2[]);
^
HINT: Could not choose a best candidate function. You might need to add explicit type casts.
Oh, that's slightly annoying ...
regression=# select foo('{1,2,3}'::oid[]);
foo
------------------
anyarray version
(1 row)
regression=# select foo('{1,2,3}'::text[]);
foo
------------------
anyarray version
(1 row)
regression=# select foo('{1,2,3}'::float8[]);
foo
------------------
anyarray version
(1 row)
I couldn't readily find any case that misbehaves except for int2[].
You can force that to work, at least in one direction:
regression=# select foo('{1,2,3}'::int2[]::int[]);
foo
---------------
int[] version
(1 row)
On the whole, I'd vote for calling it shuffle(), and expecting that
we'd also use that name for any future generic version. That's
clearly the easiest-to-remember definition, and it doesn't seem
like the gotchas are bad enough to justify using separate names.
> - I added a second function sample(), because it is a lot faster to take
> some elements from an array than to shuffle the whole array and
> slice it. This function can be removed if it is not wanted.
I have no opinion about whether this one is valuable enough to include in
intarray, but I do feel like sample() is a vague name, and easily confused
with marginally-related operations like TABLESAMPLE. Can we think of a
more on-point name? Something like "random_subset" would be pretty
clear, but it's also clunky. It's too late here for me to think of
le mot juste...
regards, tom lane
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 03:32 David G. Johnston <david.g.johnston@gmail.com>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
1 sibling, 1 reply; 25+ messages in thread
From: David G. Johnston @ 2022-07-17 03:32 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Sat, Jul 16, 2022 at 7:25 PM Martin Kalcher <
martin.kalcher@aboutsource.net> wrote:
>
> - I added a second function sample(), because it is a lot faster to take
> some elements from an array than to shuffle the whole array and
> slice it. This function can be removed if it is not wanted. The
> important one is shuffle().
>
>
+SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) !=
sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6);
+ ?column?
+----------
+ t
+(1 row)
+
While small, there is a non-zero chance for both samples to be equal. This
test should probably just go, I don't see what it tests that isn't covered
by other tests or even trivial usage.
Same goes for:
+SELECT shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}') !=
shuffle('{1,2,3,4,5,6,7,8,9,10,11,12}');
+ ?column?
+----------
+ t
+(1 row)
+
David J.
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 03:36 David G. Johnston <david.g.johnston@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 25+ messages in thread
From: David G. Johnston @ 2022-07-17 03:36 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Martin Kalcher <martin.kalcher@aboutsource.net>; Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Sat, Jul 16, 2022 at 8:18 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Martin Kalcher <martin.kalcher@aboutsource.net> writes:
>
> > - I added a second function sample(), because it is a lot faster to take
> > some elements from an array than to shuffle the whole array and
> > slice it. This function can be removed if it is not wanted.
>
> I have no opinion about whether this one is valuable enough to include in
> intarray, but I do feel like sample() is a vague name, and easily confused
> with marginally-related operations like TABLESAMPLE. Can we think of a
> more on-point name? Something like "random_subset" would be pretty
> clear, but it's also clunky. It's too late here for me to think of
> le mot juste...
>
>
choose(input anyarray, size integer, with_replacement boolean default
false, algorithm text default 'default')?
David J.
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 03:37 Tom Lane <tgl@sss.pgh.pa.us>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 2 replies; 25+ messages in thread
From: Tom Lane @ 2022-07-17 03:37 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
I wrote:
> On the whole, I'd vote for calling it shuffle(), and expecting that
> we'd also use that name for any future generic version.
Actually ... is there a reason to bother with an intarray version
at all, rather than going straight for an in-core anyarray function?
It's not obvious to me that an int4-only version would have
major performance advantages.
regards, tom lane
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 06:00 Thomas Munro <thomas.munro@gmail.com>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 2 replies; 25+ messages in thread
From: Thomas Munro @ 2022-07-17 06:00 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Martin Kalcher <martin.kalcher@aboutsource.net>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Sun, Jul 17, 2022 at 3:37 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> I wrote:
> > On the whole, I'd vote for calling it shuffle(), and expecting that
> > we'd also use that name for any future generic version.
>
> Actually ... is there a reason to bother with an intarray version
> at all, rather than going straight for an in-core anyarray function?
> It's not obvious to me that an int4-only version would have
> major performance advantages.
Yeah, that seems like a good direction. If there is a performance
advantage to specialising, then perhaps we only have to specialise on
size, not type. Perhaps there could be a general function that
internally looks out for typbyval && typlen == 4, and dispatches to a
specialised 4-byte, and likewise for 8, if it can, and that'd already
be enough to cover int, bigint, float etc, without needing
specialisations for each type.
I went to see what Professor Lemire would have to say about all this,
expecting to find a SIMD rabbit hole to fall down for some Sunday
evening reading, but the main thing that jumped out was this article
about the modulo operation required by textbook Fisher-Yates to get a
bounded random number, the random() % n that appears in the patch. He
talks about shuffling twice as fast by using a no-division trick to
get bounded random numbers[1]. I guess you might need to use our
pg_prng_uint32() for that trick because random()'s 0..RAND_MAX might
introduce bias. Anyway, file that under go-faster ideas for later.
[1] https://lemire.me/blog/2016/06/30/fast-random-shuffling/
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 09:16 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 25+ messages in thread
From: Martin Kalcher @ 2022-07-17 09:16 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 17.07.22 um 05:37 schrieb Tom Lane:
>
> Actually ... is there a reason to bother with an intarray version
> at all, rather than going straight for an in-core anyarray function?
> It's not obvious to me that an int4-only version would have
> major performance advantages.
>
> regards, tom lane
Hi Tom,
thank you for your thoughts. There are two reasons for choosing an
int4-only version. I am not familiar with postgres development (yet) and
i was not sure how open you are about such changes to core and if the
proposed feature is considered valuable enough to go into core. The
second reason was ease of implementation. The intarray extension does
not allow any NULL elements in arrays and treats multidimensional arrays
as though they were linear. Which makes the implementation straight
forward, because there are fewer cases to consider.
However, i will take a look at an implementation for anyarray in core.
Martin
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 09:38 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 0 replies; 25+ messages in thread
From: Martin Kalcher @ 2022-07-17 09:38 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; Tom Lane <tgl@sss.pgh.pa.us>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 17.07.22 um 08:00 schrieb Thomas Munro:
>
> I went to see what Professor Lemire would have to say about all this,
> expecting to find a SIMD rabbit hole to fall down for some Sunday
> evening reading, but the main thing that jumped out was this article
> about the modulo operation required by textbook Fisher-Yates to get a
> bounded random number, the random() % n that appears in the patch. He
> talks about shuffling twice as fast by using a no-division trick to
> get bounded random numbers[1]. I guess you might need to use our
> pg_prng_uint32() for that trick because random()'s 0..RAND_MAX might
> introduce bias. Anyway, file that under go-faster ideas for later.
>
> [1] https://lemire.me/blog/2016/06/30/fast-random-shuffling/
Hi Thomas,
the small bias of random() % n is not a problem for my use case, but
might be for others. Its easily replaceable with
(int) pg_prng_uint64_range(&pg_global_prng_state, 0, n-1)
Unfortunately it is a bit slower (on my machine), but thats negligible.
Martin
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 09:54 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: David G. Johnston <david.g.johnston@gmail.com>
0 siblings, 0 replies; 25+ messages in thread
From: Martin Kalcher @ 2022-07-17 09:54 UTC (permalink / raw)
To: David G. Johnston <david.g.johnston@gmail.com>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 17.07.22 um 05:32 schrieb David G. Johnston:
>
> +SELECT sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6) !=
> sample('{1,2,3,4,5,6,7,8,9,10,11,12}', 6);
> + ?column?
> +----------
> + t
> +(1 row)
> +
>
> While small, there is a non-zero chance for both samples to be equal. This
> test should probably just go, I don't see what it tests that isn't covered
> by other tests or even trivial usage.
>
Hey David,
you are right. There is a small chance for this test to fail. I wanted
to test, that two invocations produce different results (after all the
main feature of the function). But it can probably go.
Martin
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 16:15 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 2 replies; 25+ messages in thread
From: Martin Kalcher @ 2022-07-17 16:15 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; Tom Lane <tgl@sss.pgh.pa.us>; +Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 17.07.22 um 08:00 schrieb Thomas Munro:
>> Actually ... is there a reason to bother with an intarray version
>> at all, rather than going straight for an in-core anyarray function?
>> It's not obvious to me that an int4-only version would have
>> major performance advantages.
>
> Yeah, that seems like a good direction. If there is a performance
> advantage to specialising, then perhaps we only have to specialise on
> size, not type. Perhaps there could be a general function that
> internally looks out for typbyval && typlen == 4, and dispatches to a
> specialised 4-byte, and likewise for 8, if it can, and that'd already
> be enough to cover int, bigint, float etc, without needing
> specialisations for each type.
I played around with the idea of an anyarray shuffle(). The hard part
was to deal with arrays with variable length elements, as they can not
be swapped easily in place. I solved it by creating an intermediate
array of references to the elements. I'll attach a patch with the proof
of concept. Unfortunatly it is already about 5 times slower than the
specialised version and i am not sure if it is worth going down that road.
Martin
Attachments:
0001-introduce-array_shuffle.patch (text/x-patch, 3.4K) download
From 85cb90c79459132c4220b8d78586dffe6e590ba9 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()
---
src/backend/utils/adt/arrayfuncs.c | 73 ++++++++++++++++++++++++++++++
src/include/catalog/pg_proc.dat | 3 ++
2 files changed, 76 insertions(+)
diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c
index fb167f226a..b6576ce178 100644
--- a/src/backend/utils/adt/arrayfuncs.c
+++ b/src/backend/utils/adt/arrayfuncs.c
@@ -6872,3 +6872,76 @@ trim_array(PG_FUNCTION_ARGS)
PG_RETURN_DATUM(result);
}
+
+Datum
+array_shuffle(PG_FUNCTION_ARGS)
+{
+ ArrayType *array,
+ *result;
+ char *adat,
+ *rdat;
+ int nitems,
+ i;
+ Oid elemtype;
+ TypeCacheEntry typentry;
+ struct { char *dat; size_t size; } *refs;
+
+ array = PG_GETARG_ARRAYTYPE_P(0);
+
+ if (ARR_HASNULL(array))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("shuffling arrays with null elements is not supported")));
+
+ if (ARR_NDIM(array) > 1)
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("shuffling of multidimensional arrays is not supported")));
+
+ elemtype = ARR_ELEMTYPE(array);
+ typentry = *lookup_type_cache(elemtype, 0);
+ nitems = ArrayGetNItems(ARR_NDIM(array), ARR_DIMS(array));
+ refs = palloc(nitems * (sizeof(char *) + sizeof(size_t)));
+ adat = ARR_DATA_PTR(array);
+
+ /*
+ * To allow shuffling of arrays with variable length elements, we are going
+ * to shuffle references to the elements, because swapping variable length
+ * elements in an array is complicated. In a second step we will iterate the
+ * shuffled references and copy the elements to the destination array.
+ * We are using the "inside-out" variant of the Fisher-Yates algorithm to
+ * produce a shuffled array of references: Append each reference than swap it
+ * with a radomly-chosen refence.
+ */
+ for (i = 0; i < nitems; i++)
+ {
+ int j = random() % (i + 1);
+ char *next = att_addlength_pointer(adat, typentry.typlen, adat);
+ next = (char *) att_align_nominal(next, typentry.typalign);
+ refs[i] = refs[j];
+ refs[j].dat = adat;
+ refs[j].size = next - adat;
+ adat = next;
+ }
+
+ result = create_array_envelope(ARR_NDIM(array),
+ ARR_DIMS(array),
+ ARR_LBOUND(array),
+ ARR_SIZE(array),
+ ARR_ELEMTYPE(array),
+ array->dataoffset);
+
+ rdat = ARR_DATA_PTR(result);
+
+ /* Collect all references and copy elements to the destination array */
+ for (i = 0; i < nitems; i++)
+ {
+ memcpy(rdat, refs[i].dat, refs[i].size);
+ rdat += refs[i].size;
+ }
+
+ pfree(refs);
+ 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..56aff551d3 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1681,6 +1681,9 @@
proname => 'arraycontjoinsel', provolatile => 's', prorettype => 'float8',
proargtypes => 'internal oid internal int2 internal',
prosrc => 'arraycontjoinsel' },
+{ oid => '7777', descr => 'shuffle array',
+ proname => 'array_shuffle', proisstrict => 'f', prorettype => 'anyarray',
+ proargtypes => 'anyarray', prosrc => 'array_shuffle' },
{ oid => '764', descr => 'large object import',
proname => 'lo_import', provolatile => 'v', proparallel => 'u',
--
2.37.1
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 22:37 Thomas Munro <thomas.munro@gmail.com>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
1 sibling, 2 replies; 25+ messages in thread
From: Thomas Munro @ 2022-07-17 22:37 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Mon, Jul 18, 2022 at 4:15 AM Martin Kalcher
<martin.kalcher@aboutsource.net> wrote:
> Am 17.07.22 um 08:00 schrieb Thomas Munro:
> >> Actually ... is there a reason to bother with an intarray version
> >> at all, rather than going straight for an in-core anyarray function?
> >> It's not obvious to me that an int4-only version would have
> >> major performance advantages.
> >
> > Yeah, that seems like a good direction. If there is a performance
> > advantage to specialising, then perhaps we only have to specialise on
> > size, not type. Perhaps there could be a general function that
> > internally looks out for typbyval && typlen == 4, and dispatches to a
> > specialised 4-byte, and likewise for 8, if it can, and that'd already
> > be enough to cover int, bigint, float etc, without needing
> > specialisations for each type.
>
> I played around with the idea of an anyarray shuffle(). The hard part
> was to deal with arrays with variable length elements, as they can not
> be swapped easily in place. I solved it by creating an intermediate
> array of references to the elements. I'll attach a patch with the proof
> of concept. Unfortunatly it is already about 5 times slower than the
> specialised version and i am not sure if it is worth going down that road.
Seems OK for a worst case. It must still be a lot faster than doing
it in SQL. Now I wonder what the exact requirements would be to
dispatch to a faster version that would handle int4. I haven't
studied this in detail but perhaps to dispatch to a fast shuffle for
objects of size X, the requirement would be something like typlen == X
&& align_bytes <= typlen && typlen % align_bytes == 0, where
align_bytes is typalign converted to ALIGNOF_{CHAR,SHORT,INT,DOUBLE}?
Or in English, 'the data consists of densely packed objects of fixed
size X, no padding'. Or perhaps you can work out the padded size and
use that, to catch a few more types. Then you call
array_shuffle_{2,4,8}() as appropriate, which should be as fast as
your original int[] proposal, but work also for float, date, ...?
About your experimental patch, I haven't reviewed it properly or tried
it but I wonder if uint32 dat_offset, uint32 size (= half size
elements) would be enough due to limitations on varlenas.
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 22:46 Tom Lane <tgl@sss.pgh.pa.us>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
1 sibling, 1 reply; 25+ messages in thread
From: Tom Lane @ 2022-07-17 22:46 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Martin Kalcher <martin.kalcher@aboutsource.net> writes:
> Am 17.07.22 um 08:00 schrieb Thomas Munro:
>>> Actually ... is there a reason to bother with an intarray version
>>> at all, rather than going straight for an in-core anyarray function?
> I played around with the idea of an anyarray shuffle(). The hard part
> was to deal with arrays with variable length elements, as they can not
> be swapped easily in place. I solved it by creating an intermediate
> array of references to the elements. I'll attach a patch with the proof
> of concept.
This does not look particularly idiomatic, or even type-safe. What you
should have done was use deconstruct_array to get an array of Datums and
isnull flags, then shuffled those, then used construct_array to build the
output.
(Or, perhaps, use construct_md_array to replicate the input's
precise dimensionality. Not sure if anyone would care.)
regards, tom lane
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 22:53 Tom Lane <tgl@sss.pgh.pa.us>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 0 replies; 25+ messages in thread
From: Tom Lane @ 2022-07-17 22:53 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: Martin Kalcher <martin.kalcher@aboutsource.net>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Thomas Munro <thomas.munro@gmail.com> writes:
> Seems OK for a worst case. It must still be a lot faster than doing
> it in SQL. Now I wonder what the exact requirements would be to
> dispatch to a faster version that would handle int4.
I find it impossible to believe that it's worth micro-optimizing
shuffle() to that extent. Now, maybe doing something in that line
in deconstruct_array and construct_array would be worth our time,
as that'd benefit a pretty wide group of functions.
regards, tom lane
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 23:05 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 25+ messages in thread
From: Martin Kalcher @ 2022-07-17 23:05 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 18.07.22 um 00:46 schrieb Tom Lane:
>
> This does not look particularly idiomatic, or even type-safe. What you
> should have done was use deconstruct_array to get an array of Datums and
> isnull flags, then shuffled those, then used construct_array to build the
> output.
>
> (Or, perhaps, use construct_md_array to replicate the input's
> precise dimensionality. Not sure if anyone would care.)
>
> regards, tom lane
deconstruct_array() would destroy the arrays dimensions. I would expect
that shuffle() only shuffles the first dimension and keeps the inner
arrays intact.
Martin
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 23:07 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Thomas Munro <thomas.munro@gmail.com>
1 sibling, 0 replies; 25+ messages in thread
From: Martin Kalcher @ 2022-07-17 23:07 UTC (permalink / raw)
To: Thomas Munro <thomas.munro@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 18.07.22 um 00:37 schrieb Thomas Munro:
> Seems OK for a worst case. It must still be a lot faster than doing
> it in SQL. Now I wonder what the exact requirements would be to
> dispatch to a faster version that would handle int4. I haven't
> studied this in detail but perhaps to dispatch to a fast shuffle for
> objects of size X, the requirement would be something like typlen == X
> && align_bytes <= typlen && typlen % align_bytes == 0, where
> align_bytes is typalign converted to ALIGNOF_{CHAR,SHORT,INT,DOUBLE}?
> Or in English, 'the data consists of densely packed objects of fixed
> size X, no padding'. Or perhaps you can work out the padded size and
> use that, to catch a few more types. Then you call
> array_shuffle_{2,4,8}() as appropriate, which should be as fast as
> your original int[] proposal, but work also for float, date, ...?
>
> About your experimental patch, I haven't reviewed it properly or tried
> it but I wonder if uint32 dat_offset, uint32 size (= half size
> elements) would be enough due to limitations on varlenas.
I made another experimental patch with fast tracks for typelen4 and
typelen8. alignments are not yet considered.
Attachments:
0001-introduce-array_shuffle.patch (text/x-patch, 5.3K) download
From 37269598a1dace99c9059514e0fdcb90b9240ed3 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()
---
src/backend/utils/adt/arrayfuncs.c | 178 +++++++++++++++++++++++++++++
src/include/catalog/pg_proc.dat | 3 +
2 files changed, 181 insertions(+)
diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c
index fb167f226a..919cb2bfd6 100644
--- a/src/backend/utils/adt/arrayfuncs.c
+++ b/src/backend/utils/adt/arrayfuncs.c
@@ -6872,3 +6872,181 @@ trim_array(PG_FUNCTION_ARGS)
PG_RETURN_DATUM(result);
}
+
+static ArrayType *
+array_shuffle_4(ArrayType *array)
+{
+ ArrayType *result;
+ int32 *adat,
+ *rdat;
+ int i,
+ j,
+ nitems;
+
+ result = create_array_envelope(ARR_NDIM(array),
+ ARR_DIMS(array),
+ ARR_LBOUND(array),
+ ARR_SIZE(array),
+ ARR_ELEMTYPE(array),
+ array->dataoffset);
+
+ adat = (int32 *) ARR_DATA_PTR(array);
+ rdat = (int32 *) ARR_DATA_PTR(result);
+ nitems = ARR_DIMS(array)[0];
+
+ for (i = 0; i < nitems; i++)
+ {
+ j = random() % (i + 1);
+ rdat[i] = rdat[j];
+ rdat[j] = adat[i];
+ }
+ return result;
+}
+
+static ArrayType *
+array_shuffle_8(ArrayType *array)
+{
+ ArrayType *result;
+ int64 *adat,
+ *rdat;
+ int i,
+ j,
+ nitems;
+
+ result = create_array_envelope(ARR_NDIM(array),
+ ARR_DIMS(array),
+ ARR_LBOUND(array),
+ ARR_SIZE(array),
+ ARR_ELEMTYPE(array),
+ array->dataoffset);
+
+ adat = (int64 *) ARR_DATA_PTR(array);
+ rdat = (int64 *) ARR_DATA_PTR(result);
+ nitems = ARR_DIMS(array)[0];
+
+ for (i = 0; i < nitems; i++)
+ {
+ j = random() % (i + 1);
+ rdat[i] = rdat[j];
+ rdat[j] = adat[i];
+ }
+ return result;
+}
+
+static ArrayType *
+array_shuffle_generic(ArrayType *array,
+ int16 elmlen, bool elmbyval, char elmalign)
+{
+ ArrayType *result;
+ char *adat,
+ *rdat;
+ int i,
+ ndim,
+ *dims,
+ nitems,
+ nelms_per_item;
+
+ struct {
+ char *dat;
+ size_t size;
+ } *refs;
+
+ ndim = ARR_NDIM(array);
+ dims = ARR_DIMS(array);
+
+ nelms_per_item = 1;
+
+ for (i = 1; i < ndim; i++)
+ nelms_per_item *= dims[i];
+
+ nitems = dims[0];
+
+ refs = palloc(nitems * (sizeof(char *) + sizeof(size_t)));
+ adat = ARR_DATA_PTR(array);
+
+ /*
+ * To allow shuffling of arrays with variable length elements, we are going
+ * to shuffle references to the elements, because swapping variable length
+ * elements in an array is complicated. In a second step we will iterate the
+ * shuffled references and copy the elements to the destination array.
+ * We are using the "inside-out" variant of the Fisher-Yates algorithm to
+ * produce a shuffled array of references: Append each reference than swap it
+ * with a radomly-chosen refence.
+ */
+ for (i = 0; i < nitems; i++)
+ {
+ char *next = array_seek(adat, 0, NULL, nelms_per_item,
+ elmlen, elmbyval, elmalign);
+ int j = random() % (i + 1);
+ refs[i] = refs[j];
+ refs[j].dat = adat;
+ refs[j].size = next - adat;
+ adat = next;
+ }
+
+ result = create_array_envelope(ARR_NDIM(array),
+ ARR_DIMS(array),
+ ARR_LBOUND(array),
+ ARR_SIZE(array),
+ ARR_ELEMTYPE(array),
+ array->dataoffset);
+
+ rdat = ARR_DATA_PTR(result);
+
+ /* Collect all references and copy elements to the destination array */
+ for (i = 0; i < nitems; i++)
+ {
+ memcpy(rdat, refs[i].dat, refs[i].size);
+ rdat += refs[i].size;
+ }
+
+ pfree(refs);
+
+ return result;
+}
+
+Datum
+array_shuffle(PG_FUNCTION_ARGS)
+{
+ ArrayType *array,
+ *result;
+ int16 elmlen;
+ bool elmbyval;
+ char elmalign;
+ Oid elmtyp;
+ TypeCacheEntry *typentry;
+
+ array = PG_GETARG_ARRAYTYPE_P(0);
+
+ if (ARR_HASNULL(array))
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("shuffling arrays with null elements is not supported")));
+
+ if (ARR_NDIM(array) < 1 || ARR_DIMS(array)[0] < 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;
+
+ if (ARR_NDIM(array) == 1 && elmlen == 4)
+ result = array_shuffle_4(array);
+ else if (ARR_NDIM(array) == 1 && elmlen == 8)
+ result = array_shuffle_8(array);
+ else
+ result = array_shuffle_generic(array, elmlen, elmbyval, elmalign);
+
+ 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..56aff551d3 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1681,6 +1681,9 @@
proname => 'arraycontjoinsel', provolatile => 's', prorettype => 'float8',
proargtypes => 'internal oid internal int2 internal',
prosrc => 'arraycontjoinsel' },
+{ oid => '7777', descr => 'shuffle array',
+ proname => 'array_shuffle', proisstrict => 'f', prorettype => 'anyarray',
+ proargtypes => 'anyarray', prosrc => 'array_shuffle' },
{ oid => '764', descr => 'large object import',
proname => 'lo_import', provolatile => 'v', proparallel => 'u',
--
2.37.1
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-17 23:20 Tom Lane <tgl@sss.pgh.pa.us>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
0 siblings, 2 replies; 25+ messages in thread
From: Tom Lane @ 2022-07-17 23:20 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Martin Kalcher <martin.kalcher@aboutsource.net> writes:
> Am 18.07.22 um 00:46 schrieb Tom Lane:
>> This does not look particularly idiomatic, or even type-safe. What you
>> should have done was use deconstruct_array to get an array of Datums and
>> isnull flags, then shuffled those, then used construct_array to build the
>> output.
>>
>> (Or, perhaps, use construct_md_array to replicate the input's
>> precise dimensionality. Not sure if anyone would care.)
> deconstruct_array() would destroy the arrays dimensions.
As I said, you can use construct_md_array if you want to preserve the
array shape.
> I would expect that shuffle() only shuffles the first dimension and
> keeps the inner arrays intact.
This argument is based on a false premise, ie that Postgres thinks
multidimensional arrays are arrays-of-arrays. They aren't, and
we're not going to start making them so by defining shuffle()
at variance with every other array-manipulating function. Shuffling
the individual elements regardless of array shape is the definition
that's consistent with our existing functionality.
(Having said that, even if we were going to implement it with that
definition, I should think that it'd be easiest to do so on the
array-of-Datums representation produced by deconstruct_array.
That way you don't need to do different things for different element
types.)
regards, tom lane
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-18 07:12 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 0 replies; 25+ messages in thread
From: Martin Kalcher @ 2022-07-18 07:12 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 18.07.22 um 01:20 schrieb Tom Lane:
>> I would expect that shuffle() only shuffles the first dimension and
>> keeps the inner arrays intact.
>
> This argument is based on a false premise, ie that Postgres thinks
> multidimensional arrays are arrays-of-arrays. They aren't, and
> we're not going to start making them so by defining shuffle()
> at variance with every other array-manipulating function. Shuffling
> the individual elements regardless of array shape is the definition
> that's consistent with our existing functionality.
Hey Tom,
thank you for clarification. I did not know that. I will make a patch
that is using deconstruct_array().
Martin
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-18 07:47 Martin Kalcher <martin.kalcher@aboutsource.net>
parent: Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 25+ messages in thread
From: Martin Kalcher @ 2022-07-18 07:47 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Am 18.07.22 um 01:20 schrieb Tom Lane:
> (Having said that, even if we were going to implement it with that
> definition, I should think that it'd be easiest to do so on the
> array-of-Datums representation produced by deconstruct_array.
> That way you don't need to do different things for different element
> types.)
Thank you Tom, here is a patch utilising deconstruct_array(). If we
agree, that this is the way to go, i would like to add array_sample()
(good name?), some test cases, and documentation.
One more question. How do i pick a Oid for the functions?
Martin
Attachments:
0001-introduce-array_shuffle.patch (text/x-patch, 2.6K) download
From baec08168357098287342c92672ef97361a91371 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()
---
src/backend/utils/adt/arrayfuncs.c | 61 ++++++++++++++++++++++++++++++
src/include/catalog/pg_proc.dat | 3 ++
2 files changed, 64 insertions(+)
diff --git a/src/backend/utils/adt/arrayfuncs.c b/src/backend/utils/adt/arrayfuncs.c
index fb167f226a..e185c1ef74 100644
--- a/src/backend/utils/adt/arrayfuncs.c
+++ b/src/backend/utils/adt/arrayfuncs.c
@@ -6872,3 +6872,64 @@ trim_array(PG_FUNCTION_ARGS)
PG_RETURN_DATUM(result);
}
+
+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);
+
+ if (ArrayGetNItems(ARR_NDIM(array), ARR_DIMS(array)) < 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);
+
+ 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);
+}
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 2e41f4d9e8..56aff551d3 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -1681,6 +1681,9 @@
proname => 'arraycontjoinsel', provolatile => 's', prorettype => 'float8',
proargtypes => 'internal oid internal int2 internal',
prosrc => 'arraycontjoinsel' },
+{ oid => '7777', descr => 'shuffle array',
+ proname => 'array_shuffle', proisstrict => 'f', prorettype => 'anyarray',
+ proargtypes => 'anyarray', prosrc => 'array_shuffle' },
{ oid => '764', descr => 'large object import',
proname => 'lo_import', provolatile => 'v', proparallel => 'u',
--
2.37.1
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-18 08:18 John Naylor <john.naylor@enterprisedb.com>
parent: Martin Kalcher <martin.kalcher@aboutsource.net>
0 siblings, 1 reply; 25+ messages in thread
From: John Naylor @ 2022-07-18 08:18 UTC (permalink / raw)
To: Martin Kalcher <martin.kalcher@aboutsource.net>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
On Mon, Jul 18, 2022 at 2:47 PM Martin Kalcher <
martin.kalcher@aboutsource.net> wrote:
> One more question. How do i pick a Oid for the functions?
For this, we recommend running src/include/catalog/unused_oids, and it will
give you a random range to pick from. That reduces the chance of different
patches conflicting with each other. It doesn't really matter what the oid
here is, since at feature freeze a committer will change them anyway.
--
John Naylor
EDB: http://www.enterprisedb.com
^ permalink raw reply [nested|flat] 25+ messages in thread
* Re: Proposal to introduce a shuffle function to intarray extension
@ 2022-07-18 13:48 Tom Lane <tgl@sss.pgh.pa.us>
parent: John Naylor <john.naylor@enterprisedb.com>
0 siblings, 0 replies; 25+ messages in thread
From: Tom Lane @ 2022-07-18 13:48 UTC (permalink / raw)
To: John Naylor <john.naylor@enterprisedb.com>; +Cc: Martin Kalcher <martin.kalcher@aboutsource.net>; Thomas Munro <thomas.munro@gmail.com>; PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
John Naylor <john.naylor@enterprisedb.com> writes:
> On Mon, Jul 18, 2022 at 2:47 PM Martin Kalcher <
> martin.kalcher@aboutsource.net> wrote:
>> One more question. How do i pick a Oid for the functions?
> For this, we recommend running src/include/catalog/unused_oids, and it will
> give you a random range to pick from. That reduces the chance of different
> patches conflicting with each other. It doesn't really matter what the oid
> here is, since at feature freeze a committer will change them anyway.
If you want the nitty gritty details here, see
https://www.postgresql.org/docs/devel/system-catalog-initial-data.html#SYSTEM-CATALOG-OID-ASSIGNMENT
regards, tom lane
^ permalink raw reply [nested|flat] 25+ messages in thread
end of thread, other threads:[~2022-07-18 13:48 UTC | newest]
Thread overview: 25+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2022-07-15 08:36 Proposal to introduce a shuffle function to intarray extension Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-16 16:53 ` Mladen Gogala <gogala.mladen@gmail.com>
2022-07-16 20:21 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-16 21:30 ` Mladen Gogala <gogala.mladen@gmail.com>
2022-07-16 21:56 ` Thomas Munro <thomas.munro@gmail.com>
2022-07-17 02:25 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-17 03:18 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-07-17 03:36 ` David G. Johnston <david.g.johnston@gmail.com>
2022-07-17 03:37 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-07-17 06:00 ` Thomas Munro <thomas.munro@gmail.com>
2022-07-17 09:38 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-17 16:15 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-17 22:37 ` Thomas Munro <thomas.munro@gmail.com>
2022-07-17 22:53 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-07-17 23:07 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-17 22:46 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-07-17 23:05 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-17 23:20 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-07-18 07:12 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-18 07:47 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-18 08:18 ` John Naylor <john.naylor@enterprisedb.com>
2022-07-18 13:48 ` Tom Lane <tgl@sss.pgh.pa.us>
2022-07-17 09:16 ` Martin Kalcher <martin.kalcher@aboutsource.net>
2022-07-17 03:32 ` David G. Johnston <david.g.johnston@gmail.com>
2022-07-17 09:54 ` Martin Kalcher <martin.kalcher@aboutsource.net>
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