LabelListIndex: NOT filters mis-handle NULL lists (list-level NULLs)

[fenfeng9]

Description

Follow-up issue for #5867.

Reproduce

import lance
import pyarrow as pa

tbl = pa.table({"labels": [["foo"], ["bar"], None, []]})
dataset = lance.write_dataset(tbl, "/tmp/dataset", mode="overwrite")

filters = [
  "NOT array_has_any(labels, ['foo'])",
  "NOT array_has_all(labels, ['foo'])",
  "NOT array_contains(labels, 'foo')",
]

expected = {
  f: dataset.to_table(filter=f).column("labels").to_pylist() for f in filters
}

dataset.create_scalar_index("labels", index_type="LABEL_LIST")

actual = {
  f: dataset.to_table(filter=f).column("labels").to_pylist() for f in filters
}

print(f"{'Filter':<35} {'Expected':<25} {'Actual':<25} {'Match':<6}")
print("="*95)
for f in filters:
  exp_str = str(expected[f])
  act_str = str(actual[f])
  match = "✓" if expected[f] == actual[f] else "✗"
  print(f"{f:<35} {exp_str:<25} {act_str:<25} {match:<6}")

Result

Filter                              Expected                  Actual                    Match 
===============================================================================================
NOT array_has_any(labels, ['foo'])  [['bar'], []]             [['bar'], None, []]       ✗     
NOT array_has_all(labels, ['foo'])  [['bar'], []]             [['bar'], None, []]       ✗     
NOT array_contains(labels, 'foo')   [['bar'], []]             [['bar'], None, []]       ✗ 

[fenfeng9]

Hi @wjones127, I have a few questions regarding the following proposal.

My proposal is to fix list-level NULL semantics by persisting a separate RowAddrTreeMap for list-level NULL rows (label_list_nulls.lance) and OR-ing it into the result null-set so that NOT filters don’t treat list-level NULL as TRUE.

This changes the index format, so I plan to bump LABEL_LIST_INDEX_VERSION.

I’m unsure about the backward-compatibility strategy. Would it be acceptable to simply reject old LabelList indices (requiring a rebuild), or do we need to provide a compatibility/migration path?

Compatibility filtering happens during index load via retain_supported_indices.

lance/rust/lance/src/index.rs

Lines 691 to 711 in 9b0fa9a

	async fn load_indices(&self) -> Result<Arc<Vec<IndexMetadata>>> {
	let metadata_key = IndexMetadataKey {
	version: self.version().version,
	};
	let indices = match self.index_cache.get_with_key(&metadata_key).await {
	Some(indices) => indices,
	None => {
	let mut loaded_indices = read_manifest_indexes(
	&self.object_store,
	&self.manifest_location,
	&self.manifest,
	)
	.await?;
	retain_supported_indices(&mut loaded_indices);
	let loaded_indices = Arc::new(loaded_indices);
	self.index_cache
	.insert_with_key(&metadata_key, loaded_indices.clone())
	.await;
	loaded_indices
	}
	};

This is the current version‑filtering logic.

lance/rust/lance/src/index.rs

Lines 1189 to 1212 in 9b0fa9a

	pub(crate) fn retain_supported_indices(indices: &mut Vec<IndexMetadata>) {
	indices.retain(|idx| {
	let max_supported_version = idx
	.index_details
	.as_ref()
	.map(|details| {
	IndexDetails(details.clone())
	.index_version()
	// If we don't know how to read the index, it isn't supported
	.unwrap_or(i32::MAX as u32)
	})
	.unwrap_or_default();
	let is_valid = idx.index_version <= max_supported_version as i32;
	if !is_valid {
	log::warn!(
	"Index {} has version {}, which is not supported (<={}), ignoring it",
	idx.name,
	idx.index_version,
	max_supported_version,
	);
	}
	is_valid
	})
	}

[wjones127]

My proposal is to fix list-level NULL semantics by persisting a separate RowAddrTreeMap for list-level NULL rows (label_list_nulls.lance) and OR-ing it into the result null-set so that NOT filters don’t treat list-level NULL as TRUE.

This seems like a good solution.

I’m unsure about the backward-compatibility strategy. Would it be acceptable to simply reject old LabelList indices (requiring a rebuild), or do we need to provide a compatibility/migration path?

This is a good question.

I think erroring if there is an old LabelList index doesn't seem like the best solution.

I'm inclined to make sure we support both version, but log a warning if we find there is an old LabelList index on a nullable column. This index should be valid on a non-nullable column.

@westonpace may have an opinion here as well.

[westonpace]

I'm inclined to make sure we support both version, but log a warning if we find there is an old LabelList index on a nullable column. This index should be valid on a non-nullable column.

This sounds like a good approach. I think you can just set the list-level nulls bitmap to an empty set in this case so it shouldn't be too difficult to keep backwards compatibility. Logging a warning should be sufficient.