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

7 files changed, 105 insertions, 28 deletions

diff --git a/core/java/android/database/BulkCursorNative.java b/core/java/android/database/BulkCursorNative.java
index 20a9c67198b2..67cf0f82700a 100644
--- a/core/java/android/database/BulkCursorNative.java
+++ b/core/java/android/database/BulkCursorNative.java
@@ -180,13 +180,13 @@ final class BulkCursorProxy implements IBulkCursor {
         return mRemote;
     }
 
-    public CursorWindow getWindow(int startPos) throws RemoteException
+    public CursorWindow getWindow(int position) throws RemoteException
     {
         Parcel data = Parcel.obtain();
         Parcel reply = Parcel.obtain();
         try {
             data.writeInterfaceToken(IBulkCursor.descriptor);
-            data.writeInt(startPos);
+            data.writeInt(position);
 
             mRemote.transact(GET_CURSOR_WINDOW_TRANSACTION, data, reply, 0);
             DatabaseUtils.readExceptionFromParcel(reply);
diff --git a/core/java/android/database/CursorToBulkCursorAdaptor.java b/core/java/android/database/CursorToBulkCursorAdaptor.java
index 215035de3076..aa0f61e377e4 100644
--- a/core/java/android/database/CursorToBulkCursorAdaptor.java
+++ b/core/java/android/database/CursorToBulkCursorAdaptor.java
@@ -132,11 +132,11 @@ public final class CursorToBulkCursorAdaptor extends BulkCursorNative
     }
 
     @Override
-    public CursorWindow getWindow(int startPos) {
+    public CursorWindow getWindow(int position) {
         synchronized (mLock) {
             throwIfCursorIsClosed();
 
-            if (!mCursor.moveToPosition(startPos)) {
+            if (!mCursor.moveToPosition(position)) {
                 closeFilledWindowLocked();
                 return null;
             }
@@ -149,12 +149,11 @@ public final class CursorToBulkCursorAdaptor extends BulkCursorNative
                 if (window == null) {
                     mFilledWindow = new CursorWindow(mProviderName);
                     window = mFilledWindow;
-                    mCursor.fillWindow(startPos, window);
-                } else if (startPos < window.getStartPosition()
-                        || startPos >= window.getStartPosition() + window.getNumRows()) {
+                } else if (position < window.getStartPosition()
+                        || position >= window.getStartPosition() + window.getNumRows()) {
                     window.clear();
-                    mCursor.fillWindow(startPos, window);
                 }
+                mCursor.fillWindow(position, window);
             }
 
             // Acquire a reference before returning from this RPC.
diff --git a/core/java/android/database/CursorWindow.java b/core/java/android/database/CursorWindow.java
index 31e6f02c371e..e9675e8a1d22 100644
--- a/core/java/android/database/CursorWindow.java
+++ b/core/java/android/database/CursorWindow.java
@@ -55,6 +55,7 @@ public class CursorWindow extends SQLiteClosable implements Parcelable {
     public int mWindowPtr;
 
     private int mStartPos;
+    private final String mName;
 
     private final CloseGuard mCloseGuard = CloseGuard.get();
 
@@ -84,6 +85,8 @@ public class CursorWindow extends SQLiteClosable implements Parcelable {
     private static native boolean nativePutDouble(int windowPtr, double value, int row, int column);
     private static native boolean nativePutNull(int windowPtr, int row, int column);
 
+    private static native String nativeGetName(int windowPtr);
+
     /**
      * Creates a new empty cursor window and gives it a name.
      * <p>
@@ -95,6 +98,7 @@ public class CursorWindow extends SQLiteClosable implements Parcelable {
      */
     public CursorWindow(String name) {
         mStartPos = 0;
+        mName = name;
         mWindowPtr = nativeCreate(name, sCursorWindowSize);
         if (mWindowPtr == 0) {
             throw new CursorWindowAllocationException("Cursor window allocation of " +
@@ -129,6 +133,7 @@ public class CursorWindow extends SQLiteClosable implements Parcelable {
             throw new CursorWindowAllocationException("Cursor window could not be "
                     + "created from binder.");
         }
+        mName = nativeGetName(mWindowPtr);
         mCloseGuard.open("close");
     }
 
@@ -156,6 +161,14 @@ public class CursorWindow extends SQLiteClosable implements Parcelable {
     }
 
     /**
+     * Gets the name of this cursor window.
+     * @hide
+     */
+    public String getName() {
+        return mName;
+    }
+
+    /**
      * Closes the cursor window and frees its underlying resources when all other
      * remaining references have been released.
      */
@@ -758,4 +771,9 @@ public class CursorWindow extends SQLiteClosable implements Parcelable {
         String s = (buff.length() > 980) ? buff.substring(0, 980) : buff.toString();
         return "# Open Cursors=" + total + s;
     }
+
+    @Override
+    public String toString() {
+        return getName() + " {" + Integer.toHexString(mWindowPtr) + "}";
+    }
 }
diff --git a/core/java/android/database/DatabaseUtils.java b/core/java/android/database/DatabaseUtils.java
index a10ca1502a77..a8ba9a36ad2e 100644
--- a/core/java/android/database/DatabaseUtils.java
+++ b/core/java/android/database/DatabaseUtils.java
@@ -726,6 +726,32 @@ public class DatabaseUtils {
     }
 
     /**
+     * Picks a start position for {@link Cursor#fillWindow} such that the
+     * window will contain the requested row and a useful range of rows
+     * around it.
+     *
+     * When the data set is too large to fit in a cursor window, seeking the
+     * cursor can become a very expensive operation since we have to run the
+     * query again when we move outside the bounds of the current window.
+     *
+     * We try to choose a start position for the cursor window such that
+     * 1/3 of the window's capacity is used to hold rows before the requested
+     * position and 2/3 of the window's capacity is used to hold rows after the
+     * requested position.
+     *
+     * @param cursorPosition The row index of the row we want to get.
+     * @param cursorWindowCapacity The estimated number of rows that can fit in
+     * a cursor window, or 0 if unknown.
+     * @return The recommended start position, always less than or equal to
+     * the requested row.
+     * @hide
+     */
+    public static int cursorPickFillWindowStartPosition(
+            int cursorPosition, int cursorWindowCapacity) {
+        return Math.max(cursorPosition - cursorWindowCapacity / 3, 0);
+    }
+
+    /**
      * Query the table for the number of rows in the table.
      * @param db the database the table is in
      * @param table the name of the table to query
diff --git a/core/java/android/database/IBulkCursor.java b/core/java/android/database/IBulkCursor.java
index 7c967970a34f..0f4500a7aec8 100644
--- a/core/java/android/database/IBulkCursor.java
+++ b/core/java/android/database/IBulkCursor.java
@@ -30,11 +30,17 @@ import android.os.RemoteException;
  */
 public interface IBulkCursor extends IInterface  {
     /**
-     * Returns a BulkCursorWindow, which either has a reference to a shared
-     * memory segment with the rows, or an array of JSON strings.
+     * Gets a cursor window that contains the specified position.
+     * The window will contain a range of rows around the specified position.
      */
-    public CursorWindow getWindow(int startPos) throws RemoteException;
+    public CursorWindow getWindow(int position) throws RemoteException;
 
+    /**
+     * Notifies the cursor that the position has changed.
+     * Only called when {@link #getWantsAllOnMoveCalls()} returns true.
+     *
+     * @param position The new position
+     */
     public void onMove(int position) throws RemoteException;
 
     /**
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;