Обсуждение: Should we have an optional limit on the recursion depth of recursive CTEs?

Should we have an optional, disabled-by-default limit on the
recursion/iteration depth of recursive CTEs to guard against stupid
queries that loop ad infinitum?

I've looked at other database systems that support WITH RECURSIVE
queries, and this idea crops up there. For example, Firebird, the only
other RDBMS that I cared to look at for reasons you can perhaps guess,
has a hard limit of 1024 (though you could argue that that's a
limitation of their implementation, and I'd agree). Maybe the
proprietary databases like SQL server have similar, perhaps even
optional/adjustable limits - I don't know because I didn't check.

I'd suggest that an appropriate interface would be an int GUC with a
GucContext of PGC_SUSET, so that DBAs can impose system-wide limits.

A possible use of such a GUC is to zero in on the actual recursion
depth of the rCTE with the greatest depth in a given query, by
performing a "git bisect" style binary search, setting the GUC
dynamically at each step. It's probably not worth having a proper
interface to do that with, but I can imagine that being a useful trick
in certain narrow situations.

We could also add a similar GUC that can be separately set by
unprivileged users, that independently limits the recursion depth per
session. This could be used as a sort of assertion of the maximum
recursion depth of a given query.

--
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Peter Geoghegan <peter@2ndquadrant.com> writes:
> Should we have an optional, disabled-by-default limit on the
> recursion/iteration depth of recursive CTEs to guard against stupid
> queries that loop ad infinitum?

I think not ...

> I'd suggest that an appropriate interface would be an int GUC with a
> GucContext of PGC_SUSET, so that DBAs can impose system-wide limits.

... and that would be a seriously bad API.  There are not SUSET
restrictions on other resources such as work_mem.  Why do we need
one for this?

By and large, this sounds like a solution looking for a problem.
        regards, tom lane

On Mon, Aug 15, 2011 at 9:31 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> ... and that would be a seriously bad API.  There are not SUSET
> restrictions on other resources such as work_mem.  Why do we need
> one for this?

I think a better analogy would be imposing a maximum number of rows a
query can output. That might be a sane thing to have for some
circumstances but it's not useful in general.

Consider for instance my favourite recursive query application,
displaying the lock dependency graph for pg_locks. What arbitrary
maximum number of locks would you like to impose at which the query
should error out?

There is a situation though that I think is motivating this though
where it would be nice to detect a problem: when the query is such
that it *can't* produce a record because there's an infinite loop
before the first record. Ideally you want some way to detect that
you've recursed and haven't changed anything that could lead to a
change in the recursion condition. But that seems like a pretty hard
thing to detect, probably impossible.


--
greg

On 15 August 2011 21:31, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> I'd suggest that an appropriate interface would be an int GUC with a
>> GucContext of PGC_SUSET, so that DBAs can impose system-wide limits.
>
> ... and that would be a seriously bad API.  There are not SUSET
> restrictions on other resources such as work_mem.  Why do we need
> one for this?

I think that there perhaps /should/ be optional SUSET restrictions on
those resources, particularly work_mem (though I'd suggest a more
sophisticated interface there) - I haven't argued for that because,
respectfully, I already know that to do so would be pretty close to
futile. I have argued for this because I think that an important
distinction can be drawn that might convince those who'd reject the
idea of "poor man's admission control".

The distinction is that the only way that we'll ever be able to guard
against this sort of failure is with an approach that is essentially
equivalent to my proposal - stop trying after some arbitrary number of
some unit of work. I'm sure that you don't need me to tell you that it
has already been proven that solving the halting problem is
impossible. What you may not be aware of is the fact that a proof
exists for PG rCTE's Turing completeness. Consequently, I think that
"solving the halting problem" is the barrier to coming up with
something fundamentally better.

I don't think that your scepticism about the general need to have such
protection is justified; I believe that there is plenty of anecdotal
evidence out there that this is useful in larger commercial contexts,
and I've already named some places where a person might look for such
anecdotal evidence.

--
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

On Mon, Aug 15, 2011 at 23:49, Greg Stark <stark@mit.edu> wrote:
> On Mon, Aug 15, 2011 at 9:31 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> ... and that would be a seriously bad API.  There are not SUSET
>> restrictions on other resources such as work_mem.  Why do we need
>> one for this?
>
> I think a better analogy would be imposing a maximum number of rows a
> query can output. That might be a sane thing to have for some
> circumstances but it's not useful in general.

Uh. You mean like LIMIT, which we already have?

--
 Magnus Hagander
 Me: http://www.hagander.net/
 Work: http://www.redpill-linpro.com/

On 08/16/2011 04:56 AM, Magnus Hagander wrote:
> On Mon, Aug 15, 2011 at 23:49, Greg Stark<stark@mit.edu>  wrote:
>> On Mon, Aug 15, 2011 at 9:31 PM, Tom Lane<tgl@sss.pgh.pa.us>  wrote:
>>> ... and that would be a seriously bad API.  There are not SUSET
>>> restrictions on other resources such as work_mem.  Why do we need
>>> one for this?
>> I think a better analogy would be imposing a maximum number of rows a
>> query can output. That might be a sane thing to have for some
>> circumstances but it's not useful in general.
> Uh. You mean like LIMIT, which we already have?

There is no LIMIT imposed on a query by a server setting, which would be 
the right analogy here.

cheers

andrew

On Tue, Aug 16, 2011 at 7:23 AM, Andrew Dunstan <andrew@dunslane.net> wrote:
> There is no LIMIT imposed on a query by a server setting, which would be the
> right analogy here.

I am not sure I understand any of these analogies.  I think Peter's
point is that it's not very difficult to write (perhaps accidentally)
a CTE that goes into infinite recursion.  In general, we can't detect
that situation, because it's equivalent to the halting problem.  But
there's an old joke about a Turing test (where a computer program must
try to fool a human into believing that it is also human) where the
person asks the computer:

