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 1tPZUw-00Divt-VT for pgsql-hackers@arkaria.postgresql.org; Mon, 23 Dec 2024 03:52:51 +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 1tPZUw-006pZK-8D for pgsql-hackers@arkaria.postgresql.org; Mon, 23 Dec 2024 03:52:49 +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 1tPZUv-006pZB-QY for pgsql-hackers@lists.postgresql.org; Mon, 23 Dec 2024 03:52:49 +0000 Received: from mail-lj1-x22d.google.com ([2a00:1450:4864:20::22d]) by makus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.96) (envelope-from ) id 1tPZUu-0007gT-0X for pgsql-hackers@lists.postgresql.org; Mon, 23 Dec 2024 03:52:48 +0000 Received: by mail-lj1-x22d.google.com with SMTP id 38308e7fff4ca-30167f4c1e3so41780851fa.3 for ; Sun, 22 Dec 2024 19:52:48 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1734925966; x=1735530766; darn=lists.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=USoVc9JjIhDEOZjYyFj1GWeXtlL/4p76WdGbb3PWZ0A=; b=geLGvH8GuwvjCXxVOpvVDfXiPqkRqNBKHfyMR6Kmg+cSec/O6YjH2TKsohsGQrYX7W xbmqzn0pMj2zK954YXZb81hpPUtdh+dCVs3uTy25pxZaoSrB1QoO8HQRhL+65exqUI7x 3X4pm7f+p7Ns+FrIivc8xNK6O5IYM4lxtH/bkb0sBbMjySbbi7JWgRVYZfaNLPU0sIAl H3dHMxE/7/p8D5jlNueBYwccYwD/QJVeXx3nvo6Lgns2Ib20oYYcoXAH0a0NP4k7x518 4cxZIWmwWSLVmCJY7Vvd59I3PZJ2iXQTnW1VsNw6G0N3l2xdNVnVqWIkWWYJqA97CPEk Jp1w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1734925966; x=1735530766; 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=USoVc9JjIhDEOZjYyFj1GWeXtlL/4p76WdGbb3PWZ0A=; b=U9fy2A10GoQMWCe9b4fWzfflwm1BsV4NWREhwiV6jLe4GO0OWM4T0Fg6gAjOrBS0TA 0L3p+rGtmYhO79Brw3CheR6NM3B1uF1YCAuNs1Gx4c7ojHF8uTmZo1KdVVUTZXa0Rl4u QiU4EvEbB+4f3H3+9VzRETvrE2bvjiks7IGxkwZd+8gKj/XH9KxVsHBglrvo9ZT9d9BK O5vUaehmeWU5ZBuD8iqUX4ZVLSeUo+Y0Fx8Ntw9oV7mCDRHS/lkROT9epHSzDgUY1pzv RdY/3jRXL/udMjUMuAtDcml4CjhV66Bp1VqNkRrrefWckeQC4aH5ylIiY/UAfFTjmFEV SXsg== X-Forwarded-Encrypted: i=1; AJvYcCVhYQszpH4QzlyE1gQbl5oVbqgdt4D4LjwbmHNLoBne24dPEiVio56YwzN9IqbShISFVy+oBrq3qmRtXNQO@lists.postgresql.org X-Gm-Message-State: AOJu0YzqW/4qP2KYPta3q9ht4PNeug2H9EZKv85y5kMEBOAnXazK0kyF qI/gbE3xCy5pyj3+is5ZwYk++A88ljusu0h7A5CMCsLM21JZvNonBdpfv0IV3t9fs1rWLNsqQC2 L60lim8FWwMiHRnqslZTYxduESDY= X-Gm-Gg: ASbGncsW7UdJ9UzkD3iwoGbQ/Q1KVdH52ELeErNwHrZj7/ovKEz6qEFu7pi6LdHMBfA kov04t4jPzVfQbAqlWBwqtpctCJvfngXAQ1KvbA== X-Google-Smtp-Source: AGHT+IGxeQsyND7y47bfqaceg3bcBpkBfSs0n06AUtDvENklcudqJuhDPhoGbaKDeUaXPOBfvou9SvQ7sebgx/KRcG4= X-Received: by 2002:a05:651c:1a0b:b0:302:1aed:f62a with SMTP id 38308e7fff4ca-304685513edmr39684171fa.21.1734925965367; Sun, 22 Dec 2024 19:52:45 -0800 (PST) MIME-Version: 1.0 References: <1342498.1729444411@sss.pgh.pa.us> <1445998.1729482404@sss.pgh.pa.us> <2062830.1729625620@sss.pgh.pa.us> <2265411.1729699470@sss.pgh.pa.us> <2354718.1729737539@sss.pgh.pa.us> <2581216.1729794746@sss.pgh.pa.us> <1948345.1730500073@sss.pgh.pa.us> <3797606.1732045516@sss.pgh.pa.us> <2234661.1733272923@sss.pgh.pa.us> <2811228.1734553329@sss.pgh.pa.us> In-Reply-To: <2811228.1734553329@sss.pgh.pa.us> From: Michel Pelletier Date: Sun, 22 Dec 2024 19:52:08 -0800 Message-ID: Subject: Re: Using Expanded Objects other than Arrays from plpgsql To: Tom Lane Cc: Pavel Stehule , pgsql-hackers@lists.postgresql.org Content-Type: multipart/alternative; boundary="000000000000e0a15b0629e7ed79" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000e0a15b0629e7ed79 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Wed, Dec 18, 2024 at 12:22=E2=80=AFPM Tom Lane wrote= : > Michel Pelletier writes: > > My bad, sorry for the long confusing email, I figured out that I was > > calling the wrong macro when getting my matrix datum and inadvertently > > expanding RO pointers as well, I've fixed that issue, and everything is > > working great! No extra expansions and my support functions are workin= g > > well, I need to go through a few more places in the API to add more > support > > but otherwise the fixes Tom has put into plpgsql have worked perfectly > and > > the library now appears to be behaving optimally! I can get down to > doing > > some benchmarks and head-to-head with the C and Python bindings to > compare > > against. > > So, just to clarify where we're at: you are satisfied that the current > patch-set does what you need? > I have some updates on this thread based on some graph algorithms I've ported from the Python/C graphblas libraries. All of the plpgsql expanded object optimizations so far are working well, I can minimize object expansion in most cases, there are a couple I haven't been able to work around but I'm still getting excellent benchmarking numbers on some large test graphs: LiveJournal Orkut Nodes 3,997,962 3,072,441 Edges 34,681,185 117,185,037 Triangles 177,820,130 627,583,972 Seconds Edges/S Seconds Edges/S Tri Count LL 2.80s 12,386,138 32.03s 3,658,602 Tri Count LU 1.91s 18,157,688 16.38s 7,156,338 Tri Centrality 1.55s 22,374,958 12.22s 9,589,610 Page Rank 8.10s 4,281,628 23.14s 5,064,176 That's on a 2020 era 4 core economy laptop and is in line with what the C/Python/Julia bindings get on similar hardware. There are a few cases where I have to force an expansion, I work around this by calling a `wait()` function, which expands the datum, calls GrB_wait() on it (a nop in this case) and returns a r/w pointer. You can see this in the following Triangle Counting function which is a matrix multiplication of a graph to itself, using itself as a mask. This matrix reduces to the triangle count (times six): create or replace function tcount_b(graph matrix) returns bigint language plpgsql as $$ begin graph =3D wait(graph); graph =3D mxm(graph, graph, 'plus_pair_int32', mask=3D>graph, descr=3D>'s'); return reduce_scalar(graph) / 6; end; $$; DEBUG: new_matrix DEBUG: flatten_matrix DEBUG: matrix_wait DEBUG: expand_matrix -- expansion happens here in wait() DEBUG: new_matrix DEBUG: matrix_mxm -- mxm does not re-expand the object, good! DEBUG: expand_semiring DEBUG: new_semiring DEBUG: new_matrix DEBUG: expand_descriptor DEBUG: new_descriptor DEBUG: matrix_reduce_scalar -- neither does reduce, good! DEBUG: new_scalar DEBUG: scalar_div_int32 DEBUG: new_scalar DEBUG: cast_scalar_int64 If I take out the call to wait(), then mxm calls expand_matrix 3 times as it did before your optimizations. The other task we'd talked about was generalizing the existing > heuristics in exec_assign_value() and plpgsql_exec_function() that > say that array-type values should be forced into expanded R/W form > when being assigned to an array-type PL/pgSQL variable. The argument > for that is that the PL/pgSQL function might subsequently do a lot of > subscripted accesses to the array (which'd benefit from working with > an expanded array) while never doing another assignment and thus not > having any opportunity to revisit the decision. The counter-argument > is that it might *not* do such accesses, so that the expansion was > just a waste of cycles. So this is squishy enough that I'd prefer to > have some solid use-cases to look at before trying to generalize it. > > It's sounding to me like you're going to end up in a place where all > your values are passed around in expanded form already and so you have > little need for that optimization. If so, I'd prefer not to go any > further than the present patch-set for now. Adding "type support" > hooks as discussed would be a substantial amount of work, so I'd > like to have a more compelling case for it before doing that. > I agree it makes sense to have more use cases before making deeper changes. I only work with expanded forms, but need to call wait() to pre-expand the object to avoid multiple expansions in functions that can take the same object in multiple parameters. This is a pretty common pattern in GraphBLAS (and linear algebra in general) where (many) matrices are commutable to themselves in several ways like multiplication, element-wise operations, and element masking. I'm not sure if eliminating wait() is a good enough use case, it would definitely be nice to get rid of but I can document it pretty thoroughly and it's relatively easy to catch. -Michel --000000000000e0a15b0629e7ed79 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Wed, Dec 18, 2024 at 12:22=E2=80=AFPM = Tom Lane <tgl@sss.pgh.pa.us>= wrote:
Michel Pelletier <pelletier.michel@gmail.com> writes:
> My bad, sorry for the long confusing email, I figured out that I was > calling the wrong macro when getting my matrix datum and inadvertently=
> expanding RO pointers as well, I've fixed that issue, and everythi= ng is
> working great!=C2=A0 No extra expansions and my support functions are = working
> well, I need to go through a few more places in the API to add more su= pport
> but otherwise the fixes Tom has put into plpgsql have worked perfectly= and
> the library now appears to be behaving optimally!=C2=A0 I can get down= to doing
> some benchmarks and head-to-head with the C and Python bindings to com= pare
> against.

