9 ms·

These blog posts have been great. I'd love to see a deep dive on the query planner at some point. I've done lots of benchmarking SQLite while writing ducks [1]

These blog posts have been great. I'd love to see a deep dive on the query planner at some point. I've done lots of benchmarking SQLite while writing ducks [1], and found some interesting stuff. It seems like SQLite will only use one index, even in cases where two indexes would better suit the query. Or, in cases where the query is fetching most of the table, it will use an index even though a full scan would actually be much faster. Don't get me wrong, SQLite is awesome, and it's quite possible to work around these behaviors. Just interested in why they're not built in. [1] https://github.com/manimino/ducks https://github.com/manimino/ducks

samatman 4y ago
Have you brought any of that up in the SQLite forum? Not that you must, but the team loves that kind of feedback. They won't take all opportunities to make queries faster, if it's too complex for example, but they care a lot about speed of execution.
chasil 4y ago
The author of SQLite recently published a paper on olap performance and duckdb that went into greater detail on the virtual machine. https://news.ycombinator.com/item?id=32684424 https://news.ycombinator.com/item?id=32684424 Also, there is a "hint" mechanism in SQLite to force the use of a specific index. A variant of it ("not indexed") can be used to force a full table scan, which is appropriate when more than 5% of a table's rows are involved. The docs strongly admonish that these are not "hints," and the optimizer must obey these clauses when they are used. https://www.sqlite.org/lang_indexedby.html https://www.sqlite.org/lang_indexedby.html
- manimino 4y ago
  Exactly. So the workaround looks like: - Make one query with LIMIT of 5% - If it returns LIMIT rows, do a query with NOT INDEXED Which is surprising; why not build that into the query planning / execution in the first place?
  - dllthomas 4y ago
    The workaround is to understand how the questions you're asking the database relate to the structure of your data. What you describe is a brute force way to acquire that understanding on the fly on arbitrary queries. It might sometimes be the best you can do, and then it might be worth it (benchmark!), but in quite a few cases it'll be quite a bit slower.
    - manimino 4y ago
      That's a great point. The LIMIT workaround takes no knowledge of the data distribution, but an optimizer could do much better with some statistics such as estimated percentiles.
- lilyball 4y ago
  The docs also say these aren't meant to be used for performance tuning but instead of protecting against regressions if the schema changes. I guess the idea is once you're done and happy with performance you check the query plan for time-sensitive queries and update the relevant statements with INDEXED BY to reference the indexes they're already using.
  - chasil 4y ago
    In Oracle, stats can change a CBO query plan in ways that adversely affect performance. To address this, Oracle 7 added hints, and then 8i introduced the ability to "pin" an existing optimizer plan to a query. Stats are run here and there in SQLite, so I can see how bad stats could throw the cost-based optimizer (CBO) into bad performance. Stats can be manually run with the ANALYZE command. This should likely be done (among other things) prior to distributing SQLite databases to an audience, or perhaps in weekly maintenance of active databases undergoing extensive DML. https://www.sqlite.org/lang_analyze.html https://www.sqlite.org/lang_analyze.html
- hinkley 4y ago
  > full table scan, which is appropriate when more than 5% of a table's rows are involved Am I wrong in thinking this ratio could be improved? Table scan being 20x faster than indexes seems like it might be leaving quite a bit on the table.
  - HanyouHottie 4y ago
    I can believe it. Accessing sequential data that's being prefetched into cache is astonishingly faster than following references.
whalesalad 4y ago
cool library, potentially have an immediate need for it will take it for a spin. currently maintaining multiple dict's in order to achieve concurrent (air quotes with my fingers here) writes but as more dimensions are added, more locks are needed etc. memory is cheap so I'd rather just store a big list of objects
- manimino 4y ago
  Thanks! Hopefully ducks is everything you need it to be.
derefr 4y ago
> It seems like SQLite will only use one index, even in cases where two indexes would better suit the query. If you mean "one index per table per subquery", then AFAIK this is true of all RDBMSes. A query plan boils down to a bunch of "get [stream of tuples looking like X] out of [table Y]" leaf nodes; and those leaf nodes are then plan-optimized to extract those tuples using some particular strategy, which is always a very strict pipeline of "take a data source [table or index]; slice it to some range; then walk it either ascending or descending, filtering it, potentially with some offset+limit; and, if a non-covering index, dereference the index's file-offset-typed value to replace the index row-tuple with its backing table row-tuple." There's no room in that pipeline for having two indices work together to materialize one scan. If you want the effect of two indices working together, you either have to create a compound index (for a logical conjunction); or you have to use two subqueries and join them with UNION (for a logical disjunction.)

