Re: 3.18.0 SELECT..WHERE x & ? != 0; doesn't use an index

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: 3.18.0 SELECT..WHERE x & ? != 0; doesn't use an index

Keith Medcalf
On Friday, 14 July, 2017 18:20, Marc L. Allen <[hidden email]> said:

> I don't know... since each match would then require a lookup in the main
> table to pull all the fields. If X was a covering index for the query, I
> would agree.

So, if you did a table scan, you would have to scan all the rows in the table and unpack at least 24 columns of integers to be able to execute the where condition, and if there is a match, unpack the remaining two columns.  

Contrast this with scanning an index containing ONLY the integer required (so 24 times less data to unpack) before executing the where condition which if and only if the condition is matched requires finding the table row and unpacking 26 columns of values.

There is obviously a point at which the % of returned vs scanned rows (and total rows) makes one more efficient than the other.

Of course,  one could always force the index scan method:

select * from x indexed by xy where expression(y);

if you know this is going to be more efficient.

> > On Jul 14, 2017, at 7:54 PM, Keith Medcalf <[hidden email]> wrote:
> >
> >
> > Not necessarily.  Your table may be defined as:
> >
> > create table x(a int, b int, c int, d int, ... y int, z int);
> > create index x_y on x (y);
> >
> > in that case a select * from x where expression(y)
> >
> > that scans the index (even without any skip-scan optimization) would be
> far more efficient than scanning the table, assuming that the where
> condition does not match all rows.
> >
> > --
> > ˙uʍop-ǝpısdn sı ɹoʇıuoɯ ɹnoʎ 'sıɥʇ pɐǝɹ uɐɔ noʎ ɟı
> >
> >> -----Original Message-----
> >> From: sqlite-users [mailto:sqlite-users-
> [hidden email]]
> >> On Behalf Of Marc L. Allen
> >> Sent: Friday, 14 July, 2017 14:50
> >> To: SQLite mailing list
> >> Subject: Re: [sqlite] 3.18.0 SELECT..WHERE x & ? != 0; doesn't use an
> >> index
> >>
> >> Generally, but not always, WHERE elements using a column in an
> expression
> >> are unsuitable to using an index.
> >>
> >> For instance:
> >>
> >> WHERE y + 2 = 4 generally can't use an index, whereas WHERE y = 2 can.
> >>
> >> That's not to say a smart optimizer won't convert the former to the
> >> latter.
> >>
> >> But, what's the equivalent of y & 2 != 0?
> >>
> >> That converts to y IN (0, 2, 4, ... MAX(y) & 2)
> >>
> >> Ignoring the MAX(y), that's just a series of multiple indexed lookups
> and
> >> a table scan is almost certainly more efficient.
> >>
> >> Marc
> >>
> >>> On Jul 14, 2017, at 1:55 PM, Howard Kapustein
> >> <[hidden email]> wrote:
> >>>
> >>> sqlite> create table blah(id integer primary key not null, x text, y
> >> integer not null);
> >>> sqlite> create index blahindex on blah (y);
> >>> sqlite> explain query plan select * from blah where y & ? != 0;
> >>> 0|0|0|SCAN TABLE blah
> >>>
> >>> But other numeric expressions do e.g.
> >>>
> >>> sqlite> explain query plan select * from blah where y = ?;
> >>> 0|0|0|SEARCH TABLE blah USING INDEX blahindex (y=?)
> >>> sqlite> explain query plan select * from blah where y > ?;
> >>> 0|0|0|SEARCH TABLE blah USING INDEX blahindex (y>?)
> >>>
> >>> Is this a known issue?
> >>> _______________________________________________
> >>> sqlite-users mailing list
> >>> [hidden email]
> >>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
> >>
> >>
> >> Confidentiality notice: This e-mail is intended solely for use of the
> >> individual or entity to which it is addressed and may contain
> information
> >> that is proprietary, privileged, company confidential and/or exempt
> from
> >> disclosure under applicable law. If the reader is not the intended
> >> recipient or agent responsible for delivering the message to the
> intended
> >> recipient, you are hereby notified that any dissemination, distribution
> or
> >> copying of this communication is strictly prohibited. If you have
> received
> >> this communication in error, please notify the sender by reply e-mail
> or
> >> collect telephone call and delete or destroy all copies of this e-mail
> >> message, any physical copies made of this e-mail message and/or any
> file
> >> attachment(s).
> >> _______________________________________________
> >> 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
>
>
>
> Confidentiality notice: This e-mail is intended solely for use of the
> individual or entity to which it is addressed and may contain information
> that is proprietary, privileged, company confidential and/or exempt from
> disclosure under applicable law. If the reader is not the intended
> recipient or agent responsible for delivering the message to the intended
> recipient, you are hereby notified that any dissemination, distribution or
> copying of this communication is strictly prohibited. If you have received
> this communication in error, please notify the sender by reply e-mail or
> collect telephone call and delete or destroy all copies of this e-mail
> message, any physical copies made of this e-mail message and/or any file
> attachment(s).
> _______________________________________________
> 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
|  
Report Content as Inappropriate

Re: 3.18.0 SELECT..WHERE x & ? != 0; doesn't use an index

Marc L. Allen
Yes... that's true. Since I don't know enough about  how SQLite looks up a single record referenced by an index, I'm not in a position to discuss further.

Naturally, there is always a trade off and, given the right percentage of matches, or position of matches, one way will be more efficient that the other.

I didn't realize (or had forgotten) that integers could be stored with variable length. Naturally, that has additional impact.

