Optimizer limitation with partial indexes

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Optimizer limitation with partial indexes

Jens Alfke-2
I'm running into a problem with partial indexes; apparently the query optimizer isn't smart enough.

I currently have indexes of the form
        CREATE INDEX Index1 ON Table (expr1)
        CREATE INDEX Index2 ON Table (expr2)
where expr1 and expr2 are expressions involving table columns.

The problematic queries are of the form
        SELECT * FROM Table WHERE (expr1 > val1 OR expr2 > val2) AND expr3
Such a query correctly uses the above indexes — the EXPLAIN command shows it's using a multi-index OR combining two 'search table using index' loops.

If, however, I try to make the indexes smaller by changing them to
        CREATE INDEX Index1 ON Table (expr1) WHERE expr3
        CREATE INDEX Index2 ON Table (expr2) WHERE expr3
the query stops using the indexes effectively. It's reduced to doing 'scan table using index', i.e. O(n).

It looks like what happens is that the optimizer doesn't associate the "AND expr3" clause with the "expr1" and "expr2" comparisons. In other words, it doesn't realize that (A OR B) AND C is equivalent to (A AND C) OR (B AND C).

If this were a hand-written SELECT statement it would be easy to work around this, but it's not. It's the output of a query translator that generates SQL, and it can generate arbitrary queries with arbitrary combinations of operators.

I know the SQLite optimizer isn't a Mathematica-grade symbolic logic analyzer! But I'm wondering if in this case there's a way around this limitation?

—Jens
_______________________________________________
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: Optimizer limitation with partial indexes

wmertens
Does moving the expr3 work?

SELECT * FROM Table WHERE ((expr1 > val1 AND AND expr3) OR (expr2 > val2
AND expr3))

Wout.


On Wed, Feb 12, 2020 at 12:09 AM Jens Alfke <[hidden email]> wrote:

> I'm running into a problem with partial indexes; apparently the query
> optimizer isn't smart enough.
>
> I currently have indexes of the form
>         CREATE INDEX Index1 ON Table (expr1)
>         CREATE INDEX Index2 ON Table (expr2)
> where expr1 and expr2 are expressions involving table columns.
>
> The problematic queries are of the form
>         SELECT * FROM Table WHERE (expr1 > val1 OR expr2 > val2) AND expr3
> Such a query correctly uses the above indexes — the EXPLAIN command shows
> it's using a multi-index OR combining two 'search table using index' loops.
>
> If, however, I try to make the indexes smaller by changing them to
>         CREATE INDEX Index1 ON Table (expr1) WHERE expr3
>         CREATE INDEX Index2 ON Table (expr2) WHERE expr3
> the query stops using the indexes effectively. It's reduced to doing 'scan
> table using index', i.e. O(n).
>
> It looks like what happens is that the optimizer doesn't associate the
> "AND expr3" clause with the "expr1" and "expr2" comparisons. In other
> words, it doesn't realize that (A OR B) AND C is equivalent to (A AND C) OR
> (B AND C).
>
> If this were a hand-written SELECT statement it would be easy to work
> around this, but it's not. It's the output of a query translator that
> generates SQL, and it can generate arbitrary queries with arbitrary
> combinations of operators.
>
> I know the SQLite optimizer isn't a Mathematica-grade symbolic logic
> analyzer! But I'm wondering if in this case there's a way around this
> limitation?
>
> —Jens
> _______________________________________________
> 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] Optimizer limitation with partial indexes

Hick Gunter
In reply to this post by Jens Alfke-2
This is documented here https://sqlite.org/partialindex.html and here https://sqlite.org/queryplanner.html

Specifically, SQLIte does not prove theorems in first-order logic.

To have a chance of using the partial indices, you would need to have your query translator formulate (expr1>val1 AND expr 3) OR (expr2>val2 AND expr3)

-----Ursprüngliche Nachricht-----
Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Jens Alfke
Gesendet: Mittwoch, 12. Februar 2020 00:09
An: SQLite mailing list <[hidden email]>
Betreff: [EXTERNAL] [sqlite] Optimizer limitation with partial indexes

