SQLite Query runs way slower on Android Lollipop

I have a query that runs perfectly fine on Gingerbread devices and Jellybean but runs a huge amount slower on Lollipop devices. I'm certain the query is correct and written well as it runs fine on the older devices.

Cursor c;
String query = QUERY STRING;

c = db.rawQuery(query,new String[]{Integer.toString(a),Integer.toString(b)});

Log.e("SQL_QUERY_PROGRESS","1");

while(c.moveToNext()){
    Log.e("SQL_QUERY_PROGRESS","2");
    // Do stuff with data
}

c.close();

On the Gingerbread device there was only 0.008 of a second between the two log messages whereas on the Lollipop devices it was taking ~8 seconds which is incredibly slow.

What I can't fathom is that the Lollipop devices are newer and have more RAM, CPU power etc so surely logic dictates that the newer devices should run the query faster than the older devices.

Could there be a bug with the version of Java used on Lollipop or could the SQLite version cause this massive decrease in speed?

I've used adb shell and navigated to the database file and ran the query using sqlite3 on the Lollipop devices and it ran almost instantly so that makes me think it's more of a Java problem than SQLite problem.

I'm completely out of ideas of what could be causing the delay so any help or ideas would be greatly appreciated so I can investigate further!