test(rust): guard IVF merge row ordering

<!-- lance-gatekeeper-fix:v1 agent=5c80c44c083b3b8ad0da595419d468fc
generation=1 -->

## Root cause

The legacy synchronous Python table called `delete` on a shared, mutable
`lance.Dataset`. Concurrent table operations could hold a PyO3 borrow
while delete requested an exclusive borrow, producing `RuntimeError:
Already borrowed`. The current async-backed binding fixes this by
cloning its thread-safe Rust table handle before awaiting, but that
concurrency contract had no regression coverage.

## Fix

- Document why delete must clone the Rust table handle before entering
its async future.
- Add a barrier-synchronized regression test that deletes distinct rows
through one shared table from eight Python threads.
- Verify every delete commits exactly one row, every commit gets a
distinct version, and no rows remain.

## Validation

- `cargo check --quiet --features remote --tests --examples`
- `cargo fmt --all -- --check`
- `uv run --extra tests --extra dev ruff format --check
python/tests/test_table.py`
- `uv run --extra tests --extra dev ruff check
python/tests/test_table.py`
- `uv run --extra tests --extra dev pytest
python/tests/test_table.py::test_concurrent_deletes_are_thread_safe
python/tests/test_table.py::test_delete
python/tests/test_table.py::test_delete_expr
python/tests/test_table.py::test_delete_expr_async -q` (4 passed)
- Manual stress reproduction: 100 concurrent deletes on one table
completed at versions 2–101 with zero rows remaining.

Fixes #530

Co-authored-by: Gatefixer <313497061+lancedb-gatefixer[bot]@users.noreply.github.com>

python/python/lancedb/db.py

@@ -707,6 +707,9 @@ class LanceDBConnection(DBConnection):
         self._namespace_client_properties = namespace_client_properties
         if _inner is not None:
             self._conn = _inner
+            # Native-derived wrappers resolve this in their async reconstruction
+            # path so construction never synchronously re-enters LOOP.
+            self._read_consistency_interval = read_consistency_interval
             self._cached_namespace_client = None
             return
 
@@ -756,11 +759,14 @@ class LanceDBConnection(DBConnection):
         # storage_options.  Also, this class really shouldn't be holding any state
         # beyond _conn.
         self._conn = AsyncConnection(LOOP.run(do_connect()))
+        # Keep property access synchronous so debugger introspection cannot wait on
+        # the background loop while that thread is suspended at a breakpoint.
+        self._read_consistency_interval = read_consistency_interval
         self._cached_namespace_client: Optional[LanceNamespace] = None
 
     @property
     def read_consistency_interval(self) -> Optional[timedelta]:
-        return LOOP.run(self._conn.get_read_consistency_interval())
+        return self._read_consistency_interval
 
     @property
     def session(self) -> Optional[Session]:
@@ -771,8 +777,16 @@ class LanceDBConnection(DBConnection):
         return self._conn.uri
 
     @classmethod
-    def from_inner(cls, inner: LanceDbConnection):
-        return cls(None, _inner=inner)
+    def from_inner(
+        cls,
+        inner: LanceDbConnection,
+        read_consistency_interval: Optional[timedelta],
+    ):
+        return cls(
+            None,
+            read_consistency_interval=read_consistency_interval,
+            _inner=inner,
+        )
 
     def __repr__(self) -> str:
         return f"{self.__class__.__name__}(uri={self._conn.uri!r})"

python/python/lancedb/permutation.py

@@ -226,7 +226,7 @@ class PermutationBuilder:
 
         async def do_execute():
             inner_tbl = await self._async.execute()
-            return LanceTable.from_inner(inner_tbl)
+            return await LanceTable.from_inner(inner_tbl)
 
         return LOOP.run(do_execute())
 

python/python/lancedb/table.py

@@ -2182,11 +2182,15 @@ class LanceTable(Table):
         return self.name
 
     @classmethod
-    def from_inner(cls, tbl: LanceDBTable):
-        from .db import LanceDBConnection
+    async def from_inner(cls, tbl: LanceDBTable):
+        from .db import AsyncConnection, LanceDBConnection
 
         async_tbl = AsyncTable(tbl)
