SQLite newer version makes queries runner a lot slower than on previous versions

I have a query that run perfectly fine on some devices but it's very slow on Lollipop devices.

It run fine on: Kitkat with SQLite 3.7.11

Gingerbread with SQLite 3.6.22

It runs very slow on: Lollipop with 3.8.6

I've tried it on two different Lollipop devices so I'm almost certain it isn't a particular device being slow.

Lollipop devices show messages about automatic indexing such as:

(284) automatic index on teamuser(uid)

I've tried adding an index for any columns that shows this message and the auto index message is replaced with something like this:

(284) automatic index on sqlite_sq_9B00E900(uid)

I'm not entirely certain that the SQLite version is to blame but I'd be quite surprised if it wasn't something to do with the slowness.

Is it possible to get the newest version of SQLite to behave like previous versions or disable auto indexing to speed up the queries as it's currently take roughly 5 times longer to execute a query on Lollipop devices?