So, just to clarify where we're at: you are satisfied that the current<= br> patch-set does what you need?

I have some updates on this thread based on some graph algorithms I'= ve ported from the Python/C graphblas libraries.

All of = the plpgsql expanded object optimizations so far are working well, I can mi= nimize object expansion in most cases, there are a couple I haven't bee= n able to work around but I'm still getting excellent benchmarking numb= ers on some large test graphs:

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 LiveJournal = =C2=A0 =C2=A0 =C2=A0 =C2=A0 Orkut
Nodes =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 3,997,962 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 3,072,441
Edges =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 34,681,185 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A011= 7,185,037
Triangles =C2=A0 =C2=A0 =C2=A0 177,820,130 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 627,583,972

=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 Seconds Edges/S =C2=A0 =C2=A0 Seconds Edges/S
Tri Count LL = =C2=A0 =C2=A02.80s =C2=A0 12,386,138 =C2=A032.03s =C2=A03,658,602
Tri Co= unt LU =C2=A0 =C2=A01.91s =C2=A0 18,157,688 =C2=A016.38s =C2=A07,156,338Tri Centrality =C2=A01.55s =C2=A0 22,374,958 =C2=A012.22s =C2=A09,589,610<= br>Page Rank =C2=A0 =C2=A0 =C2=A0 8.10s =C2=A0 4,281,628 =C2=A0 23.14s =C2= =A05,064,176

