Banshee freezes shortly (about 5–10s) between songs

[drunken monkey]

Two days ago, I made some small changes to my music library in Banshee, removing some songs, adding others, etc. But not on a large scale.

Anyways, since then I have the problem that after every song (I'm playing a playlist, in shuffle mode) Banshee freezes for several seconds, the window graying out after a few of them, until playback resumes normally with the next song. The same upon initially starting playback and when skipping ahead to the next song.

I activated --debug and got the following output when Banshee freezes:

[5 Warn 18:24:58.416] Executed in 18321ms 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 = 131 AND CoreArtists.ArtistID = CoreTracks.ArtistID AND CoreAlbums.AlbumID = CoreTracks.AlbumID
                        AND 1=1
                        AND LastStreamError = 0
                        AND (LastPlayedStamp < 1410024153 OR LastPlayedStamp IS NULL)
                        AND (LastSkippedStamp < 1410024153 OR LastSkippedStamp IS NULL)
                        ORDER BY RANDOM () LIMIT 1

So, apparently, there is a really slow SQL query executed for finding out the next song. What I don't understand, though, is why this problem suddenly occurred, since I only added a few songs to that playlist – also, there are now only 365 songs in that list, so really nothing that should lead to such lags.

Ubuntu version: Ubuntu 14.04.1 LTS
Package version banshee: 2.9.0+really2.6.2-2ubuntu2.1