What would the following program do?
10 PRINT "HELLO"
20 GOTO 10

And gets back an infinite stream of HELLO HELLO HELLO HELLO HELLO....

I don't think it's going to be feasible to implement a security
restriction that keeps untrusted users from hosing the machine with a
long running CTE; there are nearly infinitely many ways for an
untrusted user who can run queries to hose the machine, and plugging
one of them imperfectly is going to get us pretty much nowhere.  On
the other hand, there is perhaps a reasonable argument to be made that
we should cut off CTE processing at some point to prevent
*inadvertent* exhaustion of system resources.  Or even query
processing more generally.

In fact, we already have some things sort of like this: you can use
statement_timeout to kill queries that run for too long, and we just
recently added temp_file_limit to kill those that eat too much temp
file space.   I can see a good case for memory_limit and
query_cpu_limit and maybe some others.  cte_recursion_depth_limit
wouldn't be all that high on my personal list, I guess, but the
concept doesn't seem completely insane.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> I don't think it's going to be feasible to implement a security
> restriction that keeps untrusted users from hosing the machine with a
> long running CTE; there are nearly infinitely many ways for an
> untrusted user who can run queries to hose the machine, and plugging
> one of them imperfectly is going to get us pretty much nowhere.  On
> the other hand, there is perhaps a reasonable argument to be made that
> we should cut off CTE processing at some point to prevent
> *inadvertent* exhaustion of system resources.  Or even query
> processing more generally.

Indeed: the real question here is why a recursive CTE is any worse
than, say, an accidentally unconstrained join (or three or four...).

However, we already have a perfectly suitable general mechanism for
that; it's called statement_timeout.

I think we've already had the discussion about whether there should be
a system-wide SUSET maximum statement_timeout, and rejected it on the
grounds that there was not a very clear need for it.

> In fact, we already have some things sort of like this: you can use
> statement_timeout to kill queries that run for too long, and we just
> recently added temp_file_limit to kill those that eat too much temp
> file space.   I can see a good case for memory_limit and
> query_cpu_limit and maybe some others.

temp_file_limit got accepted because it was constraining a resource not
closely related to run time.  I don't think that it provides a precedent
in support of any of these other ideas.
        regards, tom lane

On Tue, Aug 16, 2011 at 10:26 AM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> In fact, we already have some things sort of like this: you can use
>> statement_timeout to kill queries that run for too long, and we just
>> recently added temp_file_limit to kill those that eat too much temp
>> file space.   I can see a good case for memory_limit and
>> query_cpu_limit and maybe some others.
>
> temp_file_limit got accepted because it was constraining a resource not
> closely related to run time.  I don't think that it provides a precedent
> in support of any of these other ideas.

Well, CPU usage might be somewhat closely related to query runtime,
but memory usage sure isn't.

But we digress from $SUBJECT...

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