That's on a 2020 era 4 core econ= omy=C2=A0laptop and is in line with what the C/Python/Julia bindings get on= similar hardware.

There are a few cases wher= e I have to force an expansion,=C2=A0I work around this by calling a `wait()` function, which expa= nds the datum, calls GrB_wait() on it (a nop in this case) and returns a r/= w pointer.=C2=A0 You can see this in the following Triangle Counting functi= on which is a matrix multiplication of a graph to itself, using itself as a= mask.=C2=A0 This matrix reduces to the triangle count (times six):<= /div>

create or = replace function tcount_b(graph matrix) returns bigint language plpgsql as<= br>=C2=A0 =C2=A0 $$
=C2=A0 =C2=A0 begin
=C2=A0 =C2=A0 =C2=A0 =C2=A0 g= raph =3D wait(graph);
=C2=A0 =C2=A0 =C2=A0 =C2=A0 graph =3D mxm(graph, g= raph, 'plus_pair_int32', mask=3D>graph, descr=3D>'s')= ;
=C2=A0 =C2=A0 =C2=A0 =C2=A0 return reduce_scalar(graph) / 6;
=C2=A0= =C2=A0 end;
=C2=A0 =C2=A0 $$;

DEBUG: =C2=A0new_matrix
DEBUG: =C2=A0flatten= _matrix
DEBUG: =C2=A0matrix_wait
DEBUG: =C2=A0expand_matrix=C2=A0 -- = expansion happens here in wait()
DEBUG: =C2=A0new_matrix
DEBUG: =C2= =A0matrix_mxm=C2=A0 =C2=A0 =C2=A0 -- mxm does not re-expand the object, goo= d!
DEBUG: =C2=A0expand_semiring
DEBUG: =C2=A0new_semiring
DEBUG: = =C2=A0new_matrix
DEBUG: =C2=A0expand_descriptor
DEBUG: =C2=A0new_desc= riptor
DEBUG: =C2=A0matrix_reduce_scalar=C2=A0 -- neither does reduce, g= ood!
DEBUG: =C2=A0new_scalar
DEBUG: =C2=A0scalar_div_int32
DEBUG: = =C2=A0new_scalar
DEBUG: =C2=A0cast_scalar_int64

