Zone map and bloom filter don't seem to handle deletions correctly

[wjones127]

I am getting fewer results than expected from queries when there is a zone map filter and deletions.

Reproduction

import pyarrow as pa
import lance

data = pa.table({
    "id": range(10),
    "value": [True, False] * 5,
})
ds = lance.write_dataset(data, "memory://")
ds.delete("NOT value") # Works if I comment this out

ds.to_table(filter="value")

pyarrow.Table
id: int64
value: bool
----
id: [[0,2,4,6,8]]
value: [[true,true,true,true,true]]

But if I add a zone map index, I get only the first three results:

ds.create_scalar_index("value", "ZONEMAP")
ds.to_table(filter="value")

pyarrow.Table
id: int64
value: bool
----
id: [[0,2,4]]
value: [[true,true,true]]

[wjones127]

I also found there is a similar issue with bloom filter:

import pyarrow as pa
import lance

data = pa.table({
    "id": range(10),
    "value": [1, 0] * 5,
})
ds = lance.write_dataset(data, "memory://")
ds.delete("NOT (value = 1)") # Works if I comment this out

ds.to_table(filter="value = 1")

pyarrow.Table
id: int64
value: int64
----
id: [[0,2,4,6,8]]
value: [[1,1,1,1,1]]

ds.create_scalar_index("value", "BLOOMFILTER")
ds.to_table(filter="value = 1")

pyarrow.Table
id: int64
value: int64
----
id: [[0,2,4]]
value: [[1,1,1]]

Interestingly, if we delete after creating the index, we get the expected result:

data = pa.table({
    "id": range(10),
    "value": [1, 0] * 5,
})
ds = lance.write_dataset(data, "memory://")
ds.create_scalar_index("value", "BLOOMFILTER")
ds.delete("NOT (value = 1)") # Works if I comment this out
ds.to_table(filter="value = 1")

pyarrow.Table
id: int64
value: int64
----
id: [[0,2,4,6,8]]
value: [[1,1,1,1,1]]

So maybe this is a bug in how training data is passed?

[HaochengLIU]

It's definitely a bug. I'm traveling right now thus no proper dev environment access

• Interestingly, if we delete after creating the index, we get the expected result:

Currently both zonemap and bloomfilter rely on ScalarIndex Trait to handle data updates. For the training data congestion path... Summoning the master @westonpace here

[westonpace]

Debugged this a little bit. The incoming data is...

Value	Frag Id	Offset in Frag
1	0	0
1	0	2
1	0	4
1	0	6
1	0	8

The zone that gets created is then...

Min	Max	Frag Id	Start	Size
1	1	0	0	5

In other words "the first 5 rows in frag 0 have these stats". However, we are getting the "first 5 logical rows". So the index becomes an index from min/max criteria to logical offsets.

So, when the query is "value = 1", it matches the first zone, and we say "Oh, you need to check rows 0..5". Except...the searcher thinks it is getting back row addresses and not logical offsets.

Two possible fixes:

1. When training the zone map we are not looking at the "offset in frag" at all. We could look at that and use that to determine the value of start / size. So, in the above example, we would have min=1, max=1, frag_id=0, start=0, size=9.
2. Change the index search result to indicate if it is returning physical row addresses or some kind of strange "logical row address" which is 32 bits of fragment id and 32 bits of logical offset.

I think 1 would be the simplest (and maybe a good excuse to coalesce some of the logic for the two zone-like indexes)?

[HaochengLIU]

• ds.delete("NOT (value = 1)")

To confirm my understanding, the above function call marks the non 1 rows as deleted. When the searcher builds the index later, the ZoneMap only sees data as above even it's build upon row address. The row concept mismatching makes things off the rail.

• Except...the searcher thinks it is getting back row addresses and not logical offsets.
  I'm slightly confused. My reading is zonemap/sbbf all relies on row addresses as the only source of truth?

Followup clarification question: In Lance, row address is physical row address. Am I reading that correct?

For the candidate fix 1, to use offset in frag, it should refer to row id sequence..?

[westonpace]

To confirm my understanding, the above function call marks the non 1 rows as deleted. When the searcher builds the index later, the ZoneMap only sees data as above even it's build upon row address. The row concept mismatching makes things off the rail.

Sounds right.

For the candidate fix 1, to use offset in frag, it should refer to row id sequence..?

No. The row id sequence maps row addresses to row ids. Currently, indexes always use row addresses. We don't need to worry about row ids.

I mean the lower 32 bits of the row address. If we look at the training code there are several places we use the fragment id...

            if self.maps.is_empty() && self.cur_zone_offset == 0 {
                let first_row_addr = row_addrs_array.value(0);
                self.cur_fragment_id = first_row_addr >> 32; # Fragment ID is here
            }

But we can also calculate the offset of the row in the fragment...

let frag_offset = first_row_addr as u32;

Also, there is a row address class to assist with this...

let row_addr = RowAddress::new_from_u64(first_row_addr);
let fragment_id = row_addr.fragment_id();
let row_offset = row_addr.row_offset();

[HaochengLIU]

The fix PR is ready for review.