Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Keith Medcalf]

Unfortunately that is not reliable either because the aux_data is specific to 
the context and each invocation within the statement can have a different 
context.  

What does work is if you use the undocumented cross-context aux_data by using a 
negative argument number (note, since this is undocumented it is liable to 
change in future versions of SQLite3).  Passing the cross-context aux_data 
location as an argument seems to work, eg., expensive_function(-1, rowid, ?99, 
vdata) where -1 is the aux_data location to use, rowid is used in the aux_data 
struct so you know if you can use the cached result, and ?99 and vdata are the 
parameters if calculation is required.

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

>-Original Message-
>From: sqlite-users  On
>Behalf Of Keith Medcalf
>Sent: Thursday, 14 November, 2019 11:16
>To: SQLite mailing list 
>Subject: Re: [sqlite] SQLITE_DETERMINISTIC and custom function
>optimization
>
>>On Thursday, 14 November, 2019 03:52, Dominique Devienne
> wrote:
>
>>>On Sat, Nov 9, 2019 at 1:20 PM Mario M. Westphal  wrote:
>
>>>> Thanks to all the friendly people who commented on my question. Much
>>>> appreciated :-)
>
>>>> I was able to solve this with a small trick:
>>>> I created a small 'state' struct with a rowid and the result (float)
>>>> for that row.
>
>>> Sounds like you re-invented
>>> https://www.sqlite.org/c3ref/get_auxdata.html
>>> but with global state, no?
>>> I replied to your original thread with that link, before seeing this
>>> message. Using the built-in SQLite
>>> mechanism for function caching is much better, because it's clean, and
>>> properly handles the lifetime
>>> of the cache, tying it to the statement execution lifetime.
>
>>get/set auxdata is apparently intended to cache auxillary data
>associated
>>with a CONSTANT provided to a function parameter, not the dynamic result
>>of a computation.  I suppose you could attempt to store your cache
>>results against argument 2 (the table column), however that will
>probably
>>not achieve the effect desired since this is not the purpose of get/set
>>auxdata (read the web page describing it).  And storing it against
>>argument 1 will not work because, although that is a constant, how would
>>you ever know when the *value* of argument 2 changed?
>
>>Maybe I will write a wee test to see if it does work as you think or if
>>it only works as documented.
>
>The function only works as documented in that auxdata set against non-
>constant parameters is not maintained.  This could be made to work with
>"some random function" where one of the parameters is a constant or a
>bound parameter by passing the cache determinant as a parameter and
>caching the determinant and the result against the constant agrument.
>
>eg:
>
>expensive_function(?99, vdata, rowid)
>
>could have a structure containing a arg[2] and the result, and set this
>as auxdata against argument 0 anytime it is computed.  Before computing
>one would check that the retrieved auxdata rowid == arg[2] and if so
>simply return the result from the auxdata.  This assumes that the value
>of vdata is dependant on the value of rowid, of course.
>
>You can of course move the parameters around, but only auxdata stored
>against a constant has a chance of being preserved.  In this case the
>constant is a bound value.  Where there is no constant, you would have to
>"create" one ... eg expensive_function(1, rowid, data1) so that you have
>somewhere to store the auxdata ...
>
>--
>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
>sqlite-users@mailinglists.sqlite.org
>http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users



___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Keith Medcalf]

>On Thursday, 14 November, 2019 03:52, Dominique Devienne  
>wrote:

>>On Sat, Nov 9, 2019 at 1:20 PM Mario M. Westphal  wrote:

>>> Thanks to all the friendly people who commented on my question. Much
>>> appreciated :-)

>>> I was able to solve this with a small trick:
>>> I created a small 'state' struct with a rowid and the result (float)
>>> for that row.

>> Sounds like you re-invented
>> https://www.sqlite.org/c3ref/get_auxdata.html
>> but with global state, no?
>> I replied to your original thread with that link, before seeing this
>> message. Using the built-in SQLite
>> mechanism for function caching is much better, because it's clean, and
>> properly handles the lifetime
>> of the cache, tying it to the statement execution lifetime.

>get/set auxdata is apparently intended to cache auxillary data associated
>with a CONSTANT provided to a function parameter, not the dynamic result
>of a computation.  I suppose you could attempt to store your cache
>results against argument 2 (the table column), however that will probably
>not achieve the effect desired since this is not the purpose of get/set
>auxdata (read the web page describing it).  And storing it against
>argument 1 will not work because, although that is a constant, how would
>you ever know when the *value* of argument 2 changed?

