Proposed format change: Add invalidated_fragments field for IndexMetadata

[wjones127]

Background

• We track the coverage of an index segment with the fragment_bitmap field. If the fragment_bitmap is {0, 1}, we say it covers both fragment 0 and fragment 1.
• When a row is deleted, we create a deletion file in a fragment. The row addresses in this deletion file are masked out of index results at runtime.
• When a fragment is deleted, but is present in the fragment_bitmap, we mask out all row addresses matching that deleted fragment.
• Most operations perform updates by deleting the old rows and appending the updated versions. Therefore, given the two above bullet points, they won't point to out-of-date data.
• However, there are a few operations that can update fragments in-place: DataReplacement and one codepath of merge-insert. These currently can cause issues where indices point to invalid data. See an example in Getting non-existent fragment error in merge_insert #5321.

Proposed changes

1. Introduce a new field invalidated_fragments, representing fragments for which the rows in an index segment should be not be considered in queries.
2. Consider the fragments that an index covers be the set difference between fragment_bitmap and invalidated_fragments. This should be mutually exclusive across fragments.
   1. Note: this means that fragment_bitmap may now overlap. For example, you might have one index segment with fragment_bitmap: {0, 1}, invalidated_fragments: {1}, and another index segment with fragment_bitmap: {1}, invalidated_fragments: {}. This might happen if the first index was built on both fragment, then fragment 1 was updated in place, and then a new index segment was trained on the updated fragment.
3. New rules for merging index segments:
   1. Deleted fragments should either (a) have their row addresses removed from the merged index, or (b) be included in the fragment_bitmap of the resulting index. Failing to do either could lead to incorrect query results.
   2. In-place updated fragments should either (a) have their row addresses removed from the merged index, or (b) be included in the invalidated_fragments field of the resulting index. Failing to do either could lead to incorrect query results.

Frequently asked questions

Why not just modify fragment_bitmap?

To construct a mask for deleted fragments, we take fragment_bitmap \ fragment_in_dataset. If we start removing fragments in the fragment_bitmap, then this calculation will not be valid anymore. We could switch to using an allow_list for fragment_bitmap, but for performance reasons we'd like to keep the deleted fragments filter to be a deny list, as this lets the case of no deletions be a no-op.

Further reading

• I have drafted the changes in this PR: feat(format): track invalidated_fragments for index segments #5441
• As part of that PR, I rewrote the index specification to be clearer about how indices work in Lance. You can read that here: https://github.com/wjones127/lance/blob/f8290480d5e1470457632a1e44f47b514942d7ea/docs/src/format/table/index/index.md

[westonpace]

In the Update operation we have fields_modified and fields_for_preserving_frag_bitmap which we use to remove fragments from an index's fragment bitmap (because the field the index covers is invalidated).

To construct a mask for deleted fragments, we take fragment_bitmap \ fragment_in_dataset. If we start removing fragments in the fragment_bitmap, then this calculation will not be valid anymore. We could switch to using an allow_list for fragment_bitmap, but for performance reasons we'd like to keep the deleted fragments filter to be a deny list, as this lets the case of no deletions be a no-op.

I'm not sure I understand? If a fragment isn't in the fragment_bitmap we don't think it is deleted do we? Doesn't that just mean the fragment is unindexed?

[wjones127]

If a fragment isn't in the fragment_bitmap we don't think it is deleted do we? Doesn't that just mean the fragment is unindexed?

Yes, if a fragment isn't in the fragment_bitmap, it is unindexed. That's good for index updates; if we invalidate a fragment in an index segment, we want to be able to train a new index segment for the updated fragment. Removing it from the fragment bitmap allows that now. It's the construction of the mask for index results that it messes up.