Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1t2w9j-008kXI-1a for pgsql-hackers@arkaria.postgresql.org; Mon, 21 Oct 2024 17:25:23 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1t2w8i-009kEz-QF for pgsql-hackers@arkaria.postgresql.org; Mon, 21 Oct 2024 17:24:21 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1t2w8i-009kEe-4y for pgsql-hackers@lists.postgresql.org; Mon, 21 Oct 2024 17:24:20 +0000 Received: from mail-lj1-x236.google.com ([2a00:1450:4864:20::236]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1t2w8b-0022jl-64 for pgsql-hackers@postgresql.org; Mon, 21 Oct 2024 17:24:19 +0000 Received: by mail-lj1-x236.google.com with SMTP id 38308e7fff4ca-2fb559b0b00so41625081fa.0 for ; Mon, 21 Oct 2024 10:24:13 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1729531451; x=1730136251; darn=postgresql.org; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=gx20Lw5ZgAScbv0b83YGCqD4bhRZzMkliclfgavWvdk=; b=cVBFFiSjk65vXZ886F4Rgx5fJR0ZqACg9Lt9tVZRm31VpVrSMvcxU1kt356bkjlIba Smcir6+P88+N2jq8rBSo5T14V2RxANvcuj3zK1z7OO3GlHfgJf58Ac4gp6Rjjg4G/166 mRLtKJUAtycBriQvPXGjdN9Pkcf4aZy6Owu4ht/pEzTfJjYhXqJxVYysx2pKGy2H4BL8 O/9D1RgaipjKAk9WrL5uz/YFqifzQx5jpcBvkgmYKFzpEutHQN1u6JVwFHny2ssO9qbZ bO27Qu8Syn+mDs7YvkKL+RUC2wsPj5cOoYoJShn5A6QZSEej7UqtQfZuX37wdVDKYJlr EZZA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1729531451; x=1730136251; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=gx20Lw5ZgAScbv0b83YGCqD4bhRZzMkliclfgavWvdk=; b=kfSIhQosduTtrumU1njCzr6yET9PYcXPaQL3mewmhbSp2rvkXifTSX2W+IoIzgeaI3 gSVF3uf2/2QSLUy6EtZoxAjMLdilM2W7EXcO41xqyQtamq5LEVFeg50L8Mejs+5ENVu3 OlmJt+RJFKWG7mfulaAYDvIIN+pHlNyWLXTMQKYpDyuir4Gv8R7gQMBQI/ODqYDnNdqx 2Dkmt1D7jgrmbbAJ/IjOk8qGl/XMHjIHg3ctnHNZXl4Q9FWlR2iZIbfuE8EG3dAAvfRH 496PYzTTAFI2d35ZH4I5q/Pl2HSBohU3bXK7cbnkp/8u+1uIbFqgKc/XI952oItjUq4A 6/wg== X-Gm-Message-State: AOJu0Yxf5tVPt1GC37FZle3WjdrK15SsoL41nPeqAP8tGnmbgB4bMt7d 5uEDEKz0t/N/9vyktAGxXbbD8SiavUL9pvHF1QbRv8b2HGdKjSHS4wjbGVPsZBfH6Xpj3xXBhHt 5GNhigrHmSfW/FE74Jgo1uxDUxu8= X-Google-Smtp-Source: AGHT+IHD0Boh9HiKOmUrJiojktDMD9FhJnZU1wNIcQz4VBb/AsTCElgSyvdRr1a9vGl+JpHFY2WORsYTJlHMur1uREI= X-Received: by 2002:a05:651c:b0e:b0:2fb:5688:55a4 with SMTP id 38308e7fff4ca-2fb82eaf8a9mr56839921fa.17.1729531450316; Mon, 21 Oct 2024 10:24:10 -0700 (PDT) MIME-Version: 1.0 References: <1342498.1729444411@sss.pgh.pa.us> <1445998.1729482404@sss.pgh.pa.us> In-Reply-To: <1445998.1729482404@sss.pgh.pa.us> From: Michel Pelletier Date: Mon, 21 Oct 2024 10:23:33 -0700 Message-ID: Subject: Re: Using Expanded Objects other than Arrays from plpgsql To: Tom Lane Cc: pgsql-hackers@postgresql.org Content-Type: multipart/alternative; boundary="000000000000b962750624ffebff" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000b962750624ffebff Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Sun, Oct 20, 2024 at 8:46=E2=80=AFPM Tom Lane wrote: > Michel Pelletier writes: > > On Sun, Oct 20, 2024 at 10:13=E2=80=AFAM Tom Lane w= rote: > (from thread https://www.postgresql.org/message-id/CACxu%3DvJaKFNsYxooSnW1wEgsAO5u_v1XYB= acfVJ14wgJV_PYeg%40mail.gmail.com ) > >> But it seems like we could get an easy win by adjusting > >> plpgsql_exec_function along the lines of > >> ... > > > I tried this change and couldn't get it to work, on the next line: > > if (VARATT_IS_EXTERNAL_EXPANDED_RW(DatumGetPointer(var->value))) > > var->value might not be a pointer, as it seems at least from my gdb > > scratching, but say an integer. This segfaults on non-array but > > non-expandable datum. > > We need the same test that exec_assign_value makes, > !var->datatype->typbyval, before it's safe to apply DatumGetPointer. > So line 549 needs to be more like > > - if (!var->isnull && var->datatype->typisarray) > + if (!var->isnull && !var->datatype->typbyval) > > > Another comment that caught my eye was this one: > > > https://github.com/postgres/postgres/blob/master/src/pl/plpgsql/src/pl_ex= ec.c#L8304 > > Not sure what the implication is there. > > Yeah, that's some more unfinished business. I'm not sure if it > matters to your use-case or not. > > BTW, we probably should move this thread to pgsql-hackers. And here we are, thanks for your help on this Tom. For some thread switching context for others, I'm writing a postgres extension that wraps the SuiteSparse:GraphBLAS API and provides new types for sparse and dense matrices and vectors. It's like a combination of numpy and scipy.sparse but for Postgres with an emphasis on graph analytics as sparse adjacency matrices using linear algebra. I use the expandeddatum API to flatten and expand on disk compressed representations of these objects into "live" in-memory objects managed by SuiteSparse. All GraphBLAS objects are opaque handles, and my expanded objects are essentially a box around this handle. I use memory context callbacks to free the handles when the memory context of the box is freed. This works very well and I've made a lot of progress on creating a very clean algebraic API, here are the doctests for matrices, this is all generated from live code! https://onesparse.github.io/OneSparse/test_matrix_header/ Doing some benchmarking I noticed that when writing some simple graph algorithms in plpgsql, my objects were being constantly flattened and expanded. Posting my question above to pgsql-general Tom gave me some tips and suggested I move the thread here. My non-expert summary: plpgsql only optimizes for expanded objects if they are arrays. Non array expanded objects get flattened/expanded on every use. For large matrices and vectors this is very expensive. Ideally I'd like to expand my object, use it throughout the function, return it to another function that may use it, and only flatten it when it goes to disk or it's completely unavoidable. The comment in expandeddatum.h really kind of sells this as one of the main features: * An expanded object is meant to survive across multiple operations, but * not to be enormously long-lived; for example it might be a local variabl= e * in a PL/pgSQL procedure. So its extra bulk compared to the on-disk format * is a worthwhile trade-off. In my case it's not a question of saving bulk, the on disk representation of a matrix is not useful at compute time, it needs to be expanded (using GraphBLAS's serialize/deserialize API) for it to be usable for matrix operations like matmul. In most cases algorithms using these objects iterate in a loop, doing various algebraic operations almost always involving a matmul until they converge on a stable solution or they exhaust the input elements. Here for example is a "minimum parent BFS" that takes a graph and a starting node, and traverses the graph breadth first, computing a vector of every node and its minimum parent id. CREATE OR REPLACE FUNCTION bfs(graph matrix, start_node bigint) > RETURNS vector LANGUAGE plpgsql AS > $$ > DECLARE > bfs_vector vector =3D vector('int32'); > next_vector vector =3D vector('int32'); > BEGIN > bfs_vector =3D set_element(bfs_vector, start_node, 1); > WHILE sssp_vector !=3D next_vector LOOP > next_vector =3D dup(bfs_vector); > bfs_vector =3D vxm(bfs_vector, graph, 'any_secondi_int32', > w=3D>bfs_vector, accum=3D>'min_int32'); > END LOOP; > RETURN bfs_vector; > end; > $$; > (If you're wondering "Why would anyone do it this way" it's because SuiteSparse is optimized for parallel sparse matrix multiplication and has a JIT compiler that can target multiple architectures, at the moment CPUs and CUDA GPUs. Reusing the same Linear Algebra already prevalent in graph theory means not having to think about any low level implementation issues and having code that is completely portable from CPU to GPU or other accelerators). So, I made the two small changes Tom suggested above and I have them in a side fork here: https://github.com/postgres/postgres/compare/master...michelp:postgres-upst= ream:michelp-flatless#diff-0c35024d1576c347689c7abad68abd8562a0aa5f0d2c63d6= d65df4b360b0e807 Good news, my code still works, but bad news is there is still a lot of flattening/expanding/freeing going on at multiple points in each iteration of the algorithm. I'll note too that: BEGIN bfs_vector =3D set_element(sssp_vector, start_node, 1); I'd prefer that to not be an assignment, set_element mutates the object (I eventually plan to support subscripting syntax like bfs_vector[start_node] =3D 1) same with: bfs_vector =3D vxm(bfs_vector, graph, 'any_secondi_int32', w=3D>bfs_vector, accum=3D>'min_int32'); This matmul mutates bfs_vector, I shouldn't need to reassign it back but at the moment it seems necessary otherwise the mutations are lost but this costs a full flatten/expand cycle. Short term my goal is to optimize plpgsql so that my objects stay expanded for the life of the function. Long term there's some "unfinished business" to use Tom's words around the expandeddatum API. I'm not really qualified to speak on these issue but this is my understanding of some of them: - plpgsql knows how to expand arrays and is hardwired for it, but how would it know how to expand other expandable types? - Issues with exec_check_rw_parameter also being hardwired to only optimize expanded objects for array append and prepend, I suspect this has something to do with my issue above about mutating objects in place. I may have missed something but hopefully that brings anyone up to speed interested in this topic. -Michel --000000000000b962750624ffebff Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Sun, Oct 20, 2024 at 8:46=E2=80=AFPM T= om Lane <tgl@sss.pgh.pa.us> = wrote:
Michel Pelletier <pelletier.michel@gmail.com> writes:
> On Sun, Oct 20, 2024 at 10:13=E2=80=AFAM Tom Lane <tgl@sss.pgh.pa.us> wrote:
=

=C2=A0
>> But it seems like we could get an easy win by adjusting
>> plpgsql_exec_function along the lines of
>> ...

> I tried this change and couldn't get it to work, on the next line:=
>=C2=A0 =C2=A0 =C2=A0if (VARATT_IS_EXTERNAL_EXPANDED_RW(DatumGetPointer(= var->value)))
> var->value might not be a pointer, as it seems at least from my gdb=
> scratching, but say an integer.=C2=A0 This segfaults on non-array but<= br> > non-expandable datum.

=C2=A0 We need the same test that exec_assign_value makes,
!var->datatype->typbyval, before it's safe to apply DatumGetPoint= er.
So line 549 needs to be more like

-=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (= !var->isnull && var->datatype->typisarray)
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (= !var->isnull && !var->datatype->typbyval)

> Another comment that caught my eye was this one:
> https://gith= ub.com/postgres/postgres/blob/master/src/pl/plpgsql/src/pl_exec.c#L8304=
> Not sure what the implication is there.

Yeah, that's some more unfinished business.=C2=A0 I'm not sure if i= t
matters to your use-case or not.

BTW, we probably should move this thread to pgsql-hackers.

And here we are, thanks for your help on this Tom.=C2=A0 Fo= r some thread switching context for others, I'm writing a postgres exte= nsion that wraps the SuiteSparse:GraphBLAS API and provides new types for s= parse and dense matrices and vectors.=C2=A0 It's like a combination of = numpy and scipy.sparse but for Postgres with an emphasis on graph analytics= as sparse adjacency matrices using linear algebra.

I use the expandeddatum=C2=A0API to flatten and expand on disk compressed= representations of these objects into "live" in-memory objects m= anaged by SuiteSparse.=C2=A0 All GraphBLAS objects are opaque handles, and = my expanded objects are essentially a box around this handle.=C2=A0 I use m= emory context callbacks to free the handles when the memory context of the = box is freed.=C2=A0 This works very well and I've made a lot of progres= s on creating a very clean algebraic API, here are the doctests for matrice= s, this is all generated from live code!


<= div>Doing some benchmarking I noticed that when writing some simple graph a= lgorithms in plpgsql, my objects were being constantly flattened and expand= ed.=C2=A0 Posting my question above to pgsql-general Tom gave me some tips = and suggested I move the thread here.=C2=A0=C2=A0

= My non-expert summary: plpgsql only optimizes for expanded objects if they = are arrays.=C2=A0 Non array expanded objects get flattened/expanded on ever= y use.=C2=A0 For large matrices and vectors this is very expensive.=C2=A0 I= deally I'd like to expand my object, use it throughout the function, re= turn it to another function that may use it, and only flatten it when it go= es to disk or it's completely unavoidable.=C2=A0 The comment in expande= ddatum.h really kind of sells this as one of the main features:
<= br>
=C2=A0* An expanded object is meant to survive across multipl= e operations, but
=C2=A0* not to be enormously long-lived; for example i= t might be a local variable
=C2=A0* in a PL/pgSQL procedure.=C2=A0 So it= s extra bulk compared to the on-disk format
=C2=A0* is a worthwhile trad= e-off.

In my case it's not a question of s= aving bulk, the on disk representation of a matrix is not useful at compute= time, it=C2=A0needs to be expanded (using GraphBLAS's=C2=A0serialize/d= eserialize API) for it to be usable for matrix operations like matmul.=C2= =A0 In most cases algorithms using these objects iterate in a loop, doing v= arious algebraic operations almost always involving a matmul until they con= verge on a stable solution or they exhaust the input elements.=C2=A0 Here f= or example is a "minimum parent BFS" that takes a graph and a sta= rting node, and traverses the graph breadth first, computing a vector of ev= ery node and its minimum parent id.

CREATE OR REPLACE FUNCTION bfs(graph matri= x, start_node bigint)
=C2=A0 =C2=A0 RETURNS vector LANGUAGE plpgsql AS=C2=A0 =C2=A0 $$
=C2=A0 =C2=A0 DECLARE
=C2=A0 =C2=A0 bfs_vector vec= tor =3D vector('int32');
=C2=A0 =C2=A0 next_vector vector =3D ve= ctor('int32');
=C2=A0 =C2=A0 BEGIN
=C2=A0 =C2=A0 =C2=A0 =C2= =A0 bfs_vector =3D set_element(bfs_vector, start_node, 1);
=C2=A0 =C2=A0= =C2=A0 =C2=A0 WHILE sssp_vector !=3D next_vector LOOP
=C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 next_vector =3D dup(bfs_vector);
=C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 bfs_vector =3D vxm(bfs_vector, graph, 'any_= secondi_int32',
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0w=3D>bfs_vector, acc= um=3D>'min_int32');
=C2=A0 =C2=A0 =C2=A0 =C2=A0 END LOOP;
= =C2=A0 =C2=A0 RETURN bfs_vector;
=C2=A0 =C2=A0 end;
=C2=A0 =C2=A0 $$;=

(If you're wondering "Why wou= ld anyone do it this way" it's because SuiteSparse is optimized fo= r parallel sparse matrix multiplication and has a JIT compiler that can tar= get multiple architectures, at the moment CPUs and CUDA GPUs.=C2=A0 Reusing= the same Linear Algebra already prevalent in graph theory means not having= to think about any low level implementation issues and having code that is= completely portable from CPU to GPU or other accelerators).

=
So, I made the two small changes Tom suggested above and I have = them in a side fork here:


Good news, my code s= till works, but bad news is there is still a lot of flattening/expanding/fr= eeing going on at multiple points in each iteration of the algorithm.=C2=A0= I'll note too that:

=C2=A0 =C2=A0 BEGIN
= =C2=A0 =C2=A0 =C2=A0 =C2=A0 bfs_vector =3D set_element(sssp_vector, start_n= ode, 1);

I'd prefer that to not be an assi= gnment, set_element mutates the object (I eventually plan to support subscr= ipting syntax like bfs_vector[start_node] =3D 1)

s= ame with:

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 bfs_vector =3D vxm(bfs_vector, graph, 'any_secondi_int32',
= =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0w=3D>bfs_vector, accum=3D>'min_int= 32');

This matmul mutates bfs_vector, I sh= ouldn't need to reassign it back but at the moment it seems necessary o= therwise the mutations are lost but this costs a full flatten/expand cycle.=

Short term my goal is to optimize plpgsql so that= my objects stay expanded for the life of the function.=C2=A0 Long term the= re's some "unfinished business" to use Tom's words around= the expandeddatum=C2=A0API.=C2=A0 I'm not really qualified to speak on= these issue but this is my understanding of some of them:

=C2=A0 - plpgsql knows how to expand arrays and is hardwired for i= t, but how would it know how to expand other expandable types?
=C2=A0 - Issues with exec_check_rw_parameter also being hardwi= red to only optimize=C2=A0expanded objects for array append and prepend, I = suspect this has something to do with my issue above about mutating objects= in place.

I may have missed something but hopeful= ly that brings anyone up to speed interested in this topic.

<= /div>
-Michel

--000000000000b962750624ffebff--