COALESCE() does not short-circuit sometimes

classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

COALESCE() does not short-circuit sometimes

Justin Ng
This happens in SQLite 3.28 and 3.31.

Consider the following queries,

-- Query 1
SELECT
  COALESCE(
    NULL,
    (SELECT SUM(9223372036854775807) FROM (SELECT NULL UNION ALL SELECT NULL))
  );

-- Query 2
SELECT
  COALESCE(
    (SELECT 'hello'),
    (SELECT SUM(9223372036854775807) FROM (SELECT NULL UNION ALL SELECT NULL))
  );

-- Query 3
SELECT
  COALESCE(
    (SELECT 'hello'),
    ABS(-9223372036854775808)
  );


Query 1 should throw `integer overflow`.
Query 2 should return 'hello'.
Query 3 should return 'hello'.

However, Query 3 throws `integer overflow`. It should short-circuit and not evaluate ABS()
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: COALESCE() does not short-circuit sometimes

Dominique Devienne
On Wed, Mar 11, 2020 at 12:03 PM Justin Ng <[hidden email]> wrote:
> -- Query 3
> SELECT
>   COALESCE(
>     (SELECT 'hello'),
>     ABS(-9223372036854775808)
>   );
> [...]. It should short-circuit and not evaluate ABS()

Interestingly, found this as well:
https://github.com/AnyhowStep/tsql/issues/233
SQLite COALESCE() does not short-circuit sometimes #233
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: COALESCE() does not short-circuit sometimes

Jose Isaias Cabrera-4
In reply to this post by Justin Ng

Justin Ng, on Wednesday, March 11, 2020 07:03 AM, wrote...

>
> This happens in SQLite 3.28 and 3.31.
>
> Consider the following queries,
>
> -- Query 1
> SELECT
>   COALESCE(
>     NULL,
> (SELECT SUM(9223372036854775807) FROM (SELECT NULL UNION ALL SELECT
> NULL))
>   );

On 3.24.0, this worked correctly:
 8:32:20.56>sqlite3
SQLite version 3.24.0 2018-06-04 19:24:41
Enter ".help" for usage hints.
Connected to a transient in-memory database.
Use ".open FILENAME" to reopen on a persistent database.
sqlite> SELECT
   ...>   COALESCE(
   ...>     NULL,
   ...>     (SELECT SUM(9223372036854775807) FROM (SELECT NULL UNION ALL SELECT NULL))
   ...>   );
Error: integer overflow


> -- Query 2
> SELECT
>   COALESCE(
>     (SELECT 'hello'),
> (SELECT SUM(9223372036854775807) FROM (SELECT NULL UNION ALL SELECT
> NULL))
>   );

Also, on 3.24.0. this worked correctly:
sqlite> SELECT
   ...>   COALESCE(
   ...>     (SELECT 'hello'),
   ...>     (SELECT SUM(9223372036854775807) FROM (SELECT NULL UNION ALL SELECT NULL))
   ...>   );
hello

> -- Query 3
> SELECT
>   COALESCE(
>     (SELECT 'hello'),
>     ABS(-9223372036854775808)
>   );

This one, above, was bad at 3.24.0 also.
sqlite> SELECT
   ...>   COALESCE(
   ...>     (SELECT 'hello'),
   ...>     ABS(-9223372036854775808)
   ...>   );
Error: integer overflow

> Query 1 should throw `integer overflow`.
> Query 2 should return 'hello'.
> Query 3 should return 'hello'.
>
> However, Query 3 throws `integer overflow`. It should short-circuit and
> not evaluate ABS()

Why do you think that that it should not evaluate ABS?  It is there and you asked for it.  I believe it's a good idea to say, "hey, the amount you placed here is out of boundary, think about what you are doing here." IMO, of course. Thanks.

josé
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Hick Gunter
In reply to this post by Dominique Devienne
It is possible to infer, from the EXPLAIN output, that the SQLite program generator attempts to isolate constant expressions and evaluates them first, before it enters the COALESCE loop.

From my experience in reading SQL Programs, the general structure is

GOTO INIT
START:
- load constant values
- load paramters
- open tables
LOOP:
- create next result row
IF end-of-results THEN EXIT ELSE GOTO LOOP
INIT:
- check schema version
- take required locks
- evaluate constant expressions
GOTO START

Which is quite nifty, as it allows stuff unknown until the end of parsing to be appended to the program

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Dominique Devienne
Gesendet: Mittwoch, 11. März 2020 13:19
An: SQLite mailing list <[hidden email]>
Betreff: [EXTERNAL] Re: [sqlite] COALESCE() does not short-circuit sometimes

