Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

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

Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Paul
These are the queries:

CREATE TABLE foo(
    id        INTEGER,
    baz     INTEGER,
    PRIMARY KEY(id)
);

CREATE TABLE bar(
    foo       INTEGER,
    PRIMARY KEY(foo),
    FOREIGN KEY(foo) REFERENCES foo(id) ON DELETE CASCADE
);

EXPLAIN QUERY PLAN SELECT foo.id, baz FROM bar LEFT JOIN foo ON bar.foo = foo.id ORDER BY id LIMIT 10, 10;

selectid    order       from        detail                                                                                              
----------  ----------  ----------  -----------------------------------------------------------
0           0           0           SCAN TABLE bar                                                                                      
0           1           1           SEARCH TABLE foo USING INTEGER PRIMARY KEY (rowid=?)                                                
0           0           0           USE TEMP B-TREE FOR ORDER BY

'bar.foo = foo.id' gives a strong hint that primary key index of 'bar' can be used for 'ORDER BY id' ordering.
But it does not happen, hence the plan includes full scan of 'bar' and  TEMP B-TREE construction.


The reason behind ordering being 'ORDER BY id' instead of 'ORDER BY bar.foo'  is that bar pays a role of partial index.
Database was created just a year before partial indexes were released. Bar is not a single such table, there are more.
The query is being constructed dynamically and in the end  'ORDER BY id' is appended to ensure that  query is correct
no matter how many 'partial-index-tables'  the foo is LEFT JOIN-ed with.
 
 
_______________________________________________
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Hick Gunter
Maybe you are looking for

SELECT id,baz from foo where exists( select 1 from bar where foo = id) ...

which has the effect of easily extending to an arbitrary number of bar tables via additional exists subqueries that may be connected by logical operators

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Paul
Gesendet: Donnerstag, 17. November 2016 13:58
An: General Discussion of SQLite Database <[hidden email]>
Betreff: [sqlite] Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

These are the queries:

CREATE TABLE foo(
    id        INTEGER,
    baz     INTEGER,
    PRIMARY KEY(id)
);

CREATE TABLE bar(
    foo       INTEGER,
    PRIMARY KEY(foo),
    FOREIGN KEY(foo) REFERENCES foo(id) ON DELETE CASCADE );

EXPLAIN QUERY PLAN SELECT foo.id, baz FROM bar LEFT JOIN foo ON bar.foo = foo.id ORDER BY id LIMIT 10, 10;

selectid    order       from        detail
----------  ----------  ----------  -----------------------------------------------------------
0           0           0           SCAN TABLE bar
0           1           1           SEARCH TABLE foo USING INTEGER PRIMARY KEY (rowid=?)
0           0           0           USE TEMP B-TREE FOR ORDER BY

'bar.foo = foo.id' gives a strong hint that primary key index of 'bar' can be used for 'ORDER BY id' ordering.
But it does not happen, hence the plan includes full scan of 'bar' and  TEMP B-TREE construction.


The reason behind ordering being 'ORDER BY id' instead of 'ORDER BY bar.foo'  is that bar pays a role of partial index.
Database was created just a year before partial indexes were released. Bar is not a single such table, there are more.
The query is being constructed dynamically and in the end  'ORDER BY id' is appended to ensure that  query is correct no matter how many 'partial-index-tables'  the foo is LEFT JOIN-ed with.


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


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


_______________________________________________
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Paul
It's not a solution, because in your example, foo will be scanned until limit is reached.
This may take considerable amount of time, if results are parse.

Also, this solution is totally useless. It's a partial index on 'foo', meaning that I can know true or false having only rows of 'foo'.
In the other words: there is no need to do extra searches in 'partial-index-tables' like bar. The idea is that those tables are orders
of magnitude  smaller than foo, hence the LEFT JOIN to make it verbose and force query planner to scan 'bar' and co first.

 