> On Jul 14, 2017, at 9:37 PM, Keith Medcalf <[hidden email]> wrote:
>
> On Friday, 14 July, 2017 18:20, Marc L. Allen <[hidden email]> said:
>
>> I don't know... since each match would then require a lookup in the main
>> table to pull all the fields. If X was a covering index for the query, I
>> would agree.
>
> So, if you did a table scan, you would have to scan all the rows in the table and unpack at least 24 columns of integers to be able to execute the where condition, and if there is a match, unpack the remaining two columns.  
>
> Contrast this with scanning an index containing ONLY the integer required (so 24 times less data to unpack) before executing the where condition which if and only if the condition is matched requires finding the table row and unpacking 26 columns of values.
>
> There is obviously a point at which the % of returned vs scanned rows (and total rows) makes one more efficient than the other.
>
> Of course,  one could always force the index scan method:
>
> select * from x indexed by xy where expression(y);
>
> if you know this is going to be more efficient.
>
>>> On Jul 14, 2017, at 7:54 PM, Keith Medcalf <[hidden email]> wrote:
>>>
>>>
>>> Not necessarily.  Your table may be defined as:
>>>
>>> create table x(a int, b int, c int, d int, ... y int, z int);
>>> create index x_y on x (y);
>>>
>>> in that case a select * from x where expression(y)
>>>
>>> that scans the index (even without any skip-scan optimization) would be
>> far more efficient than scanning the table, assuming that the where
>> condition does not match all rows.
>>>
>>> --
>>> ˙uʍop-ǝpısdn sı ɹoʇıuoɯ ɹnoʎ 'sıɥʇ pɐǝɹ uɐɔ noʎ ɟı
>>>
>>>> -----Original Message-----
>>>> From: sqlite-users [mailto:sqlite-users-
>> [hidden email]]
>>>> On Behalf Of Marc L. Allen
>>>> Sent: Friday, 14 July, 2017 14:50
>>>> To: SQLite mailing list
>>>> Subject: Re: [sqlite] 3.18.0 SELECT..WHERE x & ? != 0; doesn't use an
>>>> index
>>>>
>>>> Generally, but not always, WHERE elements using a column in an
>> expression
>>>> are unsuitable to using an index.
>>>>
>>>> For instance:
>>>>
>>>> WHERE y + 2 = 4 generally can't use an index, whereas WHERE y = 2 can.
>>>>
>>>> That's not to say a smart optimizer won't convert the former to the
>>>> latter.
>>>>
>>>> But, what's the equivalent of y & 2 != 0?
>>>>
>>>> That converts to y IN (0, 2, 4, ... MAX(y) & 2)
>>>>
>>>> Ignoring the MAX(y), that's just a series of multiple indexed lookups
>> and
>>>> a table scan is almost certainly more efficient.
>>>>
>>>> Marc
>>>>
>>>>> On Jul 14, 2017, at 1:55 PM, Howard Kapustein
>>>> <[hidden email]> wrote:
>>>>>
>>>>> sqlite> create table blah(id integer primary key not null, x text, y
>>>> integer not null);
>>>>> sqlite> create index blahindex on blah (y);
>>>>> sqlite> explain query plan select * from blah where y & ? != 0;
>>>>> 0|0|0|SCAN TABLE blah
>>>>>
>>>>> But other numeric expressions do e.g.
>>>>>
>>>>> sqlite> explain query plan select * from blah where y = ?;
>>>>> 0|0|0|SEARCH TABLE blah USING INDEX blahindex (y=?)
>>>>> sqlite> explain query plan select * from blah where y > ?;
>>>>> 0|0|0|SEARCH TABLE blah USING INDEX blahindex (y>?)
>>>>>
>>>>> Is this a known issue?
>>>>> _______________________________________________
>>>>> sqlite-users mailing list
>>>>> [hidden email]
>>>>> http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
>>>>
>>>>
>>>> Confidentiality notice: This e-mail is intended solely for use of the
>>>> individual or entity to which it is addressed and may contain
>> information
>>>> that is proprietary, privileged, company confidential and/or exempt
>> from
>>>> disclosure under applicable law. If the reader is not the intended
>>>> recipient or agent responsible for delivering the message to the
>> intended
>>>> recipient, you are hereby notified that any dissemination, distribution
>> or
>>>> copying of this communication is strictly prohibited. If you have
>> received
>>>> this communication in error, please notify the sender by reply e-mail
>> or
>>>> collect telephone call and delete or destroy all copies of this e-mail
>>>> message, any physical copies made of this e-mail message and/or any
>> file
>>>> attachment(s).
>>>> _______________________________________________
>>>> 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
>>
>>
>>
>> Confidentiality notice: This e-mail is intended solely for use of the
>> individual or entity to which it is addressed and may contain information
>> that is proprietary, privileged, company confidential and/or exempt from
>> disclosure under applicable law. If the reader is not the intended
>> recipient or agent responsible for delivering the message to the intended
>> recipient, you are hereby notified that any dissemination, distribution or
>> copying of this communication is strictly prohibited. If you have received
>> this communication in error, please notify the sender by reply e-mail or
>> collect telephone call and delete or destroy all copies of this e-mail
>> message, any physical copies made of this e-mail message and/or any file
>> attachment(s).
>> _______________________________________________
>> 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



Confidentiality notice: This e-mail is intended solely for use of the individual or entity to which it is addressed and may contain information that is proprietary, privileged, company confidential and/or exempt from disclosure under applicable law. If the reader is not the intended recipient or agent responsible for delivering the message to the intended recipient, you are hereby notified that any dissemination, distribution or copying of this communication is strictly prohibited. If you have received this communication in error, please notify the sender by reply e-mail or collect telephone call and delete or destroy all copies of this e-mail message, any physical copies made of this e-mail message and/or any file attachment(s).
_______________________________________________
sqlite-users mailing list
[hidden email]
http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
Loading...