On Wed, Mar 11, 2020 at 12:03 PM Justin Ng <[hidden email]> wrote:
> -- Query 3
> SELECT
>   COALESCE(
>     (SELECT 'hello'),
>     ABS(-9223372036854775808)
>   );
> [...]. It should short-circuit and not evaluate ABS()

Interestingly, found this as well:
https://github.com/AnyhowStep/tsql/issues/233
SQLite COALESCE() does not short-circuit sometimes #233 _______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: COALESCE() does not short-circuit sometimes

Justin Ng
In reply to this post by Justin Ng
> Why do you think that that it should not evaluate ABS?  It is there and you asked for it.  I believe it's a good idea to say, "hey, the amount you placed here is out of boundary, think about what you are doing here." IMO, of course. Thanks.
>
> josé

Sometimes, when querying data, rather than letting NULLs propagate,
it might be better to throw an error if NULLs are not expected from an expression.

The presence of NULLs might indicate an error in logic, data, or both.

So, the COALESCE(x, ABS(-9223372036854775808)) construct is a hack to sanity-check queries.

Something like THROW_IF_NULL(x)
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: COALESCE() does not short-circuit sometimes

Keith Medcalf

On Wednesday, 11 March, 2020 09:24, Justin Ng <[hidden email]> wrote:

>Sometimes, when querying data, rather than letting NULLs propagate,
>it might be better to throw an error if NULLs are not expected from an
>expression.

>The presence of NULLs might indicate an error in logic, data, or both.

Yes, it very well might.  I believe there is a term for a programmer that uses sentinels and then forgets to handle them.  There is even a diagnostic code for it.  Some people offend themselves when they see the code, however, because it lets their secret out of the bag.


>So, the COALESCE(x, ABS(-9223372036854775808)) construct is a hack to
>sanity-check queries.

It is not a "hack" because it does not work.  It is what is called a "failed attempt" at a hack.

However, your assessment that coalesce is not "short-circuiting" is incorrect.  If x is not null, then x is returned and the constant expression is not returned.  If the constant expression were a correlated expression, then it would not be evaluated in the candidate context.  If x were null and the expression was not constant (and thus required evaluation) then it would be evaluated within the current context and its result returned.

The documentation DOES NOT say that the arguments to coalesce will not be evaluated, merely that the first one that is not-null will be returned.

https://sqlite.org/lang_corefunc.html#coalesce

>Something like THROW_IF_NULL(x)

You could certainly write a function that did that.  It would certainly be better than a "hack" that does not even work.

--
The fact that there's a Highway to Hell but only a Stairway to Heaven says a lot about anticipated traffic volume.




_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Hick Gunter
In reply to this post by Justin Ng
While ORACLE does state that COALESCE will short circuit, SQLite does not.

May I suggest implementing your own user defined function to do this instead.

void THROW_IF_NULL(
    sqlite3_context *ctx,
    int argc,
    sqlite3_value**argv) {

    int ii;

    for( ii == 0; ii < argc; ii++)
    {
        if (sqlite3_value_type(argv[ii]) != SQLITE_NULL)
        {
            sqlite3_result_value(ctx,argv[ii]));
            return;
        }
    }

    sqlite3_result_error(ctx,"NULL or empty", SQLITE_TRANSIENT);
}

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Justin Ng
Gesendet: Mittwoch, 11. März 2020 16:24
An: [hidden email]
Cc: [hidden email]
Betreff: [EXTERNAL] Re: [sqlite] COALESCE() does not short-circuit sometimes

> Why do you think that that it should not evaluate ABS?  It is there and you asked for it.  I believe it's a good idea to say, "hey, the amount you placed here is out of boundary, think about what you are doing here." IMO, of course. Thanks.
>
> josé

Sometimes, when querying data, rather than letting NULLs propagate, it might be better to throw an error if NULLs are not expected from an expression.

The presence of NULLs might indicate an error in logic, data, or both.

So, the COALESCE(x, ABS(-9223372036854775808)) construct is a hack to sanity-check queries.

Something like THROW_IF_NULL(x)
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Richard Hipp-3
On 3/11/20, Hick Gunter <[hidden email]> wrote:
> While ORACLE does state that COALESCE will short circuit,

A similar problem was reported on a ticket here:
https://www.sqlite.org/src/tktview?name=3c9eadd2a6  (The problem
reported on that ticket might not seem to be the same at first glance,
but deep down they are both the same issue.)