-        conn = LanceDBConnection.from_inner(tbl.database())
+        inner_conn = tbl.database()
+        read_consistency_interval = await AsyncConnection(
+            inner_conn
+        ).get_read_consistency_interval()
+        conn = LanceDBConnection.from_inner(inner_conn, read_consistency_interval)
         return cls(
             conn,
             async_tbl.name,

python/python/tests/test_db.py

@@ -77,6 +77,23 @@ def test_sync_repr_does_not_use_background_loop(tmp_path, monkeypatch):
     assert repr(table) == f"LanceTable(name='test', _conn={db!r})"
 
 
+def test_read_consistency_interval_does_not_use_background_loop(tmp_path, monkeypatch):
+    from lancedb.background_loop import LOOP
+    from lancedb.db import LanceDBConnection
+
+    consistency_interval = timedelta(seconds=5)
+    db = lancedb.connect(tmp_path, read_consistency_interval=consistency_interval)
+    db_from_inner = LanceDBConnection.from_inner(db._inner, consistency_interval)
+
+    def fail_run(*args, **kwargs):
+        raise AssertionError("properties should not use the Python background loop")
+
+    monkeypatch.setattr(LOOP, "run", fail_run)
+
+    assert db.read_consistency_interval == consistency_interval
+    assert db_from_inner.read_consistency_interval == consistency_interval
+
+
 def test_ingest_pd(tmp_path):
     db = lancedb.connect(tmp_path)
 

python/python/tests/test_permutation.py

@@ -6,6 +6,7 @@ import math
 import pytest
 
 from lancedb import DBConnection, Table, connect
+from lancedb.background_loop import LOOP
 from lancedb.permutation import Permutation, Permutations, permutation_builder
 
 
@@ -31,6 +32,25 @@ def test_split_random_ratios(mem_db):
     assert 65 <= split_1_count <= 75  # ~70% ± tolerance
 
 
+def test_execute_does_not_reenter_background_loop(tmp_path, monkeypatch):
+    import threading
+
+    db = connect(tmp_path)
+    tbl = db.create_table("test_table", pa.table({"x": range(10)}))
+    original_run = LOOP.run
+
+    def fail_on_reentry(future):
+        assert threading.current_thread() is not LOOP.thread
+        return original_run(future)
+
+    monkeypatch.setattr(LOOP, "run", fail_on_reentry)
+
+    permutation_tbl = permutation_builder(tbl).execute()
+
+    assert permutation_tbl.count_rows() == 10
+    assert permutation_tbl._conn.read_consistency_interval is None
+
+
 def test_split_random_counts(mem_db):
     """Test random splitting with absolute counts."""
     tbl = mem_db.create_table(

python/python/tests/test_table.py

@@ -6,6 +6,7 @@ import os
 import sys
 import threading
 import warnings
+from concurrent.futures import ThreadPoolExecutor
 from datetime import date, datetime, timedelta
 from time import sleep
 from typing import List
@@ -2124,6 +2125,27 @@ def test_delete(mem_db: DBConnection):
     assert table.to_arrow()["id"].to_pylist() == [1]
 
 
+def test_concurrent_deletes_are_thread_safe(mem_db: DBConnection):
+    num_workers = 8
+    table = mem_db.create_table(
+        "my_table", data=[{"id": row_id} for row_id in range(num_workers)]
+    )
+    barrier = threading.Barrier(num_workers)
+
+    def delete(row_id: int):
+        barrier.wait()
+        return table.delete(f"id = {row_id}")
+
+    with ThreadPoolExecutor(max_workers=num_workers) as pool:
+        results = list(pool.map(delete, range(num_workers)))
+
+    assert all(result.num_deleted_rows == 1 for result in results)
+    assert sorted(result.version for result in results) == list(
+        range(2, num_workers + 2)
+    )
+    assert table.count_rows() == 0
+
+
 def test_delete_expr(mem_db: DBConnection):
     table = mem_db.create_table(
         "my_table",

python/src/table.rs

@@ -745,6 +745,9 @@ impl Table {
 
     #[allow(private_interfaces)]
     pub fn delete(self_: PyRef<'_, Self>, condition: PredicateArg) -> PyResult<Bound<'_, PyAny>> {
+        // Do not hold the Python borrow across the await.  The cloned Rust table
+        // handle is thread-safe and allows deletes on the same Python table to
+        // run concurrently without PyO3 reporting "Already borrowed".
         let inner = self_.inner_ref()?.clone();
         future_into_py(self_.py(), async move {
             let result = match &condition {

rust/lancedb/src/table/create_index.rs

@@ -416,7 +416,7 @@ mod tests {
     use arrow_array::record_batch;
     use arrow_array::{
         Array, ArrayRef, BinaryArray, BooleanArray, FixedSizeListArray, Float32Array, Int32Array,
-        LargeBinaryArray, LargeStringArray, RecordBatch, StringArray, StructArray,
+        LargeBinaryArray, LargeStringArray, RecordBatch, StringArray, StructArray, UInt64Array,
     };
     use arrow_data::ArrayDataBuilder;
     use arrow_schema::{DataType, Field, Schema};
@@ -436,6 +436,55 @@ mod tests {
     use crate::table::optimize::{CompactionOptions, OptimizeAction};
     use lance_index::scalar::FullTextSearchQuery;
 
+    struct OrderPreservingShuffler;
+
+    struct SinglePartitionReader {
+        batches: Vec<RecordBatch>,
+    }
+
+    #[async_trait::async_trait]
+    impl lance_index::vector::v3::shuffler::Shuffler for OrderPreservingShuffler {
+        async fn shuffle(
+            &self,
+            data: Box<dyn lance_io::stream::RecordBatchStream + Unpin + 'static>,
+        ) -> lance_core::Result<Box<dyn lance_index::vector::v3::shuffler::ShuffleReader>> {
+            Ok(Box::new(SinglePartitionReader {
+                batches: data.try_collect().await?,
+            }))
+        }
+    }
+
+    #[async_trait::async_trait]
+    impl lance_index::vector::v3::shuffler::ShuffleReader for SinglePartitionReader {
+        async fn read_partition(
+            &self,
+            partition_id: usize,
+        ) -> lance_core::Result<
+            Option<Box<dyn lance_io::stream::RecordBatchStream + Unpin + 'static>>,
+        > {
+            if partition_id != 0 || self.batches.is_empty() {
+                return Ok(None);
+            }
+            let schema = self.batches[0].schema();
+            let stream = futures::stream::iter(self.batches.clone().into_iter().map(Ok));
+            Ok(Some(Box::new(
+                lance_io::stream::RecordBatchStreamAdapter::new(schema, stream),
+            )))
+        }
+
+        fn partition_size(&self, partition_id: usize) -> lance_core::Result<usize> {
+            Ok(if partition_id == 0 {
+                self.batches.iter().map(RecordBatch::num_rows).sum()
+            } else {
+                0
+            })
+        }
+
+        fn total_loss(&self) -> Option<f64> {
+            Some(0.0)
+        }
+    }
+
     fn create_fixed_size_list<T: Array>(
         values: T,
         list_size: i32,
@@ -840,6 +889,135 @@ mod tests {
         assert_eq!(stats.distance_type, Some(crate::DistanceType::L2));
     }
 
+    #[tokio::test]
+    async fn test_ivf_hnsw_sq_merge_preserves_shuffled_row_order() {
+        use lance::index::vector::builder::IvfIndexBuilder;
+        use lance_core::{ROW_ID, ROW_ID_FIELD, cache::LanceCache};
+        use lance_encoding::decoder::{DecoderPlugins, FilterExpression};
+        use lance_file::reader::{FileReader, FileReaderOptions};
+        use lance_index::INDEX_AUXILIARY_FILE_NAME;
+        use lance_index::vector::hnsw::{HNSW, builder::HnswBuildParams};
+        use lance_index::vector::ivf::IvfBuildParams;
+        use lance_index::vector::sq::{ScalarQuantizer, builder::SQBuildParams};
+        use lance_io::ReadBatchParams;
+        use lance_io::object_store::ObjectStore;
+        use lance_io::scheduler::{ScanScheduler, SchedulerConfig};
+        use lance_io::stream::RecordBatchStreamAdapter;
+        use lance_io::utils::CachedFileSize;
+
+        const NUM_ROWS: usize = 64;
+        const DIMENSION: i32 = 16;
+
+        let tmp_dir = tempdir().unwrap();
+        let conn = connect(tmp_dir.path().to_str().unwrap())
+            .execute()
+            .await
+            .unwrap();
+        let vector_field = Field::new(
+            "embeddings",
+            DataType::FixedSizeList(
+                Arc::new(Field::new("item", DataType::Float32, true)),
+                DIMENSION,
+            ),
+            false,
+        );
+        let values = Float32Array::from_iter_values(
+            (0..NUM_ROWS * DIMENSION as usize).map(|value| (value % 97) as f32),
+        );
+        let vectors = Arc::new(create_fixed_size_list(values, DIMENSION).unwrap());
+        let table_batch = RecordBatch::try_new(
+            Arc::new(Schema::new(vec![vector_field.clone()])),
+            vec![vectors.clone()],
+        )
+        .unwrap();
+        let table = conn
+            .create_table("test", table_batch)
+            .execute()
+            .await
+            .unwrap();
+
+        let dataset_guard = table.as_native().unwrap().dataset.get().await.unwrap();
+        let dataset = (*dataset_guard).clone();
+        drop(dataset_guard);
+
+        // Descending row IDs are a small sentinel for the removed merge-time
+        // sort. The old sort reordered this batch and used FixedSizeList::take,
+        // which overflowed for the large partitions reported in #3126.
+        let expected_row_ids = (0..NUM_ROWS as u64).rev().collect::<Vec<_>>();
+        let input_batch = RecordBatch::try_new(
+            Arc::new(Schema::new(vec![ROW_ID_FIELD.clone(), vector_field])),
+            vec![
+                Arc::new(UInt64Array::from(expected_row_ids.clone())),
+                vectors,
+            ],
+        )
+        .unwrap();
+        let input = RecordBatchStreamAdapter::new(
+            input_batch.schema(),
+            futures::stream::iter(vec![Ok(input_batch)]),
+        );
+
+        let index_dir = dataset.indices_dir().join(uuid::Uuid::new_v4().to_string());
+        let mut builder = IvfIndexBuilder::<HNSW, ScalarQuantizer>::new(
+            dataset,
+            "embeddings".to_string(),
+            index_dir.clone(),
+            lance_linalg::distance::DistanceType::L2,
+            Box::new(OrderPreservingShuffler),
+            Some(IvfBuildParams::new(1)),
+            Some(SQBuildParams::default()),
+            HnswBuildParams::default(),
+            None,
+        )
+        .unwrap();
+        builder.shuffle_data_input(Some(input));
+        builder.build().await.unwrap();
+
+        let object_store = Arc::new(ObjectStore::local());
+        let scheduler = ScanScheduler::new(object_store, SchedulerConfig::default_for_testing());
+        let auxiliary_path = index_dir.join(INDEX_AUXILIARY_FILE_NAME);
+        let reader = FileReader::try_open(
+            scheduler
+                .open_file(&auxiliary_path, &CachedFileSize::unknown())
+                .await
+                .unwrap(),
+            None,
+            Arc::<DecoderPlugins>::default(),
+            &LanceCache::no_cache(),
+            FileReaderOptions::default(),
+        )
+        .await
+        .unwrap();
+        let batches = reader
+            .read_stream(
+                ReadBatchParams::RangeFull,
+                u32::MAX,
+                1,
+                FilterExpression::no_filter(),
+            )
+            .await
+            .unwrap()
+            .try_collect::<Vec<_>>()
+            .await
+            .unwrap();
+        let stored_row_ids = batches
+            .iter()
+            .flat_map(|batch| {
+                batch
+                    .column_by_name(ROW_ID)
+                    .unwrap()
+                    .as_any()
+                    .downcast_ref::<UInt64Array>()
+                    .unwrap()
+                    .values()
+                    .iter()
+                    .copied()
+            })
+            .collect::<Vec<_>>();
+
+        assert_eq!(stored_row_ids, expected_row_ids);
+    }
+
     #[tokio::test]
     async fn test_create_index_ivf_hnsw_pq() {
         use std::iter::repeat_with;