> Maybe you are looking for
>
> SELECT id,baz from foo where exists( select 1 from bar where foo = id) ...
>
> which has the effect of easily extending to an arbitrary number of bar tables via additional exists subqueries that may be connected by logical operators
>
> -----Ursprüngliche Nachricht-----
> Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Paul
> Gesendet: Donnerstag, 17. November 2016 13:58
> An: General Discussion of SQLite Database
> Betreff: [sqlite] Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint
>
> These are the queries:
>
> CREATE TABLE foo(
>     id        INTEGER,
>     baz     INTEGER,
>     PRIMARY KEY(id)
> );
>
> CREATE TABLE bar(
>     foo       INTEGER,
>     PRIMARY KEY(foo),
>     FOREIGN KEY(foo) REFERENCES foo(id) ON DELETE CASCADE );
>
> EXPLAIN QUERY PLAN SELECT foo.id, baz FROM bar LEFT JOIN foo ON bar.foo = foo.id ORDER BY id LIMIT 10, 10;
>
> selectid    order       from        detail
> ----------  ----------  ----------  -----------------------------------------------------------
> 0           0           0           SCAN TABLE bar
> 0           1           1           SEARCH TABLE foo USING INTEGER PRIMARY KEY (rowid=?)
> 0           0           0           USE TEMP B-TREE FOR ORDER BY
>
> 'bar.foo = foo.id' gives a strong hint that primary key index of 'bar' can be used for 'ORDER BY id' ordering.
> But it does not happen, hence the plan includes full scan of 'bar' and  TEMP B-TREE construction.
>
>
> The reason behind ordering being 'ORDER BY id' instead of 'ORDER BY bar.foo'  is that bar pays a role of partial index.
> Database was created just a year before partial indexes were released. Bar is not a single such table, there are more.
> The query is being constructed dynamically and in the end  'ORDER BY id' is appended to ensure that  query is correct no matter how many 'partial-index-tables'  the foo is LEFT JOIN-ed with.
>
>
> _______________________________________________
> sqlite-users mailing list
> [hidden email]
> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>
>
> ___________________________________________
>  Gunter Hick
> Software Engineer
> Scientific Games International GmbH
> FN 157284 a, HG Wien
> Klitschgasse 2-4, A-1130 Vienna, Austria
> Tel: +43 1 80100 0
> E-Mail: [hidden email]
>
> This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.
>
>
> _______________________________________________
> 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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Marc L. Allen
In reply to this post by Hick Gunter
Maybe I'm missing something, but...

ORDER BY id

Is ordering by the ID the right-hand side of a LEFT join.  As such, it depends on how NULL factors into an ORDER BY.  If NULL comes first, it has to find enough records where the LEFT join fails.

Yeah.. I'm probably missing something.

-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of Hick Gunter
Sent: Thursday, November 17, 2016 8:53 AM
To: 'SQLite mailing list' <[hidden email]>
Subject: Re: [sqlite] Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Maybe you are looking for

SELECT id,baz from foo where exists( select 1 from bar where foo = id) ...

which has the effect of easily extending to an arbitrary number of bar tables via additional exists subqueries that may be connected by logical operators

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Paul
Gesendet: Donnerstag, 17. November 2016 13:58
An: General Discussion of SQLite Database <[hidden email]>
Betreff: [sqlite] Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

These are the queries:

CREATE TABLE foo(
    id        INTEGER,
    baz     INTEGER,
    PRIMARY KEY(id)
);

CREATE TABLE bar(
    foo       INTEGER,
    PRIMARY KEY(foo),
    FOREIGN KEY(foo) REFERENCES foo(id) ON DELETE CASCADE );

EXPLAIN QUERY PLAN SELECT foo.id, baz FROM bar LEFT JOIN foo ON bar.foo = foo.id ORDER BY id LIMIT 10, 10;

selectid    order       from        detail
----------  ----------  ----------  -----------------------------------------------------------
0           0           0           SCAN TABLE bar
0           1           1           SEARCH TABLE foo USING INTEGER PRIMARY KEY (rowid=?)
0           0           0           USE TEMP B-TREE FOR ORDER BY

'bar.foo = foo.id' gives a strong hint that primary key index of 'bar' can be used for 'ORDER BY id' ordering.
But it does not happen, hence the plan includes full scan of 'bar' and  TEMP B-TREE construction.


The reason behind ordering being 'ORDER BY id' instead of 'ORDER BY bar.foo'  is that bar pays a role of partial index.
Database was created just a year before partial indexes were released. Bar is not a single such table, there are more.
The query is being constructed dynamically and in the end  'ORDER BY id' is appended to ensure that  query is correct no matter how many 'partial-index-tables'  the foo is LEFT JOIN-ed with.


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