samatman 4y ago

Have you brought any of that up in the SQLite forum? Not that you must, but the team loves that kind of feedback. They won't take all opportunities to make queries faster, if it's too complex for example, but they care a lot about speed of execution.

chasil 4y ago

The author of SQLite recently published a paper on olap performance and duckdb that went into greater detail on the virtual machine. https://news.ycombinator.com/item?id=32684424 https://news.ycombinator.com/item?id=32684424 Also, there is a "hint" mechanism in SQLite to force the use of a specific index. A variant of it ("not indexed") can be used to force a full table scan, which is appropriate when more than 5% of a table's rows are involved. The docs strongly admonish that these are not "hints," and the optimizer must obey these clauses when they are used. https://www.sqlite.org/lang_indexedby.html https://www.sqlite.org/lang_indexedby.html

manimino 4y ago
Exactly. So the workaround looks like: - Make one query with LIMIT of 5% - If it returns LIMIT rows, do a query with NOT INDEXED Which is surprising; why not build that into the query planning / execution in the first place?
- dllthomas 4y ago
  The workaround is to understand how the questions you're asking the database relate to the structure of your data. What you describe is a brute force way to acquire that understanding on the fly on arbitrary queries. It might sometimes be the best you can do, and then it might be worth it (benchmark!), but in quite a few cases it'll be quite a bit slower.
  - manimino 4y ago
    That's a great point. The LIMIT workaround takes no knowledge of the data distribution, but an optimizer could do much better with some statistics such as estimated percentiles.
lilyball 4y ago
The docs also say these aren't meant to be used for performance tuning but instead of protecting against regressions if the schema changes. I guess the idea is once you're done and happy with performance you check the query plan for time-sensitive queries and update the relevant statements with INDEXED BY to reference the indexes they're already using.
- chasil 4y ago
  In Oracle, stats can change a CBO query plan in ways that adversely affect performance. To address this, Oracle 7 added hints, and then 8i introduced the ability to "pin" an existing optimizer plan to a query. Stats are run here and there in SQLite, so I can see how bad stats could throw the cost-based optimizer (CBO) into bad performance. Stats can be manually run with the ANALYZE command. This should likely be done (among other things) prior to distributing SQLite databases to an audience, or perhaps in weekly maintenance of active databases undergoing extensive DML. https://www.sqlite.org/lang_analyze.html https://www.sqlite.org/lang_analyze.html
hinkley 4y ago
> full table scan, which is appropriate when more than 5% of a table's rows are involved Am I wrong in thinking this ratio could be improved? Table scan being 20x faster than indexes seems like it might be leaving quite a bit on the table.
- HanyouHottie 4y ago
  I can believe it. Accessing sequential data that's being prefetched into cache is astonishingly faster than following references.

whalesalad 4y ago

cool library, potentially have an immediate need for it will take it for a spin. currently maintaining multiple dict's in order to achieve concurrent (air quotes with my fingers here) writes but as more dimensions are added, more locks are needed etc. memory is cheap so I'd rather just store a big list of objects

manimino 4y ago
Thanks! Hopefully ducks is everything you need it to be.

derefr 4y ago

> It seems like SQLite will only use one index, even in cases where two indexes would better suit the query. If you mean "one index per table per subquery", then AFAIK this is true of all RDBMSes. A query plan boils down to a bunch of "get [stream of tuples looking like X] out of [table Y]" leaf nodes; and those leaf nodes are then plan-optimized to extract those tuples using some particular strategy, which is always a very strict pipeline of "take a data source [table or index]; slice it to some range; then walk it either ascending or descending, filtering it, potentially with some offset+limit; and, if a non-covering index, dereference the index's file-offset-typed value to replace the index row-tuple with its backing table row-tuple." There's no room in that pipeline for having two indices work together to materialize one scan. If you want the effect of two indices working together, you either have to create a compound index (for a logical conjunction); or you have to use two subqueries and join them with UNION (for a logical disjunction.)