If I take out the call to wait(), then mxm calls expand_matrix 3 times a= s it did before your optimizations.

The other task we'd talked about was generalizing the existing
heuristics in exec_assign_value() and plpgsql_exec_function() that
say that array-type values should be forced into expanded R/W form
when being assigned to an array-type PL/pgSQL variable.=C2=A0 The argument<= br> for that is that the PL/pgSQL function might subsequently do a lot of
subscripted accesses to the array (which'd benefit from working with an expanded array) while never doing another assignment and thus not
having any opportunity to revisit the decision.=C2=A0 The counter-argument<= br> is that it might *not* do such accesses, so that the expansion was
just a waste of cycles.=C2=A0 So this is squishy enough that I'd prefer= to
have some solid use-cases to look at before trying to generalize it.

It's sounding to me like you're going to end up in a place where al= l
your values are passed around in expanded form already and so you have
little need for that optimization.
=C2=A0 If so, I'd prefer not to go any
further than the present patch-set for now.=C2=A0 Adding "type support= "
hooks as discussed would be a substantial amount of work, so I'd
like to have a more compelling case for it before doing that.

I agree it makes sense to have more use cases before= making deeper changes.=C2=A0 I only work with expanded forms,=C2=A0 but ne= ed to call wait() to pre-expand the object to avoid multiple expansions in = functions that can take the same object in multiple parameters.=C2=A0 This = is a pretty common pattern in GraphBLAS (and linear algebra in general) whe= re (many) matrices are commutable to themselves in several ways like multip= lication, element-wise operations, and element masking.

I'm not sure if eliminating wait() is a good enough use case, it = would definitely be nice to get rid of but I can document it pretty thoroug= hly and it's relatively easy to catch.=C2=A0
=C2=A0

-Michel
--000000000000e0a15b0629e7ed79--