___________________________________________
 Gunter Hick
Software Engineer
Scientific Games International GmbH
FN 157284 a, HG Wien
Klitschgasse 2-4, A-1130 Vienna, Austria
Tel: +43 1 80100 0
E-Mail: [hidden email]

This communication (including any attachments) is intended for the use of the intended recipient(s) only and may contain information that is confidential, privileged or legally protected. Any unauthorized use or dissemination of this communication is strictly prohibited. If you have received this communication in error, please immediately notify the sender by return e-mail message and delete all copies of the original communication. Thank you for your cooperation.


_______________________________________________
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Richard Hipp-3
On 11/17/16, Marc L. Allen <[hidden email]> wrote:
> Maybe I'm missing something, but...
>
> ORDER BY id
>
> Is ordering by the ID the right-hand side of a LEFT join.  As such, it
> depends on how NULL factors into an ORDER BY.  If NULL comes first, it has
> to find enough records where the LEFT join fails.
>
> Yeah.. I'm probably missing something.

No, you are correct.  Since the ID column is on the RHS of a LEFT
JOIN, it cannot use an index for sorting.

The foreign key constraint could, in theory, be used by the query
planner to simplify the LEFT JOIN into an ordinary INNER JOIN.  But
the query planner in SQLite does not currently know that trick.

So, one solution is to remove the LEFT keyword from the query in the
application....
--
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Marc L. Allen
I'm not sure that's a valid trick, as bar.foo can be NULL, in which case the LEFT join still returns it, but an INNER join does not.  Unless sqlite infers a NOT NULL on bar.foo?

-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of Richard Hipp
Sent: Thursday, November 17, 2016 9:32 AM
To: SQLite mailing list <[hidden email]>
Subject: Re: [sqlite] Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

On 11/17/16, Marc L. Allen <[hidden email]> wrote:
> Maybe I'm missing something, but...
>
> ORDER BY id
>
> Is ordering by the ID the right-hand side of a LEFT join.  As such, it
> depends on how NULL factors into an ORDER BY.  If NULL comes first, it
> has to find enough records where the LEFT join fails.
>
> Yeah.. I'm probably missing something.

No, you are correct.  Since the ID column is on the RHS of a LEFT JOIN, it cannot use an index for sorting.

The foreign key constraint could, in theory, be used by the query planner to simplify the LEFT JOIN into an ordinary INNER JOIN.  But the query planner in SQLite does not currently know that trick.

So, one solution is to remove the LEFT keyword from the query in the application....
--
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Paul
In reply to this post by Richard Hipp-3
 

> On 11/17/16, Marc L. Allen  wrote:
> > Maybe I'm missing something, but...
> >
> > ORDER BY id
> >
> > Is ordering by the ID the right-hand side of a LEFT join.  As such, it
> > depends on how NULL factors into an ORDER BY.  If NULL comes first, it has
> > to find enough records where the LEFT join fails.
> >
> > Yeah.. I'm probably missing something.
>
> No, you are correct.  Since the ID column is on the RHS of a LEFT
> JOIN, it cannot use an index for sorting.

Now I see... Thanks for making it clear.

>
> The foreign key constraint could, in theory, be used by the query
> planner to simplify the LEFT JOIN into an ordinary INNER JOIN.  But
> the query planner in SQLite does not currently know that trick.
>
> So, one solution is to remove the LEFT keyword from the query in the
> application....

Replacing JOIN does not help either:

sqlite> EXPLAIN QUERY PLAN SELECT foo.id FROM bar JOIN foo ON bar.foo = foo.id ORDER BY id DESC LIMIT 0, 40;
selectid    order       from        detail                                                                                              
----------  ----------  ----------  ----------------------------------------------------------------------------------------------------
0           0           1           SCAN TABLE foo                                                                                      
0           1           0           SEARCH TABLE bar USING INTEGER PRIMARY KEY (rowid=?)

My guess is it's because there are no sqlite_stat* tables and SQLite doesn't know that bar scan is more efficient.
That's why there was a LEFT JOIN in the first place, but as it seems, it wasn't that good idea.


