diff --git a/keystore2/Android.bp b/keystore2/Android.bp
index 28bdfea..bfda27f 100644
--- a/keystore2/Android.bp
+++ b/keystore2/Android.bp
@@ -111,6 +111,7 @@
         "liblibsqlite3_sys",
         "libnix",
         "librusqlite",
+        "libtempfile",
     ],
     // The test should always include watchdog.
     features: [
diff --git a/keystore2/src/database/tests.rs b/keystore2/src/database/tests.rs
index 031d749..8b87973 100644
--- a/keystore2/src/database/tests.rs
+++ b/keystore2/src/database/tests.rs
@@ -42,7 +42,11 @@
 use std::time::Instant;
 
 pub fn new_test_db() -> Result<KeystoreDB> {
-    let conn = KeystoreDB::make_connection("file::memory:")?;
+    new_test_db_at("file::memory:")
+}
+
+fn new_test_db_at(path: &str) -> Result<KeystoreDB> {
+    let conn = KeystoreDB::make_connection(path)?;
 
     let mut db = KeystoreDB { conn, gc: None, perboot: Arc::new(perboot::PerbootDB::new()) };
     db.with_transaction(Immediate("TX_new_test_db"), |tx| {
@@ -2526,3 +2530,151 @@
     assert_eq!(third_sid_apps, vec![second_app_id]);
     Ok(())
 }
+
+// Starting from `next_keyid`, add keys to the database until the count reaches
+// `key_count`.  (`next_keyid` is assumed to indicate how many rows already exist.)
+fn db_populate_keys(db: &mut KeystoreDB, next_keyid: usize, key_count: usize) {
+    db.with_transaction(Immediate("test_keyentry"), |tx| {
+        for next_keyid in next_keyid..key_count {
+            tx.execute(
+                "INSERT into persistent.keyentry
+                        (id, key_type, domain, namespace, alias, state, km_uuid)
+                        VALUES(?, ?, ?, ?, ?, ?, ?);",
+                params![
+                    next_keyid,
+                    KeyType::Client,
+                    Domain::APP.0 as u32,
+                    10001,
+                    &format!("alias-{next_keyid}"),
+                    KeyLifeCycle::Live,
+                    KEYSTORE_UUID,
+                ],
+            )?;
+            tx.execute(
+                "INSERT INTO persistent.blobentry
+                         (subcomponent_type, keyentryid, blob) VALUES (?, ?, ?);",
+                params![SubComponentType::KEY_BLOB, next_keyid, TEST_KEY_BLOB],
+            )?;
+            tx.execute(
+                "INSERT INTO persistent.blobentry
+                         (subcomponent_type, keyentryid, blob) VALUES (?, ?, ?);",
+                params![SubComponentType::CERT, next_keyid, TEST_CERT_BLOB],
+            )?;
+            tx.execute(
+                "INSERT INTO persistent.blobentry
+                         (subcomponent_type, keyentryid, blob) VALUES (?, ?, ?);",
+                params![SubComponentType::CERT_CHAIN, next_keyid, TEST_CERT_CHAIN_BLOB],
+            )?;
+        }
+        Ok(()).no_gc()
+    })
+    .unwrap()
+}
+
+/// Run the provided `test_fn` against the database at various increasing stages of
+/// database population.
+fn run_with_many_keys<F, T>(max_count: usize, test_fn: F) -> Result<()>
+where
+    F: Fn(&mut KeystoreDB) -> T,
+{
+    android_logger::init_once(
+        android_logger::Config::default()
+            .with_tag("keystore2_test")
+            .with_max_level(log::LevelFilter::Debug),
+    );
+    // Put the test database on disk for a more realistic result.
+    let db_root = tempfile::Builder::new().prefix("ks2db-test-").tempdir().unwrap();
+    let mut db_path = db_root.path().to_owned();
+    db_path.push("ks2-test.sqlite");
+    let mut db = new_test_db_at(&db_path.to_string_lossy())?;
+
+    println!("\nNumber_of_keys,time_in_s");
+    let mut key_count = 10;
+    let mut next_keyid = 0;
+    while key_count < max_count {
+        db_populate_keys(&mut db, next_keyid, key_count);
+        assert_eq!(db_key_count(&mut db), key_count);
+
+        let start = std::time::Instant::now();
+        let _result = test_fn(&mut db);
+        println!("{key_count}, {}", start.elapsed().as_secs_f64());
+
+        next_keyid = key_count;
+        key_count *= 2;
+    }
+
+    Ok(())
+}
+
+fn db_key_count(db: &mut KeystoreDB) -> usize {
+    db.with_transaction(TransactionBehavior::Deferred, |tx| {
+        tx.query_row(
+            "SELECT COUNT(*) FROM persistent.keyentry
+                         WHERE domain = ? AND state = ? AND key_type = ?;",
+            params![Domain::APP.0 as u32, KeyLifeCycle::Live, KeyType::Client],
+            |row| row.get::<usize, usize>(0),
+        )
+        .context(ks_err!("Failed to count number of keys."))
+        .no_gc()
+    })
+    .unwrap()
+}
+
+#[test]
+fn test_handle_superseded_with_many_keys() -> Result<()> {
+    run_with_many_keys(1_000_000, |db| db.handle_next_superseded_blobs(&[], 20))
+}
+
+#[test]
+fn test_get_storage_stats_with_many_keys() -> Result<()> {
+    use android_security_metrics::aidl::android::security::metrics::Storage::Storage as MetricsStorage;
+    run_with_many_keys(1_000_000, |db| {
+        db.get_storage_stat(MetricsStorage::DATABASE).unwrap();
+        db.get_storage_stat(MetricsStorage::KEY_ENTRY).unwrap();
+        db.get_storage_stat(MetricsStorage::KEY_ENTRY_ID_INDEX).unwrap();
+        db.get_storage_stat(MetricsStorage::KEY_ENTRY_DOMAIN_NAMESPACE_INDEX).unwrap();
+        db.get_storage_stat(MetricsStorage::BLOB_ENTRY).unwrap();
+        db.get_storage_stat(MetricsStorage::BLOB_ENTRY_KEY_ENTRY_ID_INDEX).unwrap();
+        db.get_storage_stat(MetricsStorage::KEY_PARAMETER).unwrap();
+        db.get_storage_stat(MetricsStorage::KEY_PARAMETER_KEY_ENTRY_ID_INDEX).unwrap();
+        db.get_storage_stat(MetricsStorage::KEY_METADATA).unwrap();
+        db.get_storage_stat(MetricsStorage::KEY_METADATA_KEY_ENTRY_ID_INDEX).unwrap();
+        db.get_storage_stat(MetricsStorage::GRANT).unwrap();
+        db.get_storage_stat(MetricsStorage::AUTH_TOKEN).unwrap();
+        db.get_storage_stat(MetricsStorage::BLOB_METADATA).unwrap();
+        db.get_storage_stat(MetricsStorage::BLOB_METADATA_BLOB_ENTRY_ID_INDEX).unwrap();
+    })
+}
+
+#[test]
+fn test_list_keys_with_many_keys() -> Result<()> {
+    run_with_many_keys(1_000_000, |db: &mut KeystoreDB| -> Result<()> {
+        // Behave equivalently to how clients list aliases.
+        let domain = Domain::APP;
+        let namespace = 10001;
+        let mut start_past: Option<String> = None;
+        let mut count = 0;
+        let mut batches = 0;
+        loop {
+            let keys = db
+                .list_past_alias(domain, namespace, KeyType::Client, start_past.as_deref())
+                .unwrap();
+            let batch_size = crate::utils::estimate_safe_amount_to_return(
+                domain,
+                namespace,
+                &keys,
+                crate::utils::RESPONSE_SIZE_LIMIT,
+            );
+            let batch = &keys[..batch_size];
+            count += batch.len();
+            match batch.last() {
+                Some(key) => start_past.clone_from(&key.alias),
+                None => {
+                    log::info!("got {count} keys in {batches} non-empty batches");
+                    return Ok(());
+                }
+            }
+            batches += 1;
+        }
+    })
+}
diff --git a/keystore2/src/metrics_store.rs b/keystore2/src/metrics_store.rs
index 5a76d04..a55e52f 100644
--- a/keystore2/src/metrics_store.rs
+++ b/keystore2/src/metrics_store.rs
@@ -519,7 +519,7 @@
     }
 }
 
-fn pull_storage_stats() -> Result<Vec<KeystoreAtom>> {
+pub(crate) fn pull_storage_stats() -> Result<Vec<KeystoreAtom>> {
     let mut atom_vec: Vec<KeystoreAtom> = Vec::new();
     let mut append = |stat| {
         match stat {
diff --git a/keystore2/src/utils.rs b/keystore2/src/utils.rs
index 0a545f7..7e29f17 100644
--- a/keystore2/src/utils.rs
+++ b/keystore2/src/utils.rs
@@ -519,7 +519,7 @@
     result
 }
 
-fn estimate_safe_amount_to_return(
+pub(crate) fn estimate_safe_amount_to_return(
     domain: Domain,
     namespace: i64,
     key_descriptors: &[KeyDescriptor],
@@ -557,6 +557,9 @@
     items_to_return
 }
 
+/// Estimate for maximum size of a Binder response in bytes.
+pub(crate) const RESPONSE_SIZE_LIMIT: usize = 358400;
+
 /// List all key aliases for a given domain + namespace. whose alias is greater
 /// than start_past_alias (if provided).
 pub fn list_key_entries(
@@ -580,7 +583,6 @@
         start_past_alias,
     );
 
-    const RESPONSE_SIZE_LIMIT: usize = 358400;
     let safe_amount_to_return =
         estimate_safe_amount_to_return(domain, namespace, &merged_key_entries, RESPONSE_SIZE_LIMIT);
     Ok(merged_key_entries[..safe_amount_to_return].to_vec())