Thread: [sqlsmith] Missing CHECK_FOR_INTERRUPTS in tsquery_rewrite

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

Andreas Seltenreich <seltenreich@gmx.de> 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

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