> --
> 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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Richard Hipp-3
In reply to this post by Marc L. Allen
On 11/17/16, Marc L. Allen <[hidden email]> wrote:
> I'm not sure that's a valid trick, as bar.foo can be NULL, in which case the
> LEFT join still returns it, but an INNER join does not.  Unless sqlite
> infers a NOT NULL on bar.foo?

The bar.foo column is an INTEGER PRIMARY KEY, which can never be NULL.

Standard SQL requires an implied NOT NULL on all PRIMARY KEY columns.
But due to a coding error, early versions of SQLite did not enforce
that, and so we have taken care not to enforce it on all subsequent
versions of SQLite to preserve backwards compatibility.

WITHOUT ROWID tables were added later, and so NOT NULL is properly
enforced on all PRIMARY KEY columns in WITHOUT ROWID tables.

>
> -----Original Message-----
> From: sqlite-users [mailto:[hidden email]] On
> Behalf Of Richard Hipp
> Sent: Thursday, November 17, 2016 9:32 AM
> To: SQLite mailing list <[hidden email]>
> Subject: Re: [sqlite] Query Planner fails to recognise efficient strategy
> when '=' condition gives a strong hint
>
> On 11/17/16, Marc L. Allen <[hidden email]> wrote:
>> Maybe I'm missing something, but...
>>
>> ORDER BY id
>>
>> Is ordering by the ID the right-hand side of a LEFT join.  As such, it
>> depends on how NULL factors into an ORDER BY.  If NULL comes first, it
>> has to find enough records where the LEFT join fails.
>>
>> Yeah.. I'm probably missing something.
>
> No, you are correct.  Since the ID column is on the RHS of a LEFT JOIN, it
> cannot use an index for sorting.
>
> The foreign key constraint could, in theory, be used by the query planner to
> simplify the LEFT JOIN into an ordinary INNER JOIN.  But the query planner
> in SQLite does not currently know that trick.
>
> So, one solution is to remove the LEFT keyword from the query in the
> application....
> --
> 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
>


--
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Richard Hipp-3
In reply to this post by Paul
On 11/17/16, Paul <[hidden email]> wrote:
> That's why there was a LEFT JOIN in the first place, but as it seems, it
> wasn't that good idea.

Try using CROSS JOIN instead of just JOIN or LEFT JOIN.  The query
planner in SQLite will not reorder a CROSS JOIN.

--
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Richard Hipp-3
On 11/17/16, Richard Hipp <[hidden email]> wrote:
> On 11/17/16, Paul <[hidden email]> wrote:
>> That's why there was a LEFT JOIN in the first place, but as it seems, it
>> wasn't that good idea.
>
> Try using CROSS JOIN instead of just JOIN or LEFT JOIN.  The query
> planner in SQLite will not reorder a CROSS JOIN.

But, as it turns out, if you use CROSS JOIN it goes back to sorting.  Bummer.

Ok, a new optimization opportunity.

It gets the correct answer, though, so this is not considered a bug.

--
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Paul
 
> On 11/17/16, Richard Hipp  wrote:
> > On 11/17/16, Paul  wrote:
> >> That's why there was a LEFT JOIN in the first place, but as it seems, it
> >> wasn't that good idea.
> >
> > Try using CROSS JOIN instead of just JOIN or LEFT JOIN.  The query
> > planner in SQLite will not reorder a CROSS JOIN.
>
> But, as it turns out, if you use CROSS JOIN it goes back to sorting.  Bummer.

Yes... unfortunately.

>
> Ok, a new optimization opportunity.

So, in the upcoming releases, some of these queries may get optimised?
The ones with the LEFT or wit the CROSS JOIN?

>
> It gets the correct answer, though, so this is not considered a bug.
>
> --
> 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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Richard Hipp-3
On 11/17/16, Paul <[hidden email]> wrote:

>
>> On 11/17/16, Richard Hipp  wrote:
>> > On 11/17/16, Paul  wrote:
>> >> That's why there was a LEFT JOIN in the first place, but as it seems,
>> >> it
>> >> wasn't that good idea.
>> >
>> > Try using CROSS JOIN instead of just JOIN or LEFT JOIN.  The query
>> > planner in SQLite will not reorder a CROSS JOIN.
>>
>> But, as it turns out, if you use CROSS JOIN it goes back to sorting.
>> Bummer.
>
> Yes... unfortunately.
>
>>
>> Ok, a new optimization opportunity.
>
> So, in the upcoming releases, some of these queries may get optimised?
> The ones with the LEFT or wit the CROSS JOIN?
>