I'm running into a problem with partial indexes; apparently the query optimizer isn't smart enough.

I currently have indexes of the form
        CREATE INDEX Index1 ON Table (expr1)
        CREATE INDEX Index2 ON Table (expr2)
where expr1 and expr2 are expressions involving table columns.

The problematic queries are of the form
        SELECT * FROM Table WHERE (expr1 > val1 OR expr2 > val2) AND expr3 Such a query correctly uses the above indexes — the EXPLAIN command shows it's using a multi-index OR combining two 'search table using index' loops.

If, however, I try to make the indexes smaller by changing them to
        CREATE INDEX Index1 ON Table (expr1) WHERE expr3
        CREATE INDEX Index2 ON Table (expr2) WHERE expr3 the query stops using the indexes effectively. It's reduced to doing 'scan table using index', i.e. O(n).

It looks like what happens is that the optimizer doesn't associate the "AND expr3" clause with the "expr1" and "expr2" comparisons. In other words, it doesn't realize that (A OR B) AND C is equivalent to (A AND C) OR (B AND C).

If this were a hand-written SELECT statement it would be easy to work around this, but it's not. It's the output of a query translator that generates SQL, and it can generate arbitrary queries with arbitrary combinations of operators.

I know the SQLite optimizer isn't a Mathematica-grade symbolic logic analyzer! But I'm wondering if in this case there's a way around this limitation?

—Jens
_______________________________________________
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] Optimizer limitation with partial indexes

Jens Alfke-2


> On Feb 12, 2020, at 5:30 AM, Hick Gunter <[hidden email]> wrote:
>
> This is documented here https://sqlite.org/partialindex.html <https://sqlite.org/partialindex.html> and here https://sqlite.org/queryplanner.html <https://sqlite.org/queryplanner.html>
>
> Specifically, SQLIte does not prove theorems in first-order logic.

Thanks — I hadn't seen the section "Queries Using Partial Indexes" before, and it gives more detail about how the matching is done. However, it seems that my query does match one of the rules:

        "If W [the query's WHERE clause] is AND-connected terms
         and X [the index's WHERE clause]  is OR-connected terms
         and if any term of W appears as a term of X,
         then the partial index is usable."

Here W = (expr1 > val1 OR expr2 > val2) AND expr3
 and X = expr3, which is a degenerate case of one OR-connected term.

So I'm not sure why the indexes aren't useable, unless there are limitations of the actual rule that aren't described in that English text.

—Jens
_______________________________________________
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] Optimizer limitation with partial indexes

Hick Gunter
>Von: sqlite-users [mailto:[hidden email]] Im Auftrag von Jens Alfke
>> On Feb 12, 2020, at 5:30 AM, Hick Gunter <[hidden email]> wrote:
>>
>> This is documented here https://sqlite.org/partialindex.html
>> <https://sqlite.org/partialindex.html> and here
>> https://sqlite.org/queryplanner.html
>> <https://sqlite.org/queryplanner.html>
>>
>> Specifically, SQLIte does not prove theorems in first-order logic.
>
>Thanks — I hadn't seen the section "Queries Using Partial Indexes" before, and it gives more detail about how the matching is done. >However, it seems that my query does match one of the rules:
>
>       "If W [the query's WHERE clause] is AND-connected terms
>        and X [the index's WHERE clause]  is OR-connected terms
>        and if any term of W appears as a term of X,
>        then the partial index is usable."
>
>Here W = (expr1 > val1 OR expr2 > val2) AND expr3  and X = expr3, which is a degenerate case of one OR-connected term.
>
>So I'm not sure why the indexes aren't useable, unless there are limitations of the actual rule that aren't described in that English text.

My guess ist hat SQLite is looking at the "expr1>val1" and "expr2>val2" terms respectively, which don't have a reference to expr3, and thus concludes that the indices are not usable.

However, "expr1>val1 AND expr3" clearly matches the rule and thus should use the index.


___________________________________________
 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