I have a patch to fix the problem on a branch
(https://www.sqlite.org/src/timeline?r=do-not-factor-functions) which
you can experiment with. More changes and analysis are needed prior to
landing on trunk.  I cannot guarantee that such a landing will in fact
occur, though it seems more likely than not at this point.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

skywalk
I recently tried using Coalesce() to check existence of a column name.
SELECT DISTINCT COALESCE((SELECT 'AColumnThatDoesNotExist' FROM TD), -999)
FROM TD;
But, the SQL error code dominates? "no such column: AColumnThatDoesNotExist"
Had to resort to:
SELECT name FROM pragma_table_info('TD') WHERE name =
'AColumnThatDoesNotExist';
And oddly, pragma_table_info() fails below if the Table TD is unadorned?
SELECT name FROM pragma_table_info(TD) WHERE name =
'AColumnThatDoesNotExist';

On Wed, Mar 11, 2020 at 2:20 PM Richard Hipp <[hidden email]> wrote:

> On 3/11/20, Hick Gunter <[hidden email]> wrote:
> > While ORACLE does state that COALESCE will short circuit,
>
> A similar problem was reported on a ticket here:
> https://www.sqlite.org/src/tktview?name=3c9eadd2a6  (The problem
> reported on that ticket might not seem to be the same at first glance,
> but deep down they are both the same issue.)
>
> I have a patch to fix the problem on a branch
> (https://www.sqlite.org/src/timeline?r=do-not-factor-functions) which
> you can experiment with. More changes and analysis are needed prior to
> landing on trunk.  I cannot guarantee that such a landing will in fact
> occur, though it seems more likely than not at this point.
>
> --
> D. Richard Hipp
> [hidden email]
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: COALESCE() does not short-circuit sometimes

Justin Ng
In reply to this post by Justin Ng
> It is not a "hack" because it does not work.  It is what is called a "failed attempt" at a hack.

Yeah, the ABS() hack does not work.

Which led me to use `(SELECT SUM(9223372036854775807) FROM (SELECT NULL UNION ALL SELECT NULL))`
which **does** work.

> However, your assessment that coalesce is not "short-circuiting" is incorrect.
> If x is not null, then x is returned and the constant expression is not returned.
> If the constant expression were a correlated expression, then it would not be evaluated in the candidate context.
> If x were null and the expression was not constant (and thus required evaluation)
> then it would be evaluated within the current context and its result returned.
>
> The documentation DOES NOT say that the arguments to coalesce will not be evaluated, merely that the first one that is not-null will be returned.
>
> https://sqlite.org/lang_corefunc.html#coalesce

You're right that the documentation doesn't say so.

I did assume COALESCE() would always short-circuit because the SQL standard says COALESCE() is
equivalent to CASE expressions.

And I was pretty sure CASE expressions should always short-circuit.

However, turns out, CASE expressions don't always short-circuit, either. They generally do short-circuit but there are edge cases where they don't. It isn't entirely intuitive to me what the conditions are, though.

So, I guess I learned something new today.

> > Something like THROW_IF_NULL(x)
>
> You could certainly write a function that did that.  It would certainly be better than a "hack" that does not even work.

I'd rather keep the hack that does work than use a user-defined function, if I can help it.

I feel like user-defined functions should be a last resort.

Thanks for your input, anyway.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: COALESCE() does not short-circuit sometimes

Justin Ng
In reply to this post by Justin Ng
> It is not a "hack" because it does not work.  It is what is called a "failed attempt" at a hack.

Yeah, the ABS() hack does not work.

Which led me to use `(SELECT SUM(9223372036854775807) FROM (SELECT NULL UNION ALL SELECT NULL))`
which **does** work.

> However, your assessment that coalesce is not "short-circuiting" is incorrect.
> If x is not null, then x is returned and the constant expression is not returned.
> If the constant expression were a correlated expression, then it would not be evaluated in the candidate context.
> If x were null and the expression was not constant (and thus required evaluation)
> then it would be evaluated within the current context and its result returned.
>
> The documentation DOES NOT say that the arguments to coalesce will not be evaluated, merely that the first one that is not-null will be returned.
>
> https://sqlite.org/lang_corefunc.html#coalesce

You're right that the documentation doesn't say so.

I did assume COALESCE() would always short-circuit because the SQL standard says COALESCE() is
equivalent to CASE expressions.

And I was pretty sure CASE expressions should always short-circuit.

However, turns out, CASE expressions don't always short-circuit, either. They generally do short-circuit but there are edge cases where they don't. It isn't entirely intuitive to me what the conditions are, though.

So, I guess I learned something new today.

> > Something like THROW_IF_NULL(x)
>
> You could certainly write a function that did that.  It would certainly be better than a "hack" that does not even work.

I'd rather keep the hack that does work than use a user-defined function, if I can help it.

I feel like user-defined functions should be a last resort.

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Justin Ng
In reply to this post by Justin Ng
> I have a patch to fix the problem on a branch
> (https://www.sqlite.org/src/timeline?r=do-not-factor-functions) which
> you can experiment with. More changes and analysis are needed prior to
> landing on trunk.  I cannot guarantee that such a landing will in fact
> occur, though it seems more likely than not at this point.

I remember reporting a bug about COALESCE((... LIMIT 0), x) and you fixed it the very next day.

I forgot to thank you for that!

Thanks for the quick work, as always!

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: COALESCE() does not short-circuit sometimes

Jay Kreibich
In reply to this post by Justin Ng

> On Mar 11, 2020, at 2:16 PM, Justin Ng <[hidden email]> wrote:
>
> They generally do short-circuit but there are edge cases where they don't. It isn't entirely intuitive to me what the conditions are, though.
>


"ABS(-9223372036854775808)" is a constant expression, and as such, it makes sense that it is evaluate during the parse/prepare phase of the processing, not the execution.  There are similar problems in more traditional languages (especially scripting languages) that attempt to optimize out or pre-compute constant expressions.

If that’s the case, then the issue is not so much that the COALESCE() is failing to short-circuit, but rather than the SQL statement failing to “compiling” an invalid statement.

If you’re doing this in code as separate prepare/step/finalize, it would be interesting to see where it fails.  My guess is prepare, not step.

  -j

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Hick Gunter
Exactly what I gained from the EXPLAIN output.

The SQL "compiler" is extracting the constant expression ABS(...) and evaluating it in the program prolog (where schema is checked and locks taken). See instructions 11 and 12

asql> explain select coalesce((SELECT 'hello'),ABS(-9223372036854775808));
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     11    0                    00  Start at 11
1     Once           0     6     0                    00
2     Null           0     2     2                    00  r[2..2]=NULL; Init subquery result
3     Integer        1     3     0                    00  r[3]=1; LIMIT counter
4     String8        0     2     0     hello          00  r[2]='hello'
5     DecrJumpZero   3     6     0                    00  if (--r[3])==0 goto 6
6     SCopy          2     1     0                    00  r[1]=r[2]
7     NotNull        1     9     0                    00  if r[1]!=NULL goto 9
8     SCopy          4     1     0                    00  r[1]=r[4]
9     ResultRow      1     1     0                    00  output=r[1]
10    Halt           0     0     0                    00
11    Int64          0     5     0     -9223372036854775808  00  r[5]=-9223372036854775808
12    Function0      1     5     4     abs(1)         01  r[4]=func(r[5])
13    Goto           0     1     0                    00

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Jay Kreibich
Gesendet: Mittwoch, 11. März 2020 20:53
An: SQLite mailing list <[hidden email]>
Cc: [hidden email]
Betreff: [EXTERNAL] Re: [sqlite] COALESCE() does not short-circuit sometimes


> On Mar 11, 2020, at 2:16 PM, Justin Ng <[hidden email]> wrote:
>
> They generally do short-circuit but there are edge cases where they don't. It isn't entirely intuitive to me what the conditions are, though.
>


"ABS(-9223372036854775808)" is a constant expression, and as such, it makes sense that it is evaluate during the parse/prepare phase of the processing, not the execution.  There are similar problems in more traditional languages (especially scripting languages) that attempt to optimize out or pre-compute constant expressions.

If that’s the case, then the issue is not so much that the COALESCE() is failing to short-circuit, but rather than the SQL statement failing to “compiling” an invalid statement.

If you’re doing this in code as separate prepare/step/finalize, it would be interesting to see where it fails.  My guess is prepare, not step.

  -j

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users


___________________________________________
 Gunter Hick | Software Engineer | Scientific Games International GmbH | Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O) +43 1 80100 - 0

May be privileged. May be confidential. Please delete if not the addressee.
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Richard Hipp-3
On 3/12/20, Hick Gunter <[hidden email]> wrote:
> Exactly what I gained from the EXPLAIN output.
>
> The SQL "compiler" is extracting the constant expression ABS(...) and
> evaluating it in the program prolog (where schema is checked and locks
> taken). See instructions 11 and 12

Exactly.  SQLite tries to factor out constant expressions into the
prologue so that they are only evaluated once, rather than once for
each row.  This is a performance optimization.

A traditional compiler like gcc or clang would do an enormous amount
of code movement, similar to this, as well as other simplifications,
to make the code run faster, especially with options like -O2.  But
the compiler for SQLite does not have that luxury.  Depending on the
query, the time spent compiling the query into byte code can be a
significant fraction of the total running time.  Hence, the compiler
needs to be very fast.  This is an ongoing design struggle with
SQLite:  how many CPU cycles do we burn trying to optimize the
bytecode with the hopes of making up those lost CPU cycles with a
shorter run-time?  Optimization is also constrained by the desire to
keep the SQLite code small.  Hence, the optimizations applied by the
SQLite byte-code compiler are relatively simple, so that they can be
implemented with few CPU cycles and with few bytes of machine code.

Returning to the original discussion:  The underlying problem is that
the constant expressions that get moved into the prologue, if they
involve function calls, might throw an exception.  That is what is
happening with abs(-9223372036854775808).  And that exception prevents
the main body of the code from running, even if the offending
expression was never actually going to be used.  The solution is to
not factor out expressions that use functions, but instead use the
OP_Once opcode (https://www.sqlite.org/opcode.html#Once) to prevent
those expressions from being evaluated more than once.  This seems to
make Coalesce (and CASE...END) short-circuit again.  And it also fixes
ticket https://www.sqlite.org/src/info/3c9eadd2a6ba0aa5

That change is implemented by check-in
https://www.sqlite.org/src/info/c5f96a085db9688a


>
> asql> explain select coalesce((SELECT 'hello'),ABS(-9223372036854775808));
> addr  opcode         p1    p2    p3    p4             p5  comment
> ----  -------------  ----  ----  ----  -------------  --  -------------
> 0     Init           0     11    0                    00  Start at 11
> 1     Once           0     6     0                    00
> 2     Null           0     2     2                    00  r[2..2]=NULL; Init
> subquery result
> 3     Integer        1     3     0                    00  r[3]=1; LIMIT
> counter
> 4     String8        0     2     0     hello          00  r[2]='hello'
> 5     DecrJumpZero   3     6     0                    00  if (--r[3])==0
> goto 6
> 6     SCopy          2     1     0                    00  r[1]=r[2]
> 7     NotNull        1     9     0                    00  if r[1]!=NULL goto
> 9
> 8     SCopy          4     1     0                    00  r[1]=r[4]
> 9     ResultRow      1     1     0                    00  output=r[1]
> 10    Halt           0     0     0                    00
> 11    Int64          0     5     0     -9223372036854775808  00
> r[5]=-9223372036854775808
> 12    Function0      1     5     4     abs(1)         01  r[4]=func(r[5])
> 13    Goto           0     1     0                    00
>
> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]] Im
> Auftrag von Jay Kreibich
> Gesendet: Mittwoch, 11. März 2020 20:53
> An: SQLite mailing list <[hidden email]>
> Cc: [hidden email]
> Betreff: [EXTERNAL] Re: [sqlite] COALESCE() does not short-circuit
> sometimes
>
>
>> On Mar 11, 2020, at 2:16 PM, Justin Ng <[hidden email]>
>> wrote:
>>
>> They generally do short-circuit but there are edge cases where they don't.
>> It isn't entirely intuitive to me what the conditions are, though.
>>
>
>
> "ABS(-9223372036854775808)" is a constant expression, and as such, it makes
> sense that it is evaluate during the parse/prepare phase of the processing,
> not the execution.  There are similar problems in more traditional languages
> (especially scripting languages) that attempt to optimize out or pre-compute
> constant expressions.
>
> If that’s the case, then the issue is not so much that the COALESCE() is
> failing to short-circuit, but rather than the SQL statement failing to
> “compiling” an invalid statement.
>
> If you’re doing this in code as separate prepare/step/finalize, it would be
> interesting to see where it fails.  My guess is prepare, not step.
>
>   -j
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___________________________________________
>  Gunter Hick | Software Engineer | Scientific Games International GmbH |
> Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR: 0430013 | (O)
> +43 1 80100 - 0
>
> May be privileged. May be confidential. Please delete if not the addressee.
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>