>Maybe I will write a wee test to see if it does work as you think or if
>it only works as documented.

The function only works as documented in that auxdata set against non-constant 
parameters is not maintained.  This could be made to work with "some random 
function" where one of the parameters is a constant or a bound parameter by 
passing the cache determinant as a parameter and caching the determinant and 
the result against the constant agrument.

eg:

expensive_function(?99, vdata, rowid)

could have a structure containing a arg[2] and the result, and set this as 
auxdata against argument 0 anytime it is computed.  Before computing one would 
check that the retrieved auxdata rowid == arg[2] and if so simply return the 
result from the auxdata.  This assumes that the value of vdata is dependant on 
the value of rowid, of course.

You can of course move the parameters around, but only auxdata stored against a 
constant has a chance of being preserved.  In this case the constant is a bound 
value.  Where there is no constant, you would have to "create" one ... eg 
expensive_function(1, rowid, data1) so that you have somewhere to store the 
auxdata ...

-- 
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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Keith Medcalf]

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

On Thursday, 14 November, 2019 03:52, Dominique Devienne  
wrote:

>On Sat, Nov 9, 2019 at 1:20 PM Mario M. Westphal  wrote:

>> Thanks to all the friendly people who commented on my question. Much
>> appreciated :-)

>> I was able to solve this with a small trick:
>> I created a small 'state' struct with a rowid and the result (float)
>> for that row.

> Sounds like you re-invented https://www.sqlite.org/c3ref/get_auxdata.html
> but with global state, no?
> I replied to your original thread with that link, before seeing this
> message. Using the built-in SQLite
> mechanism for function caching is much better, because it's clean, and
> properly handles the lifetime
> of the cache, tying it to the statement execution lifetime.

get/set auxdata is apparently intended to cache auxillary data associated with 
a CONSTANT provided to a function parameter, not the dynamic result of a 
computation.  I suppose you could attempt to store your cache results against 
argument 2 (the table column), however that will probably not achieve the 
effect desired since this is not the purpose of get/set auxdata (read the web 
page describing it).  And storing it against argument 1 will not work because, 
although that is a constant, how would you ever know when the *value* of 
argument 2 changed?

Maybe I will write a wee test to see if it does work as you think or if it only 
works as documented.

> Of course, if you want to tie your cache to a longer lifetime, *across*
> statement executions,
> you can use a global cache independent of SQLite, as it seems you did,
> but
> global state like
> this is rarely a good idea in my experience :). YMMV. --DD



___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Dominique Devienne]

On Sat, Nov 9, 2019 at 1:20 PM Mario M. Westphal  wrote:

> Thanks to all the friendly people who commented on my question. Much
> appreciated :-)
>
> I was able to solve this with a small trick:
> I created a small 'state' struct with a rowid and the result (float) for
> that row.
>

Sounds like you re-invented https://www.sqlite.org/c3ref/get_auxdata.html but
with global state, no?
I replied to your original thread with that link, before seeing this
message. Using the built-in SQLite
mechanism for function caching is much better, because it's clean, and
properly handles the lifetime
of the cache, tying it to the statement execution lifetime.

Of course, if you want to tie your cache to a longer lifetime, *across*
statement executions,
you can use a global cache independent of SQLite, as it seems you did, but
global state like
this is rarely a good idea in my experience :). YMMV. --DD
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Dominique Devienne]

On Fri, Nov 8, 2019 at 9:20 PM Keith Medcalf  wrote:

> [...] The optimizer is prone to calculating things more often than it
> needs to, and is difficult to force to "materialize" things.

Since your expensive function needs to be calculated for every row of the
> table anyway, it would be better to just create a table

that has it calculated once, then compute the updates table, then perform
> the update, then get rid of the extra tables. [...]
>

A better option IMHO is for the function itself to memoize its results, for
the duration of the statement's execution.
That way even if it's called multiple times, you can fetched the cached
result instead of re-performing the expensive computation.

Use https://www.sqlite.org/c3ref/get_auxdata.html for the caching. --DD

PS: Didn't read the whole thread in detail, maybe my answer is a bit off
topic :)
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Mario M. Westphal]

Thanks to all the friendly people who commented on my question. Much
appreciated :-)

 

I was able to solve this with a small trick:

 

I created a small 'state' struct with a rowid and the result (float) for
that row.

Using the "user data" parameter when creating EXPENSIVE_FUNCTION, I supply a
pointer to this struct to the function.

