Scalar index queries handle NOT and NULL incorrectly

[wjones127]

This happens with both BTREE and BITMAP:

import pyarrow as pa
import lance

data = pa.table({"value": [True, False, None]})
ds = lance.write_dataset(data, "memory://")

ds.to_table(filter="NOT value")

value: int64
----
value: [[false]]

ds.create_scalar_index("value", "BTREE")
ds.to_table(filter="NOT value")

pyarrow.Table
value: int64
----
value: [[false,null]]

ds.create_scalar_index("value", "BITMAP", replace=True)
ds.to_table(filter="NOT value")

pyarrow.Table
value: int64
----
value: [[false,null]]

Similar things happen if you use integers and use condition like NOT (value = 1)

[westonpace]

Ah, this makes sense because we interpret NOT as the logical inverse. So if value = 1 does not include one then NOT value = 1 will. Not saying this is correct though 😦.

I'm not sure of a simple way to fix it except maybe push NOT down into the indexes themselves instead of handling it a layer above.

[wjones127]

This was accidentally closed by #4815

This PR doesn't fix #4756

[wjones127]

I think what we need to do is make scalar queries return something like a nullable selection vector. That way we can process the nulls properly at all stages. Then at the very end we can resolve it to mask.

I think this is how filters work in DataFusion: it takes a nullable Boolean array. Then when filter_record_batch is called it drops null and false.

[westonpace]

What is the physical representation of a nullable selection vector? We use roaring bitmaps today which are sparse. Can we introduce nulls without moving to a dense bitmap? Or should we just bite the bullet and move to dense bitmap? Maybe we can implement it as two sparse bitmaps (one of true/false and one of nulls)?

[wjones127]

We already represent things intermediately as two sparse bitmaps: allow lists and block lists. So I was thinking it would be natural to add a third null list. We’ll see where that lands me.

[westonpace]

If you're working on this, one other optimization I was thinking of making, is removing the "block list and allow list" case. Anytime we have this case we can simply normalize it into a smaller allow list (allow_list = allow_list - block_list ; block_list = None)