Optimize fillWindow to improve reverse-seek performance.

Bug: 5520301

When an application requests a row from a SQLiteCursor that
is not in the window, instead of filling from the requested
row position onwards, fill from a little bit ahead of the
requested row position.

This fixes a problem with applications that seek backwards
in large cursor windows.  Previously the application could
end up refilling the window every time it moved back
one position.

We try to fill about 1/3 before the requested position and
2/3 after which substantially improves scrolling responsiveness
when the list is bound to a data set that does not fit
entirely within one cursor window.

Change-Id: I168ff1d3aed1a41ac96267be34a026c108590e52

2 files changed, 45 insertions, 17 deletions

diff --git a/core/java/android/database/sqlite/SQLiteCursor.java b/core/java/android/database/sqlite/SQLiteCursor.java
index c24acd456908..8dcedf2fdd05 100644
--- a/core/java/android/database/sqlite/SQLiteCursor.java
+++ b/core/java/android/database/sqlite/SQLiteCursor.java
@@ -18,6 +18,7 @@ package android.database.sqlite;
 
 import android.database.AbstractWindowedCursor;
 import android.database.CursorWindow;
+import android.database.DatabaseUtils;
 import android.os.StrictMode;
 import android.util.Log;
 
@@ -48,7 +49,10 @@ public class SQLiteCursor extends AbstractWindowedCursor {
     private final SQLiteCursorDriver mDriver;
 
     /** The number of rows in the cursor */
-    private volatile int mCount = NO_COUNT;
+    private int mCount = NO_COUNT;
+
+    /** The number of rows that can fit in the cursor window, 0 if unknown */
+    private int mCursorWindowCapacity;
 
     /** A mapping of column names to column indices, to speed up lookups */
     private Map<String, Integer> mColumnNameMap;
@@ -158,18 +162,20 @@ public class SQLiteCursor extends AbstractWindowedCursor {
         return mCount;
     }
 
-    private void fillWindow(int startPos) {
+    private void fillWindow(int requiredPos) {
         clearOrCreateWindow(getDatabase().getPath());
-        mWindow.setStartPosition(startPos);
-        int count = getQuery().fillWindow(mWindow);
-        if (startPos == 0) { // fillWindow returns count(*) only for startPos = 0
+
+        if (mCount == NO_COUNT) {
+            int startPos = DatabaseUtils.cursorPickFillWindowStartPosition(requiredPos, 0);
+            mCount = getQuery().fillWindow(mWindow, startPos, requiredPos, true);
+            mCursorWindowCapacity = mWindow.getNumRows();
             if (Log.isLoggable(TAG, Log.DEBUG)) {
-                Log.d(TAG, "received count(*) from native_fill_window: " + count);
+                Log.d(TAG, "received count(*) from native_fill_window: " + mCount);
             }
-            mCount = count;
-        } else if (mCount <= 0) {
-            throw new IllegalStateException("Row count should never be zero or negative "
-                    + "when the start position is non-zero");
+        } else {
+            int startPos = DatabaseUtils.cursorPickFillWindowStartPosition(requiredPos,
+                    mCursorWindowCapacity);
+            getQuery().fillWindow(mWindow, startPos, requiredPos, false);
         }
     }
 
diff --git a/core/java/android/database/sqlite/SQLiteQuery.java b/core/java/android/database/sqlite/SQLiteQuery.java
index 7db0914140b2..5229f1286149 100644
--- a/core/java/android/database/sqlite/SQLiteQuery.java
+++ b/core/java/android/database/sqlite/SQLiteQuery.java
@@ -30,8 +30,10 @@ import android.util.Log;
 public class SQLiteQuery extends SQLiteProgram {
     private static final String TAG = "SQLiteQuery";
 
-    private static native int nativeFillWindow(int databasePtr, int statementPtr, int windowPtr,
-            int startPos, int offsetParam);
+    private static final boolean DEBUG_FILL_WINDOW_PERFORMANCE = false;
+
+    private static native long nativeFillWindow(int databasePtr, int statementPtr, int windowPtr,
+            int offsetParam, int startPos, int requiredPos, boolean countAllRows);
     private static native int nativeColumnCount(int statementPtr);
     private static native String nativeColumnName(int statementPtr, int columnIndex);
 
@@ -71,19 +73,39 @@ public class SQLiteQuery extends SQLiteProgram {
      * Reads rows into a buffer. This method acquires the database lock.
      *
      * @param window The window to fill into
-     * @return number of total rows in the query
+     * @param startPos The start position for filling the window.
+     * @param requiredPos The position of a row that MUST be in the window.
+     * If it won't fit, then the query should discard part of what it filled.
+     * @param countAllRows True to count all rows that the query would
+     * return regardless of whether they fit in the window.
+     * @return Number of rows that were enumerated.  Might not be all rows
+     * unless countAllRows is true.
      */
-    /* package */ int fillWindow(CursorWindow window) {
+    /* package */ int fillWindow(CursorWindow window,
+            int startPos, int requiredPos, boolean countAllRows) {
         mDatabase.lock(mSql);
         long timeStart = SystemClock.uptimeMillis();
         try {
             acquireReference();
             try {
                 window.acquireReference();
-                int numRows = nativeFillWindow(nHandle, nStatement, window.mWindowPtr,
-                        window.getStartPosition(), mOffsetIndex);
+                long result = nativeFillWindow(nHandle, nStatement, window.mWindowPtr,
+                        mOffsetIndex, startPos, requiredPos, countAllRows);
+                int actualPos = (int)(result >> 32);
+                int countedRows = (int)result;
+                window.setStartPosition(actualPos);
+                if (DEBUG_FILL_WINDOW_PERFORMANCE) {
+                    Log.d(TAG, "fillWindow: window=\"" + window
+                            + "\", startPos=" + startPos + ", requiredPos=" + requiredPos
+                            + ", countAllRows=" + countAllRows
+                            + ", offset=" + mOffsetIndex
+                            + ", actualPos=" + actualPos + ", filledRows=" + window.getNumRows()
+                            + ", countedRows=" + countedRows
+                            + ", took " + (SystemClock.uptimeMillis() - timeStart)
+                            + " ms, query=\"" + mSql + "\"");
+                }
                 mDatabase.logTimeStat(mSql, timeStart);
-                return numRows;
+                return countedRows;
             } catch (IllegalStateException e){
                 // simply ignore it
                 return 0;