Re: [sqlite] Query optimizer and recursive common table expressions
Hello, On 2018-01-04 01:53, R Smith wrote: Not to mention that if you wait several years, depending on your processor/compiler, the integer 64 value might wrap around and x<=3 might become true once more, producing rows again :) Unfortunately, it will be stuck when int becomes double (at 9223372036854775808 -- still much time :-). ``We are programmers and responsible for programming. -O99 is responsible for thinking. Who in the hell implemented -O when there had not been -O?'' :-) -- best regards Cezary H. Noweta ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] Query optimizer and recursive common table expressions
On 2018/01/04 12:36 AM, Richard Hipp wrote: On 1/3/18, Shane Devwrote: sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt) select * from cnt where x <= 3; [no sqlite> prompt, CPU utilization 25%] I assume sqlite is recursively adding rows to the queue without considering that the subsequent SELECT only needs the first 3 of them. No, it is continuing to search for rows for which x<=3. The query planner does not know enough algebra to figure out that that will never happen again after the first three rows. Not to mention that if you wait several years, depending on your processor/compiler, the integer 64 value might wrap around and x<=3 might become true once more, producing rows again :) ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [SPAM] Re: Emulate right-join
Hello, On 2017-12-06 19:07, R Smith wrote: You mean make SQLite less Lite, but with Zero computational advantage, by simply adding syntactic sugar bloat? - I'm going to have to vote No on that. (Luckily my vote counts extremely little.) I think the reason SQLite never implemented it is precisely because of the fact that it simply amounts to syntactic specialization and no real computational advantage. That said, I'm not against adding those joins, just perhaps implemented in a most-efficient way rather than a simple transcription of my lazy-code. (Unless of course that ends up being the most efficient way to do it.) I'm all with you. You have taken my words. CROSS OUTER joins as simple UNION of both joins are (or can be) very inefficient, especially when a number of widow records is relatively small (as compared to a number of all records) -- this results in two, long running joins, one of which goes to a vacuum. I can see real, however negative, computational advantage. Although that way is a very good academic illustration of OUTER joins. -- best regards Cezary H. Noweta ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] Query optimizer and recursive common table expressions
On 1/3/18, Shane Devwrote: > > sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt) > select * from cnt where x <= 3; > [no sqlite> prompt, CPU utilization 25%] > > I assume sqlite is recursively adding rows to the queue without considering > that the subsequent SELECT only needs the first 3 of them. No, it is continuing to search for rows for which x<=3. The query planner does not know enough algebra to figure out that that will never happen again after the first three rows. -- D. Richard Hipp d...@sqlite.org ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] Query optimizer and recursive common table expressions
I have just spotted a couple of typos in my email below. The first two common table expressions should have been as follows - with recursive cnt(x) as (select 1 union all select x+1 from cnt limit 3) select * from cnt; with recursive cnt(x) as (select 1 union all select x+1 from cnt) select * from cnt limit 3; On 3 January 2018 at 23:24, Shane Devwrote: > Hi, > > This simple recursive common table expression returns all integers from 1 > to 3 as expected - > > sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt > limit 3) select * from cnt where x; > x > 1 > 2 > 3 > sqlite> > > If the LIMIT constraint is moved from the compound SELECT to the > subsequent SELECT, it works the same - > > sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt) > select * from cnt where x limit 3; > x > 1 > 2 > 3 > sqlite> > > If the LIMIT constraint is replaced with a WHERE constraint in the > compound SELECT, it still works the same - > > sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt > where x < 3) select * from cnt; > x > 1 > 2 > 3 > sqlite> > > However if the WHERE constraint is moved from the compound SELECT to the > subsequent SELECT and adjusted slightly, it selects correct results but > then hangs indefinitely - > > sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt) > select * from cnt where x <= 3; > x > 1 > 2 > 3 > [no sqlite> prompt, CPU utilization 25%] > > I assume sqlite is recursively adding rows to the queue without > considering that the subsequent SELECT only needs the first 3 of them. > > Can we conclude the query planner is unable to optimize the compound > SELECT (the part in brackets) based on the WHERE constraint of the > subsequent SELECT statement? > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
[sqlite] Query optimizer and recursive common table expressions
Hi, This simple recursive common table expression returns all integers from 1 to 3 as expected - sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt limit 3) select * from cnt where x; x 1 2 3 sqlite> If the LIMIT constraint is moved from the compound SELECT to the subsequent SELECT, it works the same - sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt) select * from cnt where x limit 3; x 1 2 3 sqlite> If the LIMIT constraint is replaced with a WHERE constraint in the compound SELECT, it still works the same - sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt where x < 3) select * from cnt; x 1 2 3 sqlite> However if the WHERE constraint is moved from the compound SELECT to the subsequent SELECT and adjusted slightly, it selects correct results but then hangs indefinitely - sqlite> with recursive cnt(x) as (select 1 union all select x+1 from cnt) select * from cnt where x <= 3; x 1 2 3 [no sqlite> prompt, CPU utilization 25%] I assume sqlite is recursively adding rows to the queue without considering that the subsequent SELECT only needs the first 3 of them. Can we conclude the query planner is unable to optimize the compound SELECT (the part in brackets) based on the WHERE constraint of the subsequent SELECT statement? ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] Emulate right-join
In lieu of adding the syntactic sugar, might it be worth documenting the alternative(s)? Currently the docs for these are "https://sqlite.org/omitted.html; - which simply says: "LEFT OUTER JOIN is implemented, but not RIGHT OUTER JOIN or FULL OUTER JOIN." A couple of lines saying why this isn't really a problem because it can be worked around apparently fairly easily could be helpful to us lay-users of SQL. On Wed, 06 Dec 2017 18:07:37 + R Smith rsm...@rsweb.co.za wrote On 2017/12/06 6:35 PM, Christian Schmitz wrote: Actually, the left outer join is sufficient to execute all the outer join operators: - right outer join: just swap the "from" arguments - full outer joins: union of left and right outer joins Couldn’t SQLite implement that and do the swap for us? As well as the union thing? You mean make SQLite less Lite, but with Zero computational advantage, by simply adding syntactic sugar bloat? - I'm going to have to vote No on that. (Luckily my vote counts extremely little.) I think the reason SQLite never implemented it is precisely because of the fact that it simply amounts to syntactic specialization and no real computational advantage. That said, I'm not against adding those joins, just perhaps implemented in a most-efficient way rather than a simple transcription of my lazy-code. (Unless of course that ends up being the most efficient way to do it.) ___ 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] Efficient query to count number of leaves in a DAG.
Playing devils advocate, there may be a purpose to those aliases (Application code requirement, which can't be changed), and/or, the single letter aliases are documented and understood throughout the application. But, you're absolutely correct. The only time I personally use single letter variables is when I'm doing tight loops. Like "for x:=.." and "X" doesn't go beyond what can be read in 10pt font on a 640x480 screen. Its a throw back to my C64 coding days. ;) On Wed, Jan 3, 2018 at 9:55 AM, David Raymondwrote: > A couple things... > > I recommend using longer names than 1 letter for your aliases, what you > save in typing you lose a couple times over again when wondering what "r" > is or why "t" has anything to do with "nodes" > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] Efficient query to count number of leaves in a DAG.
A couple things... I recommend using longer names than 1 letter for your aliases, what you save in typing you lose a couple times over again when wondering what "r" is or why "t" has anything to do with "nodes" In your CTE you're doing a 3 table join. There's no need to include the nodes table in there at all, you can get the node ID from the edge table. ...union all select e.child, top from r, edges as e where e.parent = r.id)... The big thing though is in the where clause. where...and id not in (select parent from edges where parent = id)... The "where parent = id" bit turns that into a sub query, meaning it runs it once for each row. It's kind of saying "where X is in the bucket of (X's that are in the bucket of Y's)" If you get rid of that... where...and id not in (select parent from edges)... It becomes a non-correlated sub query which only has to be run once. "where X is in the bucket of Y's" Making those 2 tweaks to your query let's look at the plans. You can see we drop the search of the nodes table, and subquery 4 is no longer correlated. Old: sqlite> explain query plan with recursive r (id, top) as (select id, id from nodes union all select t.id, top from nodes as t, edges as e, r where e.parent = r.id and t.id = e.child) select top, count(*) from r where top != id and id not in (select parent from edges where parent = id) group by top; selectid|order|from|detail 2|0|0|SCAN TABLE nodes 3|0|1|SCAN TABLE edges AS e 3|1|0|SEARCH TABLE nodes AS t USING INTEGER PRIMARY KEY (rowid=?) 3|2|2|SCAN TABLE r 1|0|0|COMPOUND SUBQUERIES 0 AND 0 (UNION ALL) 0|0|0|SCAN SUBQUERY 1 0|0|0|EXECUTE CORRELATED LIST SUBQUERY 4 4|0|0|SCAN TABLE edges 0|0|0|USE TEMP B-TREE FOR GROUP BY New: sqlite> explain query plan with recursive r (id, top) as (select id, id from nodes union all select e.child, top from edges as e, r where e.parent = r.id) select top, count(*) from r where top != id and id not in (select parent from edges) group by top; selectid|order|from|detail 2|0|0|SCAN TABLE nodes 3|0|0|SCAN TABLE edges AS e 3|1|1|SCAN TABLE r 1|0|0|COMPOUND SUBQUERIES 0 AND 0 (UNION ALL) 0|0|0|SCAN SUBQUERY 1 0|0|0|EXECUTE LIST SUBQUERY 4 4|0|0|SCAN TABLE edges 0|0|0|USE TEMP B-TREE FOR GROUP BY Now give your modified query a go and let me know how it compares to what I came up with. -Original Message- From: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org] On Behalf Of Shane Dev Sent: Wednesday, January 03, 2018 12:45 AM To: SQLite mailing list Subject: Re: [sqlite] Efficient query to count number of leaves in a DAG. Hi David, Nice work! your query is far quicker than mine- even without the reverseEdges index. I think you are right about the problem of potentially double counting leaves. There weren't any multi-parent nodes in my test data so I didn't notice this mistake. Could you please explain why your query is so much faster? On 2 January 2018 at 17:50, David Raymondwrote: > I think you need a union there instead of a union all. Otherwise you're > double (or more) counting leaves where there is more than 1 path to get to > the leaf. > > I don't have a large dataset to test it on, but how about something like: > > create table nodes > ( > id integer primary key, > description text > ); > > create table edges > ( > parent int not null references nodes, > child int not null references nodes, > primary key (parent, child), > check (parent != child) > ) without rowid; > create index reverseEdges on edges (child, parent); > > create view leafCounts as with recursive > leaves (id) as ( > select nodes.id > from nodes left outer join edges > on nodes.id = edges.parent > where edges.parent is null > ), > paths (parent, child) as ( > select parent, child from edges > union > select paths.parent, edges.child > from paths inner join edges > on paths.child = edges.parent > ) > select parent, count(*) as leafCount > from paths > where child in leaves > group by parent; > > > -Original Message- > From: sqlite-users [mailto:sqlite-users-boun...@mailinglists.sqlite.org] > On Behalf Of Shane Dev > Sent: Monday, January 01, 2018 11:14 AM > To: SQLite mailing list > Subject: [sqlite] Efficient query to count number of leaves in a DAG. > > Hi, > > I want to the count the number of leaves (descendants without children) for > each node in a DAG > > DAG definition - > > CREATE TABLE nodes(id integer primary key, description text); > CREATE TABLE edges(parent not null references nodes, child not null > references nodes, primary key(parent, child)); > > My query - > > CREATE VIEW v_count_leaves as with recursive r(id, top) as ( > select id, id from nodes > union all > select t.id, top from nodes as t, edges as e, r where e.parent=r.id and > t.id > =e.child) > select top, count(*) from r where top<>id and id not in (select parent from > edges where parent=id) group by top; > > It seems to work but is complex to understand and
Re: [sqlite] Loadable extension with shared state
On 03/01/2018 15:48, Richard Hipp wrote: On 1/3/18, Lifepillarwrote: Consider an extension that has some shared state, say a global `context` struct, whose value is used by a few user-defined SQL functions. Besides, assume that there are other SQL functions that can act on the global context. The question is: how do I turn this into a thread-safe extension? Should I use SQLite3 mutex functions to guarantee exclusive access to shared state? Or should I define my own locks? Either approach will work. Which is easiest for you? If SQLite3 locks may be used in loadable extensions, it is fine with me. Thanks for the quick feedback! Life. ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] Loadable extension with shared state
On 1/3/18, Lifepillarwrote: > Consider an extension that has some shared state, say a global `context` > struct, whose value is used by a few user-defined SQL functions. > Besides, assume that there are other SQL functions that can act on the > global context. > > The question is: how do I turn this into a thread-safe extension? > > Should I use SQLite3 mutex functions to guarantee exclusive access to > shared state? Or should I define my own locks? Either approach will work. Which is easiest for you? -- D. Richard Hipp d...@sqlite.org ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
[sqlite] Loadable extension with shared state
Consider an extension that has some shared state, say a global `context` struct, whose value is used by a few user-defined SQL functions. Besides, assume that there are other SQL functions that can act on the global context. The question is: how do I turn this into a thread-safe extension? Should I use SQLite3 mutex functions to guarantee exclusive access to shared state? Or should I define my own locks? Is there an idiomatic way to deal with cases like this in SQLite3? Thanks, Life. ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] pragma table_info return column delimiters?
On 2018/01/03 12:15 PM, Bart Smissaert wrote: Is there a way with pragma table_info or otherwise (other than parsing the table create statement from SQLite_master) to get the column names including the column delimiters, eg double quotes or square brackets? So I would get eg: [column1] [column2] etc. if indeed the column names were delimited like that. Don't think so, those are meta, it's like asking if there is a way to tell from the compiled program what the comments in the code was that the programmer inserted when coding... The compiler very correctly discards it and no trace of it exists in the compiled program. I have made a few parsers for the SQLite schemata and also you can probably copy paste some code for it directly from the SQLite source, but may I ask why you would need that information? (Perhaps the problem can be solved another way) ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] pragma table_info return column delimiters?
OK, thanks. I am getting the information now from the create table statements and sofar that seems to work OK. Just wanted to make sure there wasn't a better way to handle this. RBS On Wed, Jan 3, 2018 at 11:08 AM, Richard Hippwrote: > On 1/3/18, Bart Smissaert wrote: > > Is there a way with pragma table_info or otherwise (other than parsing > the > > table create statement from SQLite_master) to get the column names > > including the column delimiters, eg double quotes or square brackets? So > I > > would get eg: [column1] [column2] etc. if indeed the column names were > > delimited like that. > > No. SQLite does not retain that information in its internal symbol > tables. You'll have to parse out the original CREATE TABLE statements > to figure that out. > -- > D. Richard Hipp > d...@sqlite.org > ___ > 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] pragma table_info return column delimiters?
On 2018/01/03 12:15 PM, Bart Smissaert wrote: Is there a way with pragma table_info or otherwise (other than parsing the table create statement from SQLite_master) to get the column names including the column delimiters, eg double quotes or square brackets? So I would get eg: [column1] [column2] etc. if indeed the column names were delimited like that. Don't think so, those are meta, it's like asking if there is a way to tell from the compiled program what the comments in the code was that the programmer inserted when coding... The compiler very correctly discards it and no trace of it exists in the compiled program. I have made a few parsers for the SQLite schemata and also you can probably copy paste some code for it directly from the SQLite source, but may I ask why you would need that information? (Perhaps the problem can be solved another way) (Accidentally sent this on another mail first, so if it comes through twice, my apologies...) ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] pragma table_info return column delimiters?
delimiters delimit, so they are not part of the context.. such information aobut delimiters is never saved... since they havce done their job delimiiting already. Why do you want this? On Wed, Jan 3, 2018 at 2:50 AM, Bart Smissaertwrote: > > What are column delimiters? > > create table [table1)([ID] integer, [text_field] text) > > I am talking about the square brackets here surrounding the field names. > Sorry, used the wrong word in saying delimiters. > > RBS > > On Wed, Jan 3, 2018 at 10:44 AM, Luuk wrote: > > > > > > > On 03-01-18 11:15, Bart Smissaert wrote: > > > Is there a way with pragma table_info or otherwise (other than parsing > > the > > > table create statement from SQLite_master) to get the column names > > > including the column delimiters, eg double quotes or square brackets? > So > > I > > > would get eg: [column1] [column2] etc. if indeed the column names were > > > delimited like that. > > > > > > RBS > > > > > What are column delimiters? > > > > |sqlite> select * from test; > > a, b, c > > 1, 2, drie > > 4, 5, zes > > sqlite> select a,b,c from test; > > a, b, c > > 1, 2, drie > > 4, 5, zes > > sqlite> select [a],[b],[c] from test; > > a, b, c > > 1, 2, drie > > 4, 5, zes > > sqlite> select "a","b","c" from test; > > a, b, c > > 1, 2, drie > > 4, 5, zes > > > > Of course, you shoul not use single quotes ;) > > sqlite> select 'a','b','c' from test; > > 'a', 'b', 'c' > > a, b, c > > a, b, c > > sqlite>| > > ___ > > 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 > ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] pragma table_info return column delimiters?
On 1/3/18, Bart Smissaertwrote: > Is there a way with pragma table_info or otherwise (other than parsing the > table create statement from SQLite_master) to get the column names > including the column delimiters, eg double quotes or square brackets? So I > would get eg: [column1] [column2] etc. if indeed the column names were > delimited like that. No. SQLite does not retain that information in its internal symbol tables. You'll have to parse out the original CREATE TABLE statements to figure that out. -- D. Richard Hipp d...@sqlite.org ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] pragma table_info return column delimiters?
> What are column delimiters? create table [table1)([ID] integer, [text_field] text) I am talking about the square brackets here surrounding the field names. Sorry, used the wrong word in saying delimiters. RBS On Wed, Jan 3, 2018 at 10:44 AM, Luukwrote: > > > On 03-01-18 11:15, Bart Smissaert wrote: > > Is there a way with pragma table_info or otherwise (other than parsing > the > > table create statement from SQLite_master) to get the column names > > including the column delimiters, eg double quotes or square brackets? So > I > > would get eg: [column1] [column2] etc. if indeed the column names were > > delimited like that. > > > > RBS > > > What are column delimiters? > > |sqlite> select * from test; > a, b, c > 1, 2, drie > 4, 5, zes > sqlite> select a,b,c from test; > a, b, c > 1, 2, drie > 4, 5, zes > sqlite> select [a],[b],[c] from test; > a, b, c > 1, 2, drie > 4, 5, zes > sqlite> select "a","b","c" from test; > a, b, c > 1, 2, drie > 4, 5, zes > > Of course, you shoul not use single quotes ;) > sqlite> select 'a','b','c' from test; > 'a', 'b', 'c' > a, b, c > a, b, c > sqlite>| > ___ > 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] pragma table_info return column delimiters?
On 03-01-18 11:15, Bart Smissaert wrote: > Is there a way with pragma table_info or otherwise (other than parsing the > table create statement from SQLite_master) to get the column names > including the column delimiters, eg double quotes or square brackets? So I > would get eg: [column1] [column2] etc. if indeed the column names were > delimited like that. > > RBS > What are column delimiters? |sqlite> select * from test; a, b, c 1, 2, drie 4, 5, zes sqlite> select a,b,c from test; a, b, c 1, 2, drie 4, 5, zes sqlite> select [a],[b],[c] from test; a, b, c 1, 2, drie 4, 5, zes sqlite> select "a","b","c" from test; a, b, c 1, 2, drie 4, 5, zes Of course, you shoul not use single quotes ;) sqlite> select 'a','b','c' from test; 'a', 'b', 'c' a, b, c a, b, c sqlite>| ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
[sqlite] pragma table_info return column delimiters?
Is there a way with pragma table_info or otherwise (other than parsing the table create statement from SQLite_master) to get the column names including the column delimiters, eg double quotes or square brackets? So I would get eg: [column1] [column2] etc. if indeed the column names were delimited like that. RBS ___ sqlite-users mailing list sqlite-users@mailinglists.sqlite.org http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users