On 16 August 2011 14:43, Robert Haas <robertmhaas@gmail.com> wrote:
> What would the following program do?
> 10 PRINT "HELLO"
> 20 GOTO 10
>
> And gets back an infinite stream of HELLO HELLO HELLO HELLO HELLO....

heh, that's pretty funny. It also compliments my view, because the
Turing test is only failed because the human eventually thinks "hmm,
he's taking way too long to get to the '...and so on infinitum' bit".

> I don't think it's going to be feasible to implement a security
> restriction that keeps untrusted users from hosing the machine with a
> long running CTE; there are nearly infinitely many ways for an
> untrusted user who can run queries to hose the machine, and plugging
> one of them imperfectly is going to get us pretty much nowhere.

Unless that happens to be the exact area that is a problem for you,
due perhaps to a poorly written application. We're protecting against
Murphy, not Machiavelli - if your users are malicious, or are
motivated by seeing if they can somehow hose the machine for kicks,
clearly all bets are off. This mindset happens to pretty well meet the
needs of industry, IMHO. That said, I admit the case for making a
separate SUSET GUC is the least compelling one I've made on this
thread, if only because of the glaring inconsistency with other areas.

> On the other hand, there is perhaps a reasonable argument to be made that
> we should cut off CTE processing at some point to prevent
> *inadvertent* exhaustion of system resources.  Or even query
> processing more generally.
>
> In fact, we already have some things sort of like this: you can use
> statement_timeout to kill queries that run for too long, and we just
> recently added temp_file_limit to kill those that eat too much temp
> file space.

statement_timeout is far too blunt an instrument to deal with this
problem. For one thing, it may vary based on many external factors,
whereas number of iterations is a consistent, useful metric for the
WITH query in isolation. For another, it prevents the DBA from
managing known problems with deployed apps per database - maybe they
have a reporting query that is expected to take a really long time.
Sure, they can increase statement_timeout when that it run, but that's
another thing to remember.

> I can see a good case for memory_limit and
> query_cpu_limit and maybe some others.  cte_recursion_depth_limit
> wouldn't be all that high on my personal list, I guess, but the
> concept doesn't seem completely insane.

I agree that those things would be much better than this. This is
still a useful, easy-to-implement feature though.

On 16 August 2011 15:26, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Indeed: the real question here is why a recursive CTE is any worse
> than, say, an accidentally unconstrained join (or three or four...).

It's much worse because an unconstrained join query will not
all-of-a-sudden fail to have a terminating condition. It will, for the
most part, take forever or practically forever predictably and
consistently, even as the contents of tables changes over time.

--
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services

Greg Stark wrote:
> On Mon, Aug 15, 2011 at 9:31 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > ... and that would be a seriously bad API. ?There are not SUSET
> > restrictions on other resources such as work_mem. ?Why do we need
> > one for this?
> 
> I think a better analogy would be imposing a maximum number of rows a
> query can output. That might be a sane thing to have for some
> circumstances but it's not useful in general.
> 
> Consider for instance my favourite recursive query application,
> displaying the lock dependency graph for pg_locks. What arbitrary
> maximum number of locks would you like to impose at which the query
> should error out?
> 
> There is a situation though that I think is motivating this though
> where it would be nice to detect a problem: when the query is such
> that it *can't* produce a record because there's an infinite loop
> before the first record. Ideally you want some way to detect that
> you've recursed and haven't changed anything that could lead to a
> change in the recursion condition. But that seems like a pretty hard
> thing to detect, probably impossible.

Actually, using UNION instead of UNION ALL does prevent some infinite
loops:
WITH RECURSIVE source AS (        SELECT 'Hello'        UNION        SELECT 'Hello' FROM source)SELECT * FROM source;

Change that to UNION ALL and you have an infinite loop.

--  Bruce Momjian  <bruce@momjian.us>        http://momjian.us EnterpriseDB
http://enterprisedb.com
 + It's impossible for everything to be true. +

On 20 August 2011 15:34, Bruce Momjian <bruce@momjian.us> wrote:
> Actually, using UNION instead of UNION ALL does prevent some infinite
> loops:

While that is worth pointing out, it cannot be recommended as a way of
preventing infinite recursion; after all, all 5 WITH RECURSIVE
examples in the docs use UNION ALL. It's just a different way of
specifying a terminating condition that isn't likely to be applicable
to more complicated rCTEs.

--
Peter Geoghegan       http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training and Services