CROSS JOIN.  I don't think the LEFT JOIN case works, but I will confirm that.


--
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Marc L. Allen
In reply to this post by Richard Hipp-3
<sigh>  Yeah.. I know that.  Missed the PRIMARY KEY. :(

Back to lurking. ;)

-----Original Message-----
From: sqlite-users [mailto:[hidden email]] On Behalf Of Richard Hipp
Sent: Thursday, November 17, 2016 9:54 AM
To: SQLite mailing list <[hidden email]>
Subject: Re: [sqlite] Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

On 11/17/16, Marc L. Allen <[hidden email]> wrote:
> I'm not sure that's a valid trick, as bar.foo can be NULL, in which
> case the LEFT join still returns it, but an INNER join does not.  
> Unless sqlite infers a NOT NULL on bar.foo?

The bar.foo column is an INTEGER PRIMARY KEY, which can never be NULL.

Standard SQL requires an implied NOT NULL on all PRIMARY KEY columns.
But due to a coding error, early versions of SQLite did not enforce that, and so we have taken care not to enforce it on all subsequent versions of SQLite to preserve backwards compatibility.

WITHOUT ROWID tables were added later, and so NOT NULL is properly enforced on all PRIMARY KEY columns in WITHOUT ROWID tables.

>
> -----Original Message-----
> From: sqlite-users
> [mailto:[hidden email]] On Behalf Of
> Richard Hipp
> Sent: Thursday, November 17, 2016 9:32 AM
> To: SQLite mailing list <[hidden email]>
> Subject: Re: [sqlite] Query Planner fails to recognise efficient
> strategy when '=' condition gives a strong hint
>
> On 11/17/16, Marc L. Allen <[hidden email]> wrote:
>> Maybe I'm missing something, but...
>>
>> ORDER BY id
>>
>> Is ordering by the ID the right-hand side of a LEFT join.  As such,
>> it depends on how NULL factors into an ORDER BY.  If NULL comes
>> first, it has to find enough records where the LEFT join fails.
>>
>> Yeah.. I'm probably missing something.
>
> No, you are correct.  Since the ID column is on the RHS of a LEFT
> JOIN, it cannot use an index for sorting.
>
> The foreign key constraint could, in theory, be used by the query
> planner to simplify the LEFT JOIN into an ordinary INNER JOIN.  But
> the query planner in SQLite does not currently know that trick.
>
> So, one solution is to remove the LEFT keyword from the query in the
> application....
> --
> 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
>


--
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Paul
In reply to this post by Richard Hipp-3


> On 11/17/16, Paul  wrote:
> >
> >> On 11/17/16, Richard Hipp  wrote:
> >> > On 11/17/16, Paul  wrote:
> >> >> That's why there was a LEFT JOIN in the first place, but as it seems,
> >> >> it
> >> >> wasn't that good idea.
> >> >
> >> > Try using CROSS JOIN instead of just JOIN or LEFT JOIN.  The query
> >> > planner in SQLite will not reorder a CROSS JOIN.
> >>
> >> But, as it turns out, if you use CROSS JOIN it goes back to sorting.
> >> Bummer.
> >
> > Yes... unfortunately.
> >
> >>
> >> Ok, a new optimization opportunity.
> >
> > So, in the upcoming releases, some of these queries may get optimised?
> > The ones with the LEFT or wit the CROSS JOIN?
> >
>
> CROSS JOIN.  I don't think the LEFT JOIN case works, but I will confirm that.
>

BTW, bar has a FK from foo. When FKs are on I believe SQLite can assume that constraints are not violated.
Hence the right part of the LEFT JOIN can never be NULL, specifically the id.
 
 
_______________________________________________
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Nico Williams
In reply to this post by Richard Hipp-3
On Thu, Nov 17, 2016 at 09:54:01AM -0500, Richard Hipp wrote:
> Standard SQL requires an implied NOT NULL on all PRIMARY KEY columns.
> But due to a coding error, early versions of SQLite did not enforce
> that, and so we have taken care not to enforce it on all subsequent
> versions of SQLite to preserve backwards compatibility.
>
> WITHOUT ROWID tables were added later, and so NOT NULL is properly
> enforced on all PRIMARY KEY columns in WITHOUT ROWID tables.