(I have full control over when EXPENSIVE_FUNCTION is created, dropped and
used. This trick may not work in other use cases.)

 

Then I've changed the EXPENSIVE_FUNCTION signature to also take the rowed as
the first parameter: 

 

EXPENSIVE_FUNCTION(rowid,?99,vdata) 

 

EXPENSIVE_FUNCTION uses sqlite3_user_data() to get the state struct pointer
and then compares the rowid parameter with the rowid in the struct.

If they are identical, the cached result is used. Very fast.

Else the result for the requested row is calculated and cached. This is the
slow part.

 

Thanks to this change, EXPENSIVE_FUNCTION needs to perform the slow
calculations in only 46,031 of 91,806 calls. 

In all other cases the cached value from the previous call can be used.

The runtime drops to 2,580ms (from 3,350ms) for the 45K rows sample set.
Which yields a roughly 20% better runtime. Very good.

 

I'm always amazed about what can be achieved with SQLite. Very impressive
product and API design.

 

Thank again for all who provided suggestions and commented.

 

-- Mario

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Keith Medcalf]

>But this makes me think of the upcoming virtual column feature. If you
>define a virtual table column whose value is equal to
>EXPENSIVE_FUNCTION(), do multiple references to that column in a query
>cause multiple calls to the function, or is it computed only once per
>row?

In the present case this will not help since expensive_function is dependent on 
a paramter and a table column ...

However, at present, a virtual column in a table will be calculated whenever it 
is used AND/OR a record is stored to the table containing the column, 
notwithstanding that the column in not stored.  For a stored virtual column it 
will only be calculated when a record is stored.

-- 
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
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Keith Medcalf]

I meant of course the following -- "result" is really ef in the where clause ...

with t(rowid, ef)
  as (
  select distinct rowid,
  expensive_function(?99, vdata)
from some_table
 ),
 u(rowid, vdist, oid, flags)
  as (
  select some_table.rowid,
 ef as vdist,
 ?1 as oid,
 flags | (case when ef < ?2 then ?3 else 0 end)
from some_table
join t 
  on t.rowid == some_table.rowid
   where (flags & ?3) == 0
 and (oid is null and ef < 0.6)
  or ef < vdist
 )
update some_table
   set (vdist, oid, flags) = (select vdist, oid, flags
from u
   where u.rowid = some_table.rowid)
  where some_table.rowid in (select rowid from u)


example, which materializes u, but requires more than one SQL statement, but 
still only requires you provide parameters to one statement:

create temporary table u(rowid integer primary key, vdist, oid, flags);
insert into temp.u
with t(rowid, ef)
  as (
  select distinct rowid,
  expensive_function(?99, vdata)
from some_table
 ),
 u(rowid, vdist, oid, flags)
  as (
  select t.rowid,
 ef as vdist,
 ?1 as oid,
 flags | (case when ef < ?2 then ?3 else 0 end)
from some_table
join t 
  on t.rowid == some_table.rowid
   where (flags & ?3) == 0
 and (oid is null and ef < 0.6)
  or ef < vdist
 )
select rowid, vdist, oid, flags
  from u;
update some_table
   set (vdist, oid, flags) = (select vdist, oid, flags
from temp.u
   where u.rowid = some_table.rowid)
  where some_table.rowid in (select rowid from temp.u)
drop table temp.u;

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

