Re: Remove restrictions in recursive query

[Renan Alves Fonseca]

On Thu, Mar 27, 2025 at 10:50 PM Tom Lane  wrote:
>
> Renan Alves Fonseca  writes:
> > The solution using GROUP BY in the recursive query is the following:
>
> > with recursive t1(node,nb_path) as
> >  (select 1,1::numeric
> >union all
> >   (select dag.target, sum(nb_path)
> >   from t1 join dag on t1.node=dag.source
> >   group by 1)
> >  ) select sum(nb_path) from t1 join sink_nodes using (node) ;
>
> This is not about the GROUP BY; it's about the SUM().

Cannot SUM() without GROUP BY, right? (I mean the SUM() in the recursive query)

> If you try this example you get
>
> regression=# with recursive t1(node,nb_path) as
>  (select 1,1::numeric
>union all
>   (select dag.target, sum(nb_path)
>   from t1 join dag on t1.node=dag.source
>   group by 1)
>  ) select sum(nb_path) from t1 join sink_nodes using (node) ;
> ERROR:  aggregate functions are not allowed in a recursive query's recursive 
> term
> LINE 4:   (select dag.target, sum(nb_path)
>   ^

Sorry, I forgot to mention that this query only works in my local hack
(I simply removed the check that raises this error message)

> The code says that that restriction is from the SQL spec, and
> it seems to be correct as of SQL:2021.  7.17 
> SR 3)j)ix)5)C) says
>
> C) WQEi shall not contain a  QS such that QS
>immediately contains a  TE that contains a
> referencing WQNX and either of the following is true:
>
>   I) TE immediately contains a  that contains a
>  .
>
>   II) QS immediately contains a  SL that contains
>   either a , or aspecification>, or both.
>
> ( is spec-ese for "aggregate function
> call"

I suspected that this restriction came straight from the specs. I
understand that while the proposed solution can help in some specific
use cases, it is not enough to justify an exception to the spec.

> I don't know the SQL committee's precise reasoning for this
> restriction, but I suspect it's because the recursive query
> expansion is not well-defined in the presence of an aggregate.
> The spec has an interesting comment at the bottom of sub-rule ix:
>
> NOTE 310 — The restrictions insure that each WLEi, viewed as a
> transformation of the query names of the stratum, is monotonically
> increasing. According to Tarski’s fixed point theorem, this
> insures that there is a fixed point. The General Rules use
> Kleene’s fixed point theorem to define a sequence that converges
> to the minimal fixed point.
>
> regards, tom lane

Re: Remove restrictions in recursive query

[Renan Alves Fonseca]

On Thu, Mar 27, 2025 at 7:32 PM Robert Haas  wrote:
>
> > I'll assume that the silence about allowing GROUP BY means it is not a
> > great idea...
>
> I don't think there's really anything to keep you from doing this --
> just put the grouping operation where you refer to the recursive CTE,
> instead of inside the recursive CTE itself. I think allowing it to
> appear inside the recursive CTE would be rather confusing -- it's
> probably best if the mandatory UNION operation is at the top level.
>

I don't think I was clear enough about the proposed improvements. I
hope this example will clarify.

Consider a table representing the edges of a directed acyclic graph.
The following lines will create an example of such a table.

-- create DAG example
\set output_degree 10
\set maxN 2

create temp table dag(source,target) as
   (with recursive t1(source,target) as
 (select 1,1
   union
 select target, target * i from t1, generate_series(2,:output_degree +1) i
 where target*i< :maxN
 ) select * from t1 where source!=target );

Then, suppose we want to count the number of distinct paths from the
root (1) to all sink nodes. We use the following auxiliary table for
the sink nodes:

create temp table sink_nodes(node) as
   (select target from dag except select source from dag);

The solution supported in PostgreSQL is the following:

with recursive t1(node,path) as
 (select 1,array[1]
   union
 select dag.target, t1.path||dag.target
 from t1 join dag on t1.node=dag.source
) select count(*) from t1 join sink_nodes using (node) ;

This query enumerates every path and probably has something like
exponential complexity on the number of edges. It gives these results
in my laptop:
  count
-
 1114163
(1 row)
Time: 8121.044 ms (00:08.121)

The solution using GROUP BY in the recursive query is the following:

with recursive t1(node,nb_path) as
 (select 1,1::numeric
   union all
  (select dag.target, sum(nb_path)
  from t1 join dag on t1.node=dag.source
  group by 1)
 ) select sum(nb_path) from t1 join sink_nodes using (node) ;

At every iteration step, we sum the number of paths that arrived at a
given node. That is another class of algorithm complexity. The first
query cannot scale to larger inputs, while this one can scale. Here is
the result:

   sum
-
 1114163
(1 row)
Time: 27.123 ms

I hope this example made clear that allowing the GROUP BY in the
recursive clause significantly increases the capabilities of doing
analytics on graph data, and it is not only syntax sugar. Please let
me know if there is another way of handling this problem efficiently
without the proposed change.

Thanks again for your attention,
Renan

Remove restrictions in recursive query

[Renan Alves Fonseca]

Hi,

I'm confused about what we should allow in a recursive query. For example,
in the following query:

WITH RECURSIVE t1 AS ( SELECT 1 UNION  SELECT generate_series(2,3) FROM t1
ORDER BY  1 DESC) SELECT * FROM t1 ;

The parser attaches the "order by" clause to the "union" operator, and then
we error out with the following message: "ORDER BY in a recursive query is
not implemented"

The comment in the code (parser_cte.c:900) says "Disallow ORDER BY and
similar decoration atop the UNION". Then, if we wrap the recursive clause
around parentheses:

WITH RECURSIVE t1 AS ( SELECT 1 UNION  (SELECT generate_series(2,3) FROM t1
ORDER BY  1 DESC)) SELECT * FROM t1 ;

It works as expected. So, do we support the ORDER BY in a recursive query
or not? If the answer is yes, I suggest one of the following modifications:
1. Change the error message to something like "ORDER BY at the top level of
a recursive query is not implemented. HINT: wrap the respective statement
around ()"
2. (preferred) Modify the parser or simply remove these checks to allow the
first query.

If the answer is no, then there is a minor bug that allows us to bypass the
check. Even though the ORDER BY happens inside the working table, I think
it can be a useful feature combined with LIMIT and OFFSET.

There is a similar restriction regarding GROUP BY. But in this case, the
error message is very clear and it is consistent with the comment in the
code. I suggest removing this restriction as well in order to improve
PostgreSQL's capabilities to process graph data. For example, counting the
number of paths in a DAG can be computed more efficiently using an
aggregation in each step.

I don't know what the standard says about this, but it certainly does not
allow DISTINCT ON in the recursive query, while PostgreSQL does support it.
So, we could eventually skip the specs in this case to be more consistent
since a DISTINCT ON has many similarities with a GROUP BY.

I did some tests, and it is enough to remove the check regarding the GROUP
BY. The machinery to perform the GROUP BY in a recursive clause is already
there.

Of course, if it is the case, I would be glad to send a patch.

Best regards,
Renan Fonseca

Re: Remove restrictions in recursive query

[Renan Alves Fonseca]

On Thu, Mar 27, 2025 at 7:10 PM David G. Johnston
 wrote:
>
> There is distinct behavior between group by and order by here.  You seem to 
> be mixing them up.
>
> From Select:
>
> select_statement is any SELECT statement without an ORDER BY, LIMIT, FOR NO 
> KEY UPDATE, FOR UPDATE, FOR SHARE, or FOR KEY SHARE clause. (ORDER BY and 
> LIMIT can be attached to a subexpression if it is enclosed in parentheses. 
> Without parentheses, these clauses will be taken to apply to the result of 
> the UNION, not to its right-hand input expression.)
>
> This is the exact same parsing precedence order by is being given in the 
> recursive CTE query situation presented earlier.
>
> David J.
>

You're right. I'm really mixing these 2 here. Thanks for the clarification.

I'll assume that the silence about allowing GROUP BY means it is not a
great idea...

Re: Remove restrictions in recursive query

[Renan Alves Fonseca]

On Thu, Mar 27, 2025 at 5:38 PM Robert Haas  wrote:
> It's not a problem if UNION ALL is used within the initial_query and
> it's not a problem if UNION ALL is used within the iterated_query. But
> you can't apply ORDER BY to the result of the UNION, because the UNION
> is kind of fake -- we're not running the UNION as a single query,
> we're running the two halves separately, the first once and the second
> as many times as needed.

I understand that we can only apply ORDER BY separately in the
initial/iterated query. What disturbs me here is that the UNION
operator has associativity precedence over the ORDER BY only when
inside a recursive CTE. Consider the following query:

SELECT 1 UNION SELECT 1 GROUP BY 1;

It returns 2 rows. The GROUP BY clause attaches to the second
selectStmt without the need to add parenthesis. I would expect the
same syntax inside a recursive CTE.

Re: Remove restrictions in recursive query

[Renan Alves Fonseca]

On Fri, Mar 28, 2025 at 1:14 AM Tom Lane  wrote:
>
> Well, we extend the spec in lots of places.  I'd be okay with removing
> this restriction if I were sure there were no bad consequences, but
> it seems likely that there are some.  College math was way too long
> ago for me to be sure about the "fixed-point" business ... but I think
> what they may be on about is that rows produced by aggregation may not
> be stable in the face of adding more and more rows via additions to

After a quick math review, I'm quite convinced that the "fixed-point"
business applies only to the UNION [DISTINCT] case, in which the
relations can be seen as sets. Recursion with UNION ALL is a
completely different operation. I hope they mention that in the
standard. Consider this very basic recursive query:

WITH RECURSIVE t1 AS ( SELECT 1 UNION ALL SELECT * FROM t1) SELECT * FROM t1;

It does not converge. When using recursive UNION ALL it is the user
responsibility to create the conditions for convergence.

> the recursion workspace.  In your example, I think it somewhat
> accidentally doesn't matter: an underlying row might get picked up
> and added to a dag.target-grouped row in one recursion step or
> a different one, but then you sum all those sums in the top-level
> query, so the top sum comes out the same regardless of just what sets
> the intermediate grouped rows consisted of.  With a different query
> construction though, that would matter.

Not exactly accidental. I'm aware that the first GROUP BY runs in the
scope of the working table, and I'm aware that I can compose the sum
aggregates. Not every aggregate can be composed like that. The
following is the same query without the inner GROUP BY. As you've
mentioned, the SUM is much faster than COUNT (but still it has the
same complexity).

with recursive t1(node,nb_path) as
 (select 1,1::numeric
   union all
  (select dag.target, 1
  from t1 join dag on t1.node=dag.source)
 ) select sum(nb_path) from t1 join sink_nodes using (node) ;

Even if PostgreSQL allowed us to use GROUP BY in the recursive query,
we would be driving the intermediate steps, which feels wrong in a
declarative paradigm. Ideally, we would write the query above and
PostgreSQL would generate the most optimized execution that we've seen
before. I've seen that there is some ongoing work on PARTIAL
AGGREGATES. It would be beautiful if the optimizer could push down the
aggregate into the recursive clause. Does it sound possible?

Regards,
Renan

Document SQL functions behavior regarding custom/generic plan

[Renan Alves Fonseca]

Hi,

In [1], we discussed adding some lines regarding the fact that SQL
functions always use generic plan. Here is the suggested patch. I've
tested on V17 and V12. It does not concern V18.

Regards,
Renan

[1] 
https://www.postgresql.org/message-id/CAApHDvp3EDrVhGjmb21bceJ5-Y7iXKOn2UGG3-ngp_9ob_mpLw%40mail.gmail.com
From ea969fa15edec0bb9e8726860be5660b129ed993 Mon Sep 17 00:00:00 2001
From: "Renan A. Fonseca" 
Date: Tue, 1 Apr 2025 15:53:34 +0200
Subject: [PATCH] Document SQL functions' behavior regarding custom/generic
 plan

---
 doc/src/sgml/xfunc.sgml | 7 +++
 1 file changed, 7 insertions(+)

diff --git a/doc/src/sgml/xfunc.sgml b/doc/src/sgml/xfunc.sgml
index f3a3e4e2f8f..f8058d78fe6 100644
--- a/doc/src/sgml/xfunc.sgml
+++ b/doc/src/sgml/xfunc.sgml
@@ -249,6 +249,13 @@ CALL clean_emp();
  

 
+
+ 
+   Except when inlined, an SQL function is always executed with a
+   generic plan. This behavior may not be desired in some situations.
+ 
+
+

 The syntax of the CREATE FUNCTION command requires
 the function body to be written as a string constant.  It is usually
-- 
2.47.0

Re: [PATCH] Support older Pythons in oauth_server.py

[Renan Alves Fonseca]

Jacob Champion  writes:

>
> This is tested against Python 3.6.15 (3.6 went EOL at the end of
> 2021). I'm working on getting Rocky 8 installed locally to test
> against. If it's decided we want to support downwards to 3.5, I will
> test there too (but I hope we don't; see parent thread).
>

I did a quick test on 3.5. It seems to work after removing
f-strings... At this point, I would be really happy with 3.6.

Re: What's our minimum supported Python version?

[Renan Alves Fonseca]

Tom Lane  writes:

> Florents Tselai  writes:
>> On 19 Apr 2025, at 7:17 PM, Tom Lane  wrote:
>>> I think we need to do some combination of moving our
>>> minimum-supported-version goalposts forward, making sure that
>>> whatever we claim is the minimum Python version is actually
>>> being tested in the buildfarm, and fixing oauth_server.py
>>> so that it works on that version.
>
>> From an Python ecosystem perspective,
>>  3.9 is the usual minimum that people use in CI matrices nowdays.
>> So if it was up to me, that’s what I’d choose. 
>
> Per these numbers, that would be cutting off 31% of the buildfarm,
> including a lot of still-in-support distros such as RHEL8.
> So I would say that's not likely to be our choice.
>
>   regards, tom lane

Also from a python world perspective, we really don't want to run EOL
versions. Besides the security reasons, bugs in thirdy-party
dependencies usually are not fixed and the whole system seems to rot
very quickly.

Of course, this does not happen if one does not rely on third-party
deps. Even in this case, I would say that it is wise to support a
relatively small set because the built-in libs will vary over versions,
and a wide range of versions will cause more troubles like this one.

The oldest non EOL version is 3.9 right now. My suggestion is to follow
the official supported releases. I'm not familiar with the buildfarm,
but I know that python3.6 does not come installed by default in RHEL8,
so instead of installing this version we can simply install 3.9, 3.11 or
3.12.

In a persistent workstation, I believe the following should do the
trick (tested on a 8.5 box):
sudo dnf install python3.12
sudo dnf remove python36

BTW, we are used to create a virtualenv for everything, but that is another 
topic.

Best regards,
Renan Fonseca

Prototype: Implement dead tuples xid histograms

[Renan Alves Fonseca]

Hi hackers,

in a recent hacking workshop organized by Robert Haas, we discussed
[1]. Among the autovacuum issues exposed, the useless vacuum case caught
my attention. I've started to study the respective code and I came up
with a prototype to improve the statistics system regarding dead tuples.

The attached patch implements only partially the dead tuples histogram
mentioned in [1]. But, since I'm a beginner, I thought it would be nice
to have an early feedback just to make sure I don't do anything very
wrong.

My initial idea was to implement a growing histogram with a linked list
of bins, exploiting the fact that most of dead tuples are added in the
last bin. Then, I realized that there are no other cases of dynamical
data structures in pg_stats and it would be harder to serialize
it. That's why I choose to implement the histogram in a static data
structure inside one of the pg_stats data structures. It does require a
little bit more logic to maintain the histogram but it is well
integrated in the whole pg_stats architecture.

As discussed in the hacking workshop, one of the problems is to capture
the exact xmin of the dead tuple. In my tests, I've observed that,
outside of a transaction, xmin corresponds to
GetCurrentTransactionId(). But inside a transaction, xmin receives
incremental xids on successive DM statements. Capturing xids for every
statement inside a transaction seems overkill. So, I decided to
attribute the highest xmin/xid of a transaction to all dead tuples
of that transaction.

In order to see the statistics in a table t1, we do:
select pg_stat_get_dead_tuples_xid_freqs ('t1'::regclass),
   pg_stat_get_dead_tuples_xid_bounds('t1'::regclass);

Then, to verify that the bounds make sense, I've used:
select xmin from t1;

In this version, the removal of dead tuples is not yet implemented, so
these histograms only grow.

I would really appreciate any kind of feedback.

Best regards,
Renan Fonseca

[1] How Autovacuum Goes Wrong: And Can We Please Make It Stop Doing
That? (PGConf.dev 2024)
>From 396eb5ae24fc37af01c81552f656ca628f57 Mon Sep 17 00:00:00 2001
From: "Renan A. Fonseca" 
Date: Wed, 16 Apr 2025 10:52:16 +0200
Subject: [PATCH] Implement dead tuples xid histograms

This is one possible solution to provide finer statistics regarding
dead tuples. It is conceived to answer the following question: If I
vacuum this table now, how many dead tuples will be removed?

We implement it by adding a fixed size data structure in
PgStat_StatTabEntry representing an histogram with variable
bounds. This means that we persist this histogram using pg_catalog
machinery, and we need a pg_catalog version update.

It is out of the scope of this patch to modify the autovacuum
algorithm to use this new information. We provide sql functions to
retrieve dead tuples xid histogram of a given table so that users can
make experiments with this refined info.

Some details on the implementation can be found in comments.

TODO: update the histogram when removing dead tuples
---
 src/backend/access/transam/xact.c|  18 +++
 src/backend/utils/activity/pgstat_relation.c | 147 ++-
 src/backend/utils/adt/pgstatfuncs.c  |  44 ++
 src/include/access/xact.h|   1 +
 src/include/catalog/pg_proc.dat  |   8 +
 src/include/pgstat.h |  29 +++-
 6 files changed, 242 insertions(+), 5 deletions(-)

diff --git a/src/backend/access/transam/xact.c b/src/backend/access/transam/xact.c
index b885513f765..87c9e6d9617 100644
--- a/src/backend/access/transam/xact.c
+++ b/src/backend/access/transam/xact.c
@@ -460,6 +460,24 @@ GetCurrentTransactionId(void)
 	return XidFromFullTransactionId(s->fullTransactionId);
 }
 
+
+/*
+ *	GetCurrentTransactionMaxChildId
+ *
+ * This will return the highest XID among current transaction childs XIDs. It
+ * returns InvalidTransactionId if current transaction has no childs.
+ */
+TransactionId
+GetCurrentTransactionMaxChildId(void)
+{
+	TransactionState s = CurrentTransactionState;
+
+	if (s->nChildXids == 0)
+		return InvalidTransactionId;
+	else
+		return s->childXids[s->nChildXids - 1];
+}
+
 /*
  *	GetCurrentTransactionIdIfAny
  *
diff --git a/src/backend/utils/activity/pgstat_relation.c b/src/backend/utils/activity/pgstat_relation.c
index eeb2d43cb10..08ce3d4ca85 100644
--- a/src/backend/utils/activity/pgstat_relation.c
+++ b/src/backend/utils/activity/pgstat_relation.c
@@ -448,6 +448,14 @@ pgstat_count_truncate(Relation rel)
  * recovery of "delta" dead tuples; so delta_dead_tuples decreases
  * rather than increasing, and the change goes straight into the per-table
  * counter, not into transactional state.
+ *
+ * TODO: we need to take this into account in the dead_tuples_xid
+ * histogram. Actually, this is one of the reasons for using a richer
+ * representation for XIDS in the intermediate data structure
+ * (PgStat_TableStatus.counts). Since this is called quite often in
+ * heap_page_prune_opt, we