Bangin' on a Rok Amarok, KDE, and all that good stuff

The Collection Scanner’s Ultimate Speed Bump

A couple of weeks ago I spent a long period of time looking at ways to increase scanning speed. Yes, again. I had written previously (here and here) on changes I'd made to increase the speed of scanning collections, and I'd made a lot of other changes that I didn't write about. These certainly helped in many situations, and made significant differences for particular users, but overall we still had a large speed boondoggle: the number of queries issued per track to the database.

This number was at least three. At the very minimum, assuming the artist, album, genre, composer, and year had been cached, you had a lookup for the uniqueid, a lookup to check for whether the track was part of a compilation, and an insert. This number could be significantly higher in some situations; but these database queries were a large part of the reason that a scan might run, finish disk I/O, and then spend quite a long time eating up CPU time before it was done.

I looked at increasing the number of values I was pulling in using UNION queries, which was currently up to five values (depending on whether they were already cached). I also looked at prepared statements, which it turns out were not likely to give us a large speed bump and are an absolute and utter pain in the ass when using the C API as we are. (We use the C API for historical reasons; also, the official C++ API is not easily available in many distributions, and there are many unofficial contenders.)

Finally, I looked at ripping the guts out of the scan result processor and doing what  several of us devs had decided would probably be the best way to improve speed, but was at the same time the most challenging: replacing the SQL statements with local memory storage, populating these at the beginning of a scan and re-populating the database at the end. It wasn't easy. I selected data structures very carefully for speed, looking at how often each query would be run and the time complexities of insertion and lookup into various types of structures.  In addition, because of a few complex queries using joins, the behavior we needed could only be emulated by using very complex data structures (one of them is a QHash<QPair<int, QString>, QStringList*>; another is a QHash<QString, QLinkedList<QStringList*> *>). I also wanted to minimize memory usage...I did some rough back-of-the-hand calculations which indicated that using my design, for the vast, vast majority of collections, memory usage during the scan was likely to go up by only a couple of megabytes at the very most, which would be reclaimed at the end.

In addition, I implemented logic to drastically decrease the total queries needed for insertion. Since I'm constructing the final queries from the data structures, I could easily do insertion of multiple values at once. So now the database is queried at the start to see the maximum query size it will accept; then values for insertion are appended to the query up until this value is hit, at which point the query is run and a new query begun. By default I think this is one megabyte for most installations, which means that instead of possibly thousands upon thousands of insertion queries (depending on the size of your collection), you'd have to have an absolutely extraordinarily large collection to have more than 25 or so queries for the entire scan. Since there is not only round-trip delay sending data to and receiving responses from the database but also the database must parse each query each time it's run (the purpose of prepared statements is to reduce this), then this makes a drastic difference. To put it another way, the number of queries per track has gone from a minimum of three to an asymptotic value of zero.

Overall, the work seems to have paid off rather nicely. Benchmark reports that I got back indicated anywhere from 30% to 300% gains in the total time for a scan, depending on size of collection and your particular I/O throughput/CPU/etc.

I call this the Ultimate Speed Bump in the title because there is far less that can be done from this point on to increase speed, at least as far as I can currently tell -- this was the Big Mama, the elephant in the room. But hopefully it will increase scan processing enough that further increases won't really be so much of a necessity anymore.

One other data point: the database is now case-sensitive, which is something we've intended to do for a long time but is now being done. It's been a very long-standing feature request that we've finally implemented (we wanted it too), and thankfully it wasn't much work to do this and change the appropriate points in the rest of the code.

(By the by, this will all be in 2.2.1 -- enjoy!)