Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oCGo8-0007wq-TQ for pgsql-general@arkaria.postgresql.org; Fri, 15 Jul 2022 08:36:20 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1oCGo5-0000XW-TH for pgsql-general@arkaria.postgresql.org; Fri, 15 Jul 2022 08:36:17 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oCGo5-0000XN-HG for pgsql-general@lists.postgresql.org; Fri, 15 Jul 2022 08:36:17 +0000 Received: from mout-b-206.mailbox.org ([2001:67c:2050:102:465::206]) by magus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1oCGo1-0005NI-Hu for pgsql-general@lists.postgresql.org; Fri, 15 Jul 2022 08:36:16 +0000 Received: from smtp102.mailbox.org (smtp102.mailbox.org [IPv6:2001:67c:2050:b231:465::102]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange ECDHE (P-384) server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by mout-b-206.mailbox.org (Postfix) with ESMTPS id 4Lkl7W6p46z9slb for ; Fri, 15 Jul 2022 10:36:07 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=aboutsource.net; s=MBO0001; t=1657874167; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=ODWYGce0sqPm5k07QIw/ZGE5hhQkN00xp2zzKlKWgJ4=; b=Gti2WMYUHFCOwt1kH8Mn/8kpWld6gj/M18zAiTD6eitQkin8+bbX6Ysm5MfJ7vIZwLhlLp 0ZXj1hWGa6nwFtRvkND7zBK9FRU8Rpw1jVeyio5IfEdzb5w5+Ut8bySNvG2mDSdnXrDAMT U52pW9MGLgcUtDpf2Mk8wmPY9UZUsq0M+zT8UvLqHen9xXRE+BvNLO3cU24gvQyj+/NC00 q+pXZ3ZYF0Pmi8gCy9BbpqFN4iPZHyXoTyli36U7RGN4byyMBf1SW9Ur8MHZpJO1r2sS0y CfJ5ZY4hhCjG8Zj9eVhKBRyWcIlCFAC+erPeHvQrQH6fMv9f7PoZjUk0dvtZpw== Message-ID: <9d160a44-7675-51e8-60cf-6d64b76db831@aboutsource.net> Date: Fri, 15 Jul 2022 10:36:06 +0200 MIME-Version: 1.0 Content-Language: de-DE To: pgsql-general@lists.postgresql.org From: Martin Kalcher Subject: Proposal to introduce a shuffle function to intarray extension Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Rspamd-Queue-Id: 4Lkl7W6p46z9slb List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk 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; } }