pg.ddx.io  pgsql-general@postgresql.org mailing list archive  
help / color / mirror / Atom feed
From: Martin Kalcher <martin.kalcher@aboutsource.net>
To: pgsql-general@lists.postgresql.org
Subject: Proposal to introduce a shuffle function to intarray extension
Date: Fri, 15 Jul 2022 10:36:06 +0200
Message-ID: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net> (raw)

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;
   }
}








view thread (25+ messages)  latest in thread

Message-ID: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net>
Permalink:  ../9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net/
Also on:    postgresql.org/message-id/9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net

 · 

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
  Subject: Re: Proposal to introduce a shuffle function to intarray extension
  In-Reply-To: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net>
  References: <9d160a44-7675-51e8-60cf-6d64b76db831@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