An SQLite3 query is running nearly instantaneous on some versions of a database, but takes orders of magnitude longer on others

Question

I am old-fashioned and have been using Banshee as my primary music player for years. Luckily I am mostly happy with it, except for a certain issue I've been debugging for the past few days, in which, when shuffling to a new track on a playlist, it will freeze and have high CPU usage for a significant amount of time (proportional to the size of the playlist). For example, about 16 seconds for a 512-track playlist, or over 3 minutes for a 6000-track playlist. I also use Banshee on my work computer (albeit with a somewhat smaller library), and the issue is completely absent there; shuffling takes no perceptible time on any size of playlist, even the 6000-track one.

As I said, I've been studying this problem intensively for a while now. I first tried modifying the Banshee library file in various ways to see if I could produce one with the same basic content as my original one, but without the slow shuffling issue. I eventually discovered that deleting most of my playlists "solved" the issue. By comparing libraries with and without the issue, through a process approximating a binary search, I managed to produce a library file that manifested the slow shuffle issue but could be transformed into one that didn't by running a single update command:

UPDATE sqlite_stat1 SET stat='18800 1447 1' WHERE rowid=18;

After looking into what the sqlite_stat1 table is, I realized that this wasn't a bug in Banshee so much as a deep issue with SQLite3 and how it optimizes queries. Running the ANALYZE command to update the sqlite_stat1 table resolves the issue for the library file that's just one command away from working, but not for my "real" library; I'm not sure why.

I then noticed Banshee has a --debug-sql argument, which let me retrieve the actual query that was taking so long. It is being run after a few hundred other setup commands (such as creating and populating the temporary table, CoreCache) to transform the database into the temporary state in which this query runs either instantaneously or agonizingly slowly:

SELECT CoreTracks.Rating,CoreTracks.LastStreamError,CoreTracks.TrackID,
CoreTracks.PrimarySourceID,CoreTracks.ArtistID,CoreTracks.AlbumID,CoreTracks.TagSetID,
CoreTracks.MusicBrainzID,CoreTracks.MimeType,CoreTracks.FileSize,
CoreTracks.FileModifiedStamp,CoreTracks.LastSyncedStamp,CoreTracks.Attributes,
CoreTracks.Title,CoreTracks.TitleSort,CoreTracks.TrackNumber,CoreTracks.TrackCount,
CoreTracks.Disc,CoreTracks.DiscCount,CoreTracks.Duration,CoreTracks.Year,
CoreTracks.Genre,CoreTracks.Composer,CoreTracks.Conductor,CoreTracks.Grouping,
CoreTracks.Copyright,CoreTracks.LicenseUri,CoreTracks.Comment,CoreTracks.BPM,
CoreTracks.BitRate,CoreTracks.SampleRate,CoreTracks.BitsPerSample,CoreTracks.Score,
CoreTracks.PlayCount,CoreTracks.SkipCount,CoreTracks.ExternalID,
CoreTracks.LastPlayedStamp,CoreTracks.LastSkippedStamp,CoreTracks.DateAddedStamp,
CoreTracks.DateUpdatedStamp,CoreTracks.Uri,CoreArtists.Name,CoreArtists.NameSort,
CoreAlbums.Title,CoreAlbums.TitleSort,CoreAlbums.ArtistName,CoreAlbums.ArtistNameSort,
CoreAlbums.IsCompilation,CoreAlbums.MusicBrainzID,CoreArtists.MusicBrainzID
, OrderID, CoreCache.ItemID
FROM CoreTracks,CoreArtists,CoreAlbums
INNER JOIN CorePlaylistEntries
    ON CoreTracks.TrackID = CorePlaylistEntries.TrackID
INNER JOIN CoreCache
    ON CorePlaylistEntries.EntryID = CoreCache.ItemID 
WHERE
    CoreCache.ModelID = 188 AND
    CoreArtists.ArtistID = CoreTracks.ArtistID AND
    CoreAlbums.AlbumID = CoreTracks.AlbumID 
AND 1=1
AND LastStreamError = 0
AND (LastPlayedStamp < 1518483204 OR LastPlayedStamp IS NULL)
AND (LastSkippedStamp < 1518483204 OR LastSkippedStamp IS NULL)
ORDER BY RANDOM ()
LIMIT 1;

Here are the schema and sizes of the relevant tables at the time that the time-consuming query is run. These are all the same in the versions of the database in which the slow shuffle issue does and does not happen.

Running EXPLAIN QUERY PLAN on the query in a database where the issue occurs gives this plan:

0|0|0|SEARCH TABLE CoreTracks USING AUTOMATIC COVERING INDEX (LastStreamError=?)
0|1|1|SEARCH TABLE CoreArtists USING INTEGER PRIMARY KEY (rowid=?)
0|2|2|SEARCH TABLE CoreAlbums USING INTEGER PRIMARY KEY (rowid=?)
0|3|4|SEARCH TABLE CoreCache USING AUTOMATIC COVERING INDEX (ModelID=?)
0|4|3|SEARCH TABLE CorePlaylistEntries USING INTEGER PRIMARY KEY (rowid=?)
0|0|0|USE TEMP B-TREE FOR ORDER BY

And running it in a database where the issue does not occur gives this different plan:

0|0|4|SCAN TABLE CoreCache
0|1|3|SEARCH TABLE CorePlaylistEntries USING INTEGER PRIMARY KEY (rowid=?)
0|2|0|SEARCH TABLE CoreTracks USING INTEGER PRIMARY KEY (rowid=?)
0|3|1|SEARCH TABLE CoreArtists USING INTEGER PRIMARY KEY (rowid=?)
0|4|2|SEARCH TABLE CoreAlbums USING INTEGER PRIMARY KEY (rowid=?)
0|0|0|USE TEMP B-TREE FOR ORDER BY

Even after all the information on the problem I've gathered, I have plenty of questions. Why is SQLite using a different, slower query plan? Why does simply updating the cached information about the CorePlaylistEntriesIndex solve the issue sometimes, but not always? What is the basic cause of this query taking such drastically different times to run on nearly identical databases? (I'm guessing some optimization that is or is not being used)

For reference, I am running SQLite version 3.8.2, and (when I invoke SQLite through Python) am using Python 3.4.2. I've tried running the SQL to produce the problem on the current version of SQLite, 3.22, and found that some of the setup commands (INSERTs with nested SELECTs) now take inordinately long. I briefly tried patching the SQLite 3.22 executable into my system and running Banshee using it, but the slow shuffle issue was unchanged.

Answer 1

SQLite implements joins as nested loops, i.e., for each (filtered) row in one table, it looks up all matching rows in the other table. This runs faster when there are fewer rows, so the database tries to reorder the joins so that the most rows are filtered out by the WHERE clause(s) on the outermost table(s).

To estimate the selectivity of a WHERE clause, SQLite uses the information collected by ANALYZE. But when you did not run ANALYZE, or when the column is not indexed, the database does not have this information, and it just assumes that any WHERE clause of the form column = value is pretty much suitable.

The expression LastStreamError = 0 looks for the database as if it might filter out many rows, but in practice, it probably doesn't.

To speed up the query, try adding an index on LastStreamError and then running ANALYZE.

If possible, update the SQLite version; the query optimizer is constantly being improved.