Re: [HACKERS] [sqlsmith] Missing CHECK_FOR_INTERRUPTS in tsquery_rewrite

[Tom Lane]

I wrote:
> Also, I think this is outright *wrong* for phrase search --- dropping some
> of the child nodes without any other adjustment isn't valid is it?

After further digging, it seems there's no bug because the tree is
originally binary and QTNTernary won't try to flatten OP_PHRASE nodes.
So we can't actually get to this logic for such nodes.  But seems like
an Assert for that wouldn't be a bad thing.

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

Re: [HACKERS] [sqlsmith] Missing CHECK_FOR_INTERRUPTS in tsquery_rewrite

[Tom Lane]

Andreas Seltenreich  writes:
> testing with sqlsmith yielded an uncancellable backend hogging CPU time.
> Gdb showed it was busy in findeq() of tsquery_rewrite.c.  This function
> appears to have exponential complexity wrt. the size of the involved
> tsqueries.  The following query runs for 12s on my machine with no way
> to cancel it and incrementing the length of the first argument by 1
> doubles this time.

> select ts_rewrite(
>   (select string_agg(i::text, '&')::tsquery from generate_series(1,32) g(i)),
>   (select string_agg(i::text, '&')::tsquery from generate_series(1,19) g(i)),
>   'foo');

> The attached patch adds a CHECK_FOR_INTERRUPTS to make it cancellable.

A CHECK_FOR_INTERRUPTS is probably a good idea, but man is this code
stupid.  It seems to be checking for subset inclusion by forming every
possible subset of the test node and then checking for exact equality
to the target set.  Seems like we should be able to do better.

Also, I think this is outright *wrong* for phrase search --- dropping some
of the child nodes without any other adjustment isn't valid is it?

regards, tom lane


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers

[HACKERS] [sqlsmith] Missing CHECK_FOR_INTERRUPTS in tsquery_rewrite

[Andreas Seltenreich]

Hi,

testing with sqlsmith yielded an uncancellable backend hogging CPU time.
Gdb showed it was busy in findeq() of tsquery_rewrite.c.  This function
appears to have exponential complexity wrt. the size of the involved
tsqueries.  The following query runs for 12s on my machine with no way
to cancel it and incrementing the length of the first argument by 1
doubles this time.

select ts_rewrite(
  (select string_agg(i::text, '&')::tsquery from generate_series(1,32) g(i)),
  (select string_agg(i::text, '&')::tsquery from generate_series(1,19) g(i)),
  'foo');

The attached patch adds a CHECK_FOR_INTERRUPTS to make it cancellable.

regards,
Andreas

>From d9910a96c9bd73c16e29ecaa0577945d5e1c091c Mon Sep 17 00:00:00 2001
From: Andreas Seltenreich 
Date: Sun, 30 Oct 2016 03:25:55 +0100
Subject: [PATCH] Add CHECK_FOR_INTERRUPTS in tsquery_rewrite loop.

The loop in findeq() appears to have exponential complexity and
runtime becomes excessive for more than about 30 tokens in the
tsvectors.  Add a CHECK_FOR_INTERRUPTS to make it cancellable.
---
 src/backend/utils/adt/tsquery_rewrite.c | 4 
 1 file changed, 4 insertions(+)

diff --git a/src/backend/utils/adt/tsquery_rewrite.c b/src/backend/utils/adt/tsquery_rewrite.c
index 28f328d..ef6444f 100644
--- a/src/backend/utils/adt/tsquery_rewrite.c
+++ b/src/backend/utils/adt/tsquery_rewrite.c
@@ -95,6 +95,10 @@ findeq(QTNode *node, QTNode *ex, QTNode *subs, bool *isfind)
 
 			do
 			{
+/* This loop is rather heavyweight, it better be
+ * cancellable. */
+CHECK_FOR_INTERRUPTS();
+
 tnode->sign = 0;
 for (i = 0; i < ex->nchild; i++)
 {
-- 
2.9.3


-- 
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers