There has been a recent flurry of comments about SQLite at
http://www.reddit.com/r/programming/comments/8oed5/how_sqlite_is_tested/
http://news.ycombinator.com/item?id=633151
One of the criticisms of SQLite is that it is slow to do joins. That
is true if SQLite is unable to figure out how to use an index to speed
the join. I was under the impression that SQLite actually did a
fairly reasonable job of making use of indices, if they exist. But
without indices, an k-way join takes time proportional to N^k.
Do other SQL database engines not have this same limitation? Are
MySQL and PostgreSQL and Firebird and MS-SQL and Oracle creating
phantom indices on-the-fly to help them do joins faster, for example?
Or do their optimizers do a better job of finding ways to use indices
in a join? Can somebody supply me with specific examples of joins
that other database engines do efficiently but that SQLite does
slowly? Is join efficiency really a frustration to many SQLite users?
Curiously, in some of our own internal tests, SQLite is much, much
faster than MS-SQL, MySQL, and PostgreSQL for k-way joins where k is
large - greater than 20 or 30. (SQLite can handle up to a 64-way
join.) This is because SQLite uses a O(k*k) greedy algorithm for
selecting the ordering of tables in the join whereas the other guys
all do a much more extensive search. So the performance loss in the
other engines is due to the excessive time spent in the query planner,
not the time actually running the query. SQLite can plan a 64-way
join in the blink of an eye, whereas PostgreSQL requires several
minutes.
But for the tests described in the previous paragraph, there were
always good indices so that the time to actually run the join was
approximately linear. What about situations where you have a 4- or 5-
way join on tables that are not indexed? Do other database engines
handle those more efficiently than SQLite somehow? Is this something
we need to look into?
D. Richard Hipp
[email protected]
_______________________________________________
sqlite-users mailing list
[email protected]
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