>-Original Message-
>From: Keith Medcalf 
>Sent: Friday, 8 November, 2019 13:21
>To: 'SQLite mailing list' 
>Subject: RE: [sqlite] SQLITE_DETERMINISTIC and custom function
>optimization
>
>
>SQLITE_DETERMINISTIC does not mean that the function is only called once
>for each unique set of arguments, only that when called with a unique set
>of arguments that it returns the same result.  This means that if it is a
>constant it can be factored out of being called more than once.  In your
>case, the parameters are not constant so it must be called once per row.
>
>The optimizer is prone to calculating things more often than it needs to,
>and is difficult to force to "materialize" things.  Since your expensive
>function needs to be calculated for every row of the table anyway, it
>would be better to just create a table that has it calculated once, then
>compute the updates table, then perform the update, then get rid of the
>extra tables.  You could do this in one statement if anyone could figure
>out how to get the optimizer to "materialize" table u in the following
>query (table t is materialized by the distinct, which does nothing other
>than force t to be materialized -- u is not so easy).
>
>with t(rowid, ef)
>  as (
>  select distinct rowid,
>  expensive_function(?99, vdata)
>from some_table
> ),
> u(rowid, vdist, oid, flags)
>  as (
>  select some_table.rowid,
> ef as vdist,
> ?1 as oid,
> flags | (case when ef < ?2 then ?3 else 0 end)
>from some_table
>join t
>  on t.rowid == some_table.rowid
>   where (flags & ?3) == 0
> and (oid is null and ef < 0.6)
>  or result < vdist
> )
>update some_table
>   set (vdist, oid, flags) = (select vdist, oid, flags
>from u
>   where u.rowid = some_table.rowid)
>  where some_table.rowid in (select rowid from u)
>
>
>example, which materializes u, but requires more than one SQL statement,
>but still only requires you provide parameters to one statement:
>
>create temporary table u(rowid integer primary key, vdist, oid, flags);
>insert into temp.u
>with t(rowid, ef)
>  as (
>  select distinct rowid,
>  expensive_function(?99, vdata)
>from some_table
> ),
> u(rowid, vdist, oid, flags)
>  as (
>  select t.rowid,
> ef as vdist,
> ?1 as oid,
> flags | (case when ef < ?2 then ?3 else 0 end)
>from some_table
>join t
>  on t.rowid == some_table.rowid
>   where (flags & ?3) == 0
> and (oid is null and ef < 0.6)
>  or result < vdist
> )

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Keith Medcalf]

SQLITE_DETERMINISTIC does not mean that the function is only called once for 
each unique set of arguments, only that when called with a unique set of 
arguments that it returns the same result.  This means that if it is a constant 
it can be factored out of being called more than once.  In your case, the 
parameters are not constant so it must be called once per row.

The optimizer is prone to calculating things more often than it needs to, and 
is difficult to force to "materialize" things.  Since your expensive function 
needs to be calculated for every row of the table anyway, it would be better to 
just create a table that has it calculated once, then compute the updates 
table, then perform the update, then get rid of the extra tables.  You could do 
this in one statement if anyone could figure out how to get the optimizer to 
"materialize" table u in the following query (table t is materialized by the 
distinct, which does nothing other than force t to be materialized -- u is not 
so easy).

with t(rowid, ef)
  as (
  select distinct rowid,
  expensive_function(?99, vdata)
from some_table
 ),
 u(rowid, vdist, oid, flags)
  as (
  select some_table.rowid,
 ef as vdist,
 ?1 as oid,
 flags | (case when ef < ?2 then ?3 else 0 end)
from some_table
join t 
  on t.rowid == some_table.rowid
   where (flags & ?3) == 0
 and (oid is null and ef < 0.6)
  or result < vdist
 )
update some_table
   set (vdist, oid, flags) = (select vdist, oid, flags
from u
   where u.rowid = some_table.rowid)
  where some_table.rowid in (select rowid from u)


example, which materializes u, but requires more than one SQL statement, but 
still only requires you provide parameters to one statement:

create temporary table u(rowid integer primary key, vdist, oid, flags);
insert into temp.u
with t(rowid, ef)
  as (
  select distinct rowid,
  expensive_function(?99, vdata)
from some_table
 ),
 u(rowid, vdist, oid, flags)
  as (
  select t.rowid,
 ef as vdist,
 ?1 as oid,
 flags | (case when ef < ?2 then ?3 else 0 end)
from some_table
join t 
  on t.rowid == some_table.rowid
   where (flags & ?3) == 0
 and (oid is null and ef < 0.6)
  or result < vdist
 )
select rowid, vdist, oid, flags
  from u;
update some_table
   set (vdist, oid, flags) = (select vdist, oid, flags
from temp.u
   where u.rowid = some_table.rowid)
  where some_table.rowid in (select rowid from temp.u)
drop table temp.u;

This will calculate expensive_function only once per row in some_table.  It 
assumes and requires that "some_table" is a rowid table.

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