I've noticed this, and I'm quite happy about it.

A [persistent] pragma to make SQLite3 adhere more strictly to the
standard would be nice.  You could slowly add more strictness.  Anyone
who turns on strictness would be getting what they asked for as
subsequent add more.

Nico
--
_______________________________________________
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Nico Williams
In reply to this post by Paul
On Thu, Nov 17, 2016 at 04:48:20PM +0200, Paul wrote:

> Replacing JOIN does not help either:
>
> sqlite> EXPLAIN QUERY PLAN SELECT foo.id FROM bar JOIN foo ON bar.foo = foo.id ORDER BY id DESC LIMIT 0, 40;
> selectid    order       from        detail                                                                                              
> ----------  ----------  ----------  ----------------------------------------------------------------------------------------------------
> 0           0           1           SCAN TABLE foo                                                                                      
> 0           1           0           SEARCH TABLE bar USING INTEGER PRIMARY KEY (rowid=?)
>
> My guess is it's because there are no sqlite_stat* tables and SQLite
> doesn't know that bar scan is more efficient.  That's why there was a
> LEFT JOIN in the first place, but as it seems, it wasn't that good
> idea.

If you want the ORDER BY to not sort (either as results are generated or
after, but either way before the application sees a single result) then
you kinda need to scan foo first.  Is there any other way?  I don't
think so, but correct me!

Nico
--
_______________________________________________
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

dbilid
Why don't you just explicitly sort by bar.foo?


sqlite> EXPLAIN QUERY PLAN SELECT bar.foo as id, foo.baz FROM bar CROSS JOIN foo ON bar.foo = foo.id ORDER BY bar.foo LIMIT 10, 10;
0|0|0|SCAN TABLE bar
0|1|1|SEARCH TABLE foo USING INTEGER PRIMARY KEY (rowid=?)
sqlite>


Dimitris


________________________________
From: sqlite-users <[hidden email]> on behalf of Nico Williams <[hidden email]>
Sent: Thursday, November 17, 2016 4:32 PM
To: SQLite mailing list
Subject: Re: [sqlite] Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

On Thu, Nov 17, 2016 at 04:48:20PM +0200, Paul wrote:

> Replacing JOIN does not help either:
>
> sqlite> EXPLAIN QUERY PLAN SELECT foo.id FROM bar JOIN foo ON bar.foo = foo.id ORDER BY id DESC LIMIT 0, 40;
> selectid    order       from        detail
> ----------  ----------  ----------  ----------------------------------------------------------------------------------------------------
> 0           0           1           SCAN TABLE foo
> 0           1           0           SEARCH TABLE bar USING INTEGER PRIMARY KEY (rowid=?)
>
> My guess is it's because there are no sqlite_stat* tables and SQLite
> doesn't know that bar scan is more efficient.  That's why there was a
> LEFT JOIN in the first place, but as it seems, it wasn't that good
> idea.

If you want the ORDER BY to not sort (either as results are generated or
after, but either way before the application sees a single result) then
you kinda need to scan foo first.  Is there any other way?  I don't
think so, but correct me!

Nico
--
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
sqlite-users Info Page<http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users>
mailinglists.sqlite.org
To see the collection of prior postings to the list, visit the sqlite-users Archives. (The current archive is only available to the list ...


_______________________________________________
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: Query Planner fails to recognise efficient strategy when '=' condition gives a strong hint

Paul
> Why don't you just explicitly sort by bar.foo?
>
>
> sqlite> EXPLAIN QUERY PLAN SELECT bar.foo as id, foo.baz FROM bar CROSS JOIN foo ON bar.foo = foo.id ORDER BY bar.foo LIMIT 10, 10;
> 0|0|0|SCAN TABLE bar
> 0|1|1|SEARCH TABLE foo USING INTEGER PRIMARY KEY (rowid=?)
> sqlite>

I have explained that in the original message. 'foo' is a master table. There are more tables like 'baz' that play role of a partial index.
Query is built dynamically from some collection of data. As a result, various combinations of 'foo', 'baz' and co may be in the  resulting query.
The only certain thing is that 'foo' is always in the query, hence the 'id'.
 
 
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users