On Mon, 23 Mar 2015 06:43:39 +0000 Hick Gunter <hick at scigames.at> wrote:
> SQLite creates an ephemeral table for the IN list,giving O(log n) > performance for lookups. Thank you for pointing that out, Hick. Good to know! Is there some lower bound on either the size of the IN list or the number of rows in the table being queried? I ask because a linear scan of ~10 elements in a IN list won't benefit much if at all from a binary search. Similarly, if the table had only, say, 6 rows and the IN list was 100 long, we could imagine it would be faster to scan the table for each list element -- O(nm), worst case -- than to sort the IN list first and scan the table, O(m n log(n)). --jkl > >-----Urspr?ngliche Nachricht----- > >Von: James K. Lowden [mailto:jklowden at schemamania.org] > >Gesendet: Samstag, 21. M?rz 2015 20:43 > >An: sqlite-users at mailinglists.sqlite.org > >Betreff: Re: [sqlite] Query times vary between 0.2 s and 30 s for > >very > > > >On Sat, 21 Mar 2015 19:01:16 +0100 > >"Mario M. Westphal" <mw at mwlabs.de> wrote: > > > >> For now I have increased the threshold for IN clauses (instead of > >> TEMP tables) and use WHERE IN (SELECT ? from TEMP) instead of a > >> JOIN. > > > >... > >There is also the question of linear vs binary searches. When you > >supply a list of constants to IN, most if not all DBMSs search the > >list sequentially. When IN (or EXISTS) is supplied from an indexed > >column, the search is often binary. For a small number of elements, > >there's no >distinction. For 1000 elements, it's 2 orders of > >magnitude: 1000 hops versus 10. > > > >--jkl > > > ___________________________________________ > 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: hick at scigames.at > > 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 > sqlite-users at mailinglists.sqlite.org > http://mailinglists.sqlite.org/cgi-bin/mailman/listinfo/sqlite-users