>-Original Message-
>From: sqlite-users  On
>Behalf Of Mario M. Westphal
>Sent: Friday, 8 November, 2019 12:08
>To: sqlite-users@mailinglists.sqlite.org
>Subject: [sqlite] SQLITE_DETERMINISTIC and custom function optimization
>
>Hi all,
>
>
>
>I have a table with matrices stored as blobs. Each matrix has about 800
>bytes.
>
>This table has between 20,000 and 500,000 rows.
>
>
>
>I use a custom function "EXPENSIVE_FUNCTION" which performs a calculation
>using a matrix supplied via sqlite3_bind_pointer() as ?99 and the matrix
>in
>the vdata column.
>
>I create the function using the SQLITE_DETERMINISTIC flag. My hope was
>that
>the EXPENSIVE_FUNCTION is called only once per row. But that's not the
>case.
>
>
>
>The query looks like this:
>
>
>
>UPDATE some_table
>
>
>
>SET
>
>vdist = EXPENSIVE_FUNCTION(?99,vdata),
>
>oid = ?1,
>
>flags = flags | (CASE WHEN EXPENSIVE_FUNCTION(?99,vdata) < ?2 THEN ?3
>ELSE 0
>END)
>
>
>
>WHERE
>
>(flags & ?3) = 0  AND
>
>(oid IS NULL AND EXPENSIVE_FUNCTION(?99,vdata) < 0.6) OR
>
>(EXPENSIVE_FUNCTION(?99,vdata) < vdist)
>
>
>
>The EXPENSIVE_FUNCTION function is referred multiple times in the update
>statement. But it always returns the same result (for any given row).
>
>
>
>My stats report that SQLite calls EXPENSIVE_FUNCTION 91,806 times for a
>table with 45,775 rows.
>
>256 rows are modified. This takes (only) 3.3 seconds.
>
>
>
>The profiler tells me that sqlite3VdbeExec() spends 47% in
>vdbeMemFromBtreeResize and 36% in EXPENSIVE_FUNCTION.
>
>
>
>Can I change something so SQLite calls EXPENSIVE_FUNCTION only once per
>row?
>
>
>
>Thanks in advance.
>
>
>
>

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Jens Alfke]

> On Nov 8, 2019, at 11:08 AM, Mario M. Westphal  wrote:
> 
> The EXPENSIVE_FUNCTION function is referred multiple times in the update
> statement. But it always returns the same result (for any given row).

There was a similar thread (that I started, I think) from two years ago with 
subject "Common subexpression optimization of deterministic functions". It's 
worth a read.

The takeaway is that SQLite's query optimizer does not remove redundant calls 
to a deterministic function. IIRC, there weren't any good workarounds for this.

… But this makes me think of the upcoming virtual column feature. If you define 
a virtual table column whose value is equal to EXPENSIVE_FUNCTION(), do 
multiple references to that column in a query cause multiple calls to the 
function, or is it computed only once per row?

—Jens
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

Re: [sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Simon Slavin]

On 8 Nov 2019, at 7:08pm, Mario M. Westphal  wrote:

> The query looks like this:

Try using

EXPLAIN QUERY PLAN on your query.



You might be able to see the two places where your function is called.
___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users

[sqlite] SQLITE_DETERMINISTIC and custom function optimization

[Mario M. Westphal]

Hi all,

 

I have a table with matrices stored as blobs. Each matrix has about 800
bytes.

This table has between 20,000 and 500,000 rows.

 

I use a custom function "EXPENSIVE_FUNCTION" which performs a calculation
using a matrix supplied via sqlite3_bind_pointer() as ?99 and the matrix in
the vdata column.

I create the function using the SQLITE_DETERMINISTIC flag. My hope was that
the EXPENSIVE_FUNCTION is called only once per row. But that's not the case.

 

The query looks like this:

 

UPDATE some_table 

 

SET 

vdist = EXPENSIVE_FUNCTION(?99,vdata), 

oid = ?1, 

flags = flags | (CASE WHEN EXPENSIVE_FUNCTION(?99,vdata) < ?2 THEN ?3 ELSE 0
END)

 

WHERE

(flags & ?3) = 0  AND

(oid IS NULL AND EXPENSIVE_FUNCTION(?99,vdata) < 0.6) OR 

(EXPENSIVE_FUNCTION(?99,vdata) < vdist)

 

The EXPENSIVE_FUNCTION function is referred multiple times in the update
statement. But it always returns the same result (for any given row).

 

My stats report that SQLite calls EXPENSIVE_FUNCTION 91,806 times for a
table with 45,775 rows. 

256 rows are modified. This takes (only) 3.3 seconds.

 

The profiler tells me that sqlite3VdbeExec() spends 47% in
vdbeMemFromBtreeResize and 36% in EXPENSIVE_FUNCTION.

 

Can I change something so SQLite calls EXPENSIVE_FUNCTION only once per row?

 

Thanks in advance.

 

-- Mario

___
sqlite-users mailing list
sqlite-users@mailinglists.sqlite.org
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users