--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Doug
Richard, what does the explain look like with your code change, please.
Doug

> -----Original Message-----
> From: sqlite-users <[hidden email]>
> On Behalf Of Richard Hipp
> Sent: Thursday, March 12, 2020 3:09 AM
> To: SQLite mailing list <[hidden email]>
> Subject: Re: [sqlite] [EXTERNAL] Re: COALESCE() does not short-
> circuit sometimes
>
> On 3/12/20, Hick Gunter <[hidden email]> wrote:
> > Exactly what I gained from the EXPLAIN output.
> >
> > The SQL "compiler" is extracting the constant expression
> ABS(...) and
> > evaluating it in the program prolog (where schema is checked and
> locks
> > taken). See instructions 11 and 12
>
> Exactly.  SQLite tries to factor out constant expressions into the
> prologue so that they are only evaluated once, rather than once
> for
> each row.  This is a performance optimization.
>
> A traditional compiler like gcc or clang would do an enormous
> amount
> of code movement, similar to this, as well as other
> simplifications,
> to make the code run faster, especially with options like -O2.
> But
> the compiler for SQLite does not have that luxury.  Depending on
> the
> query, the time spent compiling the query into byte code can be a
> significant fraction of the total running time.  Hence, the
> compiler
> needs to be very fast.  This is an ongoing design struggle with
> SQLite:  how many CPU cycles do we burn trying to optimize the
> bytecode with the hopes of making up those lost CPU cycles with a
> shorter run-time?  Optimization is also constrained by the desire
> to
> keep the SQLite code small.  Hence, the optimizations applied by
> the
> SQLite byte-code compiler are relatively simple, so that they can
> be
> implemented with few CPU cycles and with few bytes of machine
> code.
>
> Returning to the original discussion:  The underlying problem is
> that
> the constant expressions that get moved into the prologue, if they
> involve function calls, might throw an exception.  That is what is
> happening with abs(-9223372036854775808).  And that exception
> prevents
> the main body of the code from running, even if the offending
> expression was never actually going to be used.  The solution is
> to
> not factor out expressions that use functions, but instead use the
> OP_Once opcode (https://www.sqlite.org/opcode.html#Once) to
> prevent
> those expressions from being evaluated more than once.  This seems
> to
> make Coalesce (and CASE...END) short-circuit again.  And it also
> fixes
> ticket https://www.sqlite.org/src/info/3c9eadd2a6ba0aa5
>
> That change is implemented by check-in
> https://www.sqlite.org/src/info/c5f96a085db9688a
>
>
> >
> > asql> explain select coalesce((SELECT 'hello'),ABS(-
> 9223372036854775808));
> > addr  opcode         p1    p2    p3    p4             p5
> comment
> > ----  -------------  ----  ----  ----  -------------  --  ------
> -------
> > 0     Init           0     11    0                    00  Start
> at 11
> > 1     Once           0     6     0                    00
> > 2     Null           0     2     2                    00
> r[2..2]=NULL; Init
> > subquery result
> > 3     Integer        1     3     0                    00
> r[3]=1; LIMIT
> > counter
> > 4     String8        0     2     0     hello          00
> r[2]='hello'
> > 5     DecrJumpZero   3     6     0                    00  if (--
> r[3])==0
> > goto 6
> > 6     SCopy          2     1     0                    00
> r[1]=r[2]
> > 7     NotNull        1     9     0                    00  if
> r[1]!=NULL goto
> > 9
> > 8     SCopy          4     1     0                    00
> r[1]=r[4]
> > 9     ResultRow      1     1     0                    00
> output=r[1]
> > 10    Halt           0     0     0                    00
> > 11    Int64          0     5     0     -9223372036854775808  00
> > r[5]=-9223372036854775808
> > 12    Function0      1     5     4     abs(1)         01
> r[4]=func(r[5])
> > 13    Goto           0     1     0                    00
> >
> > -----Ursprüngliche Nachricht-----
> > Von: sqlite-users [mailto:sqlite-users-
> [hidden email]] Im
> > Auftrag von Jay Kreibich
> > Gesendet: Mittwoch, 11. März 2020 20:53
> > An: SQLite mailing list <[hidden email]>
> > Cc: [hidden email]
> > Betreff: [EXTERNAL] Re: [sqlite] COALESCE() does not short-
> circuit
> > sometimes
> >
> >
> >> On Mar 11, 2020, at 2:16 PM, Justin Ng
> <[hidden email]>
> >> wrote:
> >>
> >> They generally do short-circuit but there are edge cases where
> they don't.
> >> It isn't entirely intuitive to me what the conditions are,
> though.
> >>
> >
> >
> > "ABS(-9223372036854775808)" is a constant expression, and as
> such, it makes
> > sense that it is evaluate during the parse/prepare phase of the
> processing,
> > not the execution.  There are similar problems in more
> traditional languages
> > (especially scripting languages) that attempt to optimize out or
> pre-compute
> > constant expressions.
> >
> > If that’s the case, then the issue is not so much that the
> COALESCE() is
> > failing to short-circuit, but rather than the SQL statement
> failing to
> > “compiling” an invalid statement.
> >
> > If you’re doing this in code as separate prepare/step/finalize,
> it would be
> > interesting to see where it fails.  My guess is prepare, not
> step.
> >
> >   -j
> >
> > _______________________________________________
> > sqlite-users mailing list
> > [hidden email]
> > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-
> users
> >
> >
> > ___________________________________________
> >  Gunter Hick | Software Engineer | Scientific Games
> International GmbH |
> > Klitschgasse 2-4, A-1130 Vienna | FN 157284 a, HG Wien, DVR:
> 0430013 | (O)
> > +43 1 80100 - 0
> >
> > May be privileged. May be confidential. Please delete if not the
> addressee.
> > _______________________________________________
> > sqlite-users mailing list
> > [hidden email]
> > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-
> users
> >
>
>
> --
> D. Richard Hipp
> [hidden email]
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-
> users

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Richard Hipp-3
On 3/12/20, Doug <[hidden email]> wrote:
> Richard, what does the explain look like with your code change, please.

Test case:

CREATE TABLE t1(a);
explain SELECT coalesce(a, abs(-9223372036854775808)) FROM t1;

Before the change:

addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     10    0                    00  Start at 10
1     OpenRead       0     2     0     1              00  root=2 iDb=0; t1
2     Explain        2     0     0     SCAN TABLE t1  00
3     Rewind         0     9     0                    00
4       Column         0     0     1                    00  r[1]=t1.a
5       NotNull        1     7     0                    00  if r[1]!=NULL goto 7
6       SCopy          2     1     0                    00  r[1]=r[2]
7       ResultRow      1     1     0                    00  output=r[1]
8     Next           0     4     0                    01
9     Halt           0     0     0                    00
10    Transaction    0     0     1     0              01  usesStmtJournal=0
11    Int64          0     3     0     -9223372036854775808  00
r[3]=-9223372036854775808
12    Function       1     3     2     abs(1)         00  r[2]=func(r[3])
13    Goto           0     1     0                    00

Notice that the abs() function is invoked in the "prologue" code.  The
prologue begins on instruction 10 and continues through the Goto at
instruction 13.

After the change:

addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     13    0                    00  Start at 13
1     OpenRead       0     2     0     1              00  root=2 iDb=0; t1
2     Explain        2     0     0     SCAN TABLE t1  00
3     Rewind         0     12    0                    00
4       Column         0     0     1                    00  r[1]=t1.a
5       NotNull        1     10    0                    00  if
r[1]!=NULL goto 10
6       Once           0     9     0                    00
7       Int64          0     3     0     -9223372036854775808  00
r[3]=-9223372036854775808
8       Function       1     3     2     abs(1)         00  r[2]=func(r[3])
9       SCopy          2     1     0                    00  r[1]=r[2]
10      ResultRow      1     1     0                    00  output=r[1]
11    Next           0     4     0                    01
12    Halt           0     0     0                    00
13    Transaction    0     0     1     0              01  usesStmtJournal=0
14    Goto           0     1     0                    00

Now the prologue is just instructions 13 and 14 and omits the abs()
function.  The abs() function is now computed on instructions 7 and 8,
but those instructions only run one time due to the "Once" opcode on
instruction 6.

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Doug
Thanks, Richard.

Something triggered me when I looked at the generated code: you use the contents of register 2 for the constant value each time through the loop. What if the select looks like this, with more than one function call in the coalesce? Do you handle it properly?

SELECT coalesce(a, abs(0), abs(1), abs(2)) FROM t1;

Just curious...
Doug

> -----Original Message-----
> From: sqlite-users <[hidden email]>
> On Behalf Of Richard Hipp
> Sent: Thursday, March 12, 2020 7:41 AM
> To: SQLite mailing list <[hidden email]>
> Subject: Re: [sqlite] [EXTERNAL] Re: COALESCE() does not short-
> circuit sometimes
>
> On 3/12/20, Doug <[hidden email]> wrote:
> > Richard, what does the explain look like with your code change,
> please.
>
> Test case:
>
> CREATE TABLE t1(a);
> explain SELECT coalesce(a, abs(-9223372036854775808)) FROM t1;
>
> Before the change:
>
> addr  opcode         p1    p2    p3    p4             p5  comment
> ----  -------------  ----  ----  ----  -------------  --  --------
> -----
> 0     Init           0     10    0                    00  Start at
> 10
> 1     OpenRead       0     2     0     1              00  root=2
> iDb=0; t1
> 2     Explain        2     0     0     SCAN TABLE t1  00
> 3     Rewind         0     9     0                    00
> 4       Column         0     0     1                    00
> r[1]=t1.a
> 5       NotNull        1     7     0                    00  if
> r[1]!=NULL goto 7
> 6       SCopy          2     1     0                    00
> r[1]=r[2]
> 7       ResultRow      1     1     0                    00
> output=r[1]
> 8     Next           0     4     0                    01
> 9     Halt           0     0     0                    00
> 10    Transaction    0     0     1     0              01
> usesStmtJournal=0
> 11    Int64          0     3     0     -9223372036854775808  00
> r[3]=-9223372036854775808
> 12    Function       1     3     2     abs(1)         00
> r[2]=func(r[3])
> 13    Goto           0     1     0                    00
>
> Notice that the abs() function is invoked in the "prologue" code.
> The
> prologue begins on instruction 10 and continues through the Goto
> at
> instruction 13.
>
> After the change:
>
> addr  opcode         p1    p2    p3    p4             p5  comment
> ----  -------------  ----  ----  ----  -------------  --  --------
> -----
> 0     Init           0     13    0                    00  Start at
> 13
> 1     OpenRead       0     2     0     1              00  root=2
> iDb=0; t1
> 2     Explain        2     0     0     SCAN TABLE t1  00
> 3     Rewind         0     12    0                    00
> 4       Column         0     0     1                    00
> r[1]=t1.a
> 5       NotNull        1     10    0                    00  if
> r[1]!=NULL goto 10
> 6       Once           0     9     0                    00
> 7       Int64          0     3     0     -9223372036854775808  00
> r[3]=-9223372036854775808
> 8       Function       1     3     2     abs(1)         00
> r[2]=func(r[3])
> 9       SCopy          2     1     0                    00
> r[1]=r[2]
> 10      ResultRow      1     1     0                    00
> output=r[1]
> 11    Next           0     4     0                    01
> 12    Halt           0     0     0                    00
> 13    Transaction    0     0     1     0              01
> usesStmtJournal=0
> 14    Goto           0     1     0                    00
>
> Now the prologue is just instructions 13 and 14 and omits the
> abs()
> function.  The abs() function is now computed on instructions 7
> and 8,
> but those instructions only run one time due to the "Once" opcode
> on
> instruction 6.
>
> --
> D. Richard Hipp
> [hidden email]
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-
> users

_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Reply | Threaded
Open this post in threaded view
|

Re: [EXTERNAL] Re: COALESCE() does not short-circuit sometimes

Richard Hipp-3
On 3/12/20, Doug <[hidden email]> wrote:
>
> Something triggered me when I looked at the generated code: you use the
> contents of register 2 for the constant value each time through the loop.
> What if the select looks like this, with more than one function call in the
> coalesce? Do you handle it properly?
>
> SELECT coalesce(a, abs(0), abs(1), abs(2)) FROM t1;

addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     23    0                    00  Start at 23
1     OpenRead       0     2     0     1              00  root=2 iDb=0; t1
2     Explain        2     0     0     SCAN TABLE t1  00
3     Rewind         0     22    0                    00
4       Column         0     0     1                    00  r[1]=t1.a
5       NotNull        1     20    0                    00  if
r[1]!=NULL goto 20
6       Once           0     9     0                    00
7       Integer        0     3     0                    00  r[3]=0
8       Function       1     3     2     abs(1)         00  r[2]=func(r[3])
9       SCopy          2     1     0                    00  r[1]=r[2]
10      NotNull        1     20    0                    00  if
r[1]!=NULL goto 20
11      Once           0     14    0                    00
12      Integer        1     5     0                    00  r[5]=1
13      Function       1     5     4     abs(1)         00  r[4]=func(r[5])
14      SCopy          4     1     0                    00  r[1]=r[4]
15      NotNull        1     20    0                    00  if
r[1]!=NULL goto 20
16      Once           0     19    0                    00
17      Integer        2     7     0                    00  r[7]=2
18      Function       1     7     6     abs(1)         00  r[6]=func(r[7])
19      SCopy          6     1     0                    00  r[1]=r[6]
20      ResultRow      1     1     0                    00  output=r[1]
21    Next           0     4     0                    01
22    Halt           0     0     0                    00
23    Transaction    0     0     1     0              01  usesStmtJournal=0
24    Goto           0     1     0                    00

--
D. Richard Hipp
[hidden email]
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users