CursorWindow grows without bound and looks up row slots in O(n), so reading a large cursor costs O(n²) #98

Summary

The time to read a cursor grows at least quadratically with its row count. Even moveToFirst() on a query without LIMIT copies every matching row into one window first. Two parts of the native CursorWindow combine to cause this:

1. The window never reports itself full, so all rows go into a single window.
2. Each row slot is found by walking a linked list of 100-row chunks from the start.

The framework's CursorWindow avoids both. It caps the window at its inflated size (2 MB by default), and it addresses slots in O(1).

Related: #99. A slow cursor fill holds its connection for the whole fill, and in WAL mode reads often get the primary connection, so writers wait for it.

Versions

• sqlcipher-android 4.19.1 (cipher_version reports 4.19.0 community).
• Android emulator sdk_gphone64_arm64, API 36.

Where it happens (v4.19.1)

1. The window inflates without limit. See CursorWindow::maybeInflate() in sqlcipher/src/main/jni/sqlcipher/CursorWindow.cpp:

size_t initialSize = 16 * 1024;
size_t newSize = mSize <= initialSize
                 ? 2048 * 1024
                 : mSize * 2;
...
if((mData = realloc(mData, newSize))){

• alloc() calls maybeInflate() whenever space runs out, so allocRow() never fails for lack of space and copyRow() never returns CPR_FULL (short of realloc failing, see below).
• The size passed to CursorWindow(String, int) is used only as the initial size. By default it is 16 KB (WINDOW_SIZE_KB = 16); the Javadoc of CursorWindow(String) still says "currently 2MB".

2. Every row is copied on the first fill. SQLiteCursor.fillWindow() calls mQuery.fillWindow(mWindow, startPos, requiredPos, true) while mCount == NO_COUNT. In nativeExecuteForCursorWindow, the loop while (!gotException && (!windowFull || countAllRows)) is meant to keep stepping only to count rows once the window is full. Because windowFull never becomes true, every row is copied into the window instead. A single moveToFirst() therefore materializes the whole result set. For the same reason, the "Row too big to fit in CursorWindow" branch in that loop is effectively unreachable.

3. Row slot lookup is O(n). CursorWindow::getRowSlot(row) and CursorWindow::allocRowSlot() walk RowSlotChunk (ROW_SLOT_CHUNK_NUM_ROWS = 100) from firstChunkOffset on every call:

while (chunkPos >= ROW_SLOT_CHUNK_NUM_ROWS) {
    chunk = static_cast<RowSlotChunk*>(offsetToPtr(chunk->nextChunkOffset));
    chunkPos -= ROW_SLOT_CHUNK_NUM_ROWS;
}

• allocRow() calls both functions for each copied row.
• Every put*() call in copyRow() also goes through getFieldSlot() → getRowSlot(), so copying one row walks the chunk list 2 + numColumns times.
• Every getLong/getString goes through getFieldSlot() → getRowSlot() as well.
• With N rows and C columns in one window, filling and reading the window both cost O(N² · C / 100), so wide tables suffer more than the 3-column table in the repro below.

AOSP's libs/androidfw/CursorWindow.cpp has neither problem:

• Field slots live in a contiguous region at the end of the window, so lookup is O(1):

  static_cast<uint8_t*>(mSlotsStart) - (((row * mNumColumns) + column) << kSlotShift)

• The window starts at kInlineSize (16 KB) and maybeInflate() grows it once, to mInflatedSize (2 MB by default). After that, copyRow returns CPR_FULL and the loop only counts rows.

Related problems in the same code

• realloc failure corrupts the window. mData = realloc(mData, newSize) overwrites mData with NULL when realloc fails. The old buffer leaks, and the next offsetToPtr() (for example in clear()) dereferences NULL instead of the window reporting itself full.
• The window never shrinks. SQLiteCursor reuses its window via win.clear(), and clear() doesn't touch mSize. A cursor that once inflated to many MB holds that memory until it is closed.
• Every resize is logged at ALOGI. Large result sets produce a log line for each doubling.

Minimal repro

The test uses a single table, t(id INTEGER PRIMARY KEY, a INTEGER, b TEXT), with about 75 bytes of text per row. It runs no Room code and sets no pragmas. One instrumented test runs the same queries on three databases:

• android.database.sqlite;
• sqlcipher-android with an empty password, i.e. no encryption;
• sqlcipher-android with a password.

// fullRead
db.rawQuery("SELECT id, a, b FROM t WHERE id <= ?", n).use { c ->
    while (c.moveToNext()) { c.getLong(0); c.getLong(1); c.getString(2) }
}
// moveToFirstOnly
db.rawQuery("SELECT id, a, b FROM t WHERE id <= ?", n).use { c -> c.moveToFirst(); c.getString(2) }
// chunkedRead: the same rows, as keyset pages of 2 000
db.rawQuery("SELECT id, a, b FROM t WHERE id > ? AND id <= ? ORDER BY id LIMIT 2000", lastId, n)

For android.database.sqlite, the same arguments are passed as String[], e.g. arrayOf(n.toString()).

Setup: sqlcipher-android 4.19.1, arm64 emulator, API 36. Each number is the median of 3 runs after a warm-up, in ms.

• Each time the row count doubles, the framework and SQLCipher's chunked read take about 2× longer. A single SQLCipher cursor takes 5.3–5.8× longer (154.1 → 812.7 ms), which is at least quadratic. The extra on top of 4× likely comes from the realloc copies.
• The key adds little: at 80k rows the chunked read with a key takes 115.4 ms vs 39.0 ms without, so decryption costs about 75 ms, while one cursor costs 740–770 ms more than chunks either way. The cost comes from CursorWindow, not from encryption.
• moveToFirst() alone takes 442 ms at 80k rows (59× the framework), because it copies the whole result set.
• Reading the same rows as 2 000-row pages is about 20× faster than one cursor.

import android.content.Context
import android.database.Cursor
import android.util.Log
import androidx.test.core.app.ApplicationProvider
import androidx.test.ext.junit.runners.AndroidJUnit4
import java.io.File
import org.junit.Assert.assertEquals
import org.junit.Test
import org.junit.runner.RunWith
import android.database.sqlite.SQLiteDatabase as FrameworkDatabase
import net.zetetic.database.sqlcipher.SQLiteDatabase as CipherDatabase

@RunWith(AndroidJUnit4::class)
class CursorWindowScalingReproTest {

    private val context: Context = ApplicationProvider.getApplicationContext()

    private interface Engine {
        val name: String
        fun query(sql: String, vararg args: Any): Cursor
        fun close()
    }

    @Test
    fun cursorScaling() {
        System.loadLibrary("sqlcipher")
        val engines = listOf(framework(), cipher("sqlcipher-plain", ""), cipher("sqlcipher-encrypted", "password"))
        engines.forEach { engine ->
            SIZES.forEach { n ->
                val full = median { assertEquals(n, readAll(engine, "$SELECT WHERE id <= ?", n.toLong())) }
                val first = median { moveToFirst(engine, "$SELECT WHERE id <= ?", n.toLong()) }
                val chunked = median { assertEquals(n, readChunked(engine, n.toLong())) }
                Log.i(TAG, "RESULT engine=${engine.name} rows=$n fullRead=${ms(full)}ms " +
                    "moveToFirstOnly=${ms(first)}ms chunkedRead=${ms(chunked)}ms")
            }
            engine.close()
        }
    }

    private fun readAll(engine: Engine, sql: String, vararg args: Any): Int {
        var rows = 0
        engine.query(sql, *args).use { cursor ->
            while (cursor.moveToNext()) {
                cursor.getLong(0)
                cursor.getLong(1)
                cursor.getString(2)
                rows++
            }
        }
        return rows
    }

    private fun moveToFirst(engine: Engine, sql: String, vararg args: Any) {
        engine.query(sql, *args).use { cursor ->
            check(cursor.moveToFirst())
            cursor.getString(2)
        }
    }

    private fun readChunked(engine: Engine, n: Long): Int {
        var rows = 0
        var lastId = 0L
        while (true) {
            var read = 0
            engine.query("$SELECT WHERE id > ? AND id <= ? ORDER BY id LIMIT $CHUNK", lastId, n).use { cursor ->
                while (cursor.moveToNext()) {
                    lastId = cursor.getLong(0)
                    cursor.getLong(1)
                    cursor.getString(2)
                    read++
                }
            }
            rows += read
            if (read < CHUNK) return rows
        }
    }

    private fun framework(): Engine {
        val db = FrameworkDatabase.openOrCreateDatabase(freshFile("repro-framework.db"), null)
        db.beginTransaction()
        try {
            populate { sql, args -> db.execSQL(sql, args) }
            db.setTransactionSuccessful()
        } finally {
            db.endTransaction()
        }
        return object : Engine {
            override val name = "framework"
            override fun query(sql: String, vararg args: Any): Cursor =
                db.rawQuery(sql, args.map { it.toString() }.toTypedArray())
            override fun close() = db.close()
        }
    }

    private fun cipher(engineName: String, password: String): Engine {
        val file = freshFile("repro-$engineName.db")
        val db = CipherDatabase.openDatabase(file.path, password, null, CipherDatabase.CREATE_IF_NECESSARY, null)
        db.beginTransaction()
        try {
            populate { sql, args -> db.execSQL(sql, args) }
            db.setTransactionSuccessful()
        } finally {
            db.endTransaction()
        }
        return object : Engine {
            override val name = engineName
            override fun query(sql: String, vararg args: Any): Cursor = db.rawQuery(sql, *args)
            override fun close() = db.close()
        }
    }

    private fun populate(exec: (String, Array<Any>) -> Unit) {
        exec("CREATE TABLE t (id INTEGER PRIMARY KEY, a INTEGER NOT NULL, b TEXT NOT NULL)", emptyArray())
        for (i in 1..SIZES.max()) {
            exec("INSERT INTO t (id, a, b) VALUES (?, ?, ?)", arrayOf(i, i * 31L, "row-$i-" + "x".repeat(64)))
        }
    }

    private fun freshFile(name: String): File {
        context.deleteDatabase(name)
        return context.getDatabasePath(name).also { it.parentFile?.mkdirs() }
    }

    private fun median(block: () -> Unit): Long {
        block()
        return List(RUNS) {
            val start = System.nanoTime()
            block()
            System.nanoTime() - start
        }.sorted()[RUNS / 2]
    }

    private fun ms(nanos: Long) = "%.1f".format(nanos / 1e6)

    private companion object {
        const val TAG = "CursorWindowRepro"
        const val SELECT = "SELECT id, a, b FROM t"
        val SIZES = listOf(10_000, 20_000, 40_000, 80_000)
        const val CHUNK = 2_000
        const val RUNS = 3
    }
}

Expected

The cost of reading a cursor should grow roughly linearly with its row count, as with android.database.sqlite. moveToFirst() on an unbounded query should not copy every row into native memory.

Possible fixes

Growing the window probably exists on purpose, so that a single large row (e.g. a big blob) still fits. The fixes below keep that.

• Bound inflation the way AOSP does. Start small and grow up to a fixed ceiling (2 MB, like mInflatedSize), then let alloc() fail so that copyRow returns CPR_FULL and the existing counting-only path takes over. Growing past the ceiling would only be allowed while the window is still empty, i.e. for a single oversized row. Capping at the initial windowSizeBytes instead would not help: at the 16 KB default the window holds only about a hundred rows, and every refill re-steps the query from the start.
• Address row slots in O(1). For example, use AOSP's contiguous slot layout, or at least keep a pointer to the last chunk in allocRowSlot() and index chunks directly in getRowSlot().
• Keep the old buffer when realloc fails, and report the window as full instead.
• Log resizes at debug level.

Workaround

Add LIMIT to single-row queries and page large reads with keyset chunks.

Happy to test a patch or provide more measurements.