/// Merge function for items in the object store.
///
/// The most interesting behaviour in this merge function is how extents are handled. Since extents
/// can overlap and replace one another, the merge function generally builds up the most
/// recent view of the extents in the tree, so that the output of a full merge contains no
/// overlapping extents. You can imagine looking down at the extents from the top-most layer.
///
/// A brief example:
///
/// Layer 0   |a-a-a-a|     |b-b-b|
/// Layer 1   |c-c-c-c-c|
/// Layer 2                     |d-d-d-d|
///
/// Merged    |a-a-a-a|c|   |b-b-b|d-d-d|
///
/// Adjacent or overlapping extent deletions in two adjacent layers can be merged into single
/// records (since they do not have a physical offset, so there's no need to keep the physical
/// extents contiguous). We can't merge deletions from non-adjacent layers, since that would
/// cause issues in situations like this:
///
/// Layer 0         |X-X-X|
/// Layer 1   |a-a-a-a-a-a|
/// Layer 2   |X-X-X|
///
/// Merging the two deletions in layers 0 and 2 would either result in the middle extent being
/// fully occluded or not at all (depending on whether we replaced on the left or right layer).
///
/// TODO(jfsulliv): At the base layer, we should prune deleted extents completely.
Merge function for items in the object store.
The most interesting behaviour in this merge function is how extents are handled. Since extents
can overlap and replace one another, the merge function generally builds up the most
recent view of the extents in the tree, so that the output of a full merge contains no
overlapping extents. You can imagine looking down at the extents from the top-most layer.

A brief example.





Adjacent or overlapping extent deletions in two adjacent layers can be merged into single
records (since they do not have a physical offset, so there's no need to keep the physical
extents contiguous). We can't merge deletions from non-adjacent layers, since that would
cause issues in situations like this.



Merging the two deletions in layers 0 and 2 would either result in the middle extent being
fully occluded or not at all (depending on whether we replaced on the left or right layer).

At the base layer, we should prune deleted extents completely.
Merge function for items in the object store . The most interesting behaviour in this merge function is how extents are handled . Since extents can overlap and replace one another the merge function generally builds up the most recent view of the extents in the tree so that the output of a full merge contains no overlapping extents . You can imagine looking down at the extents from the top - most layer . A brief example . Adjacent or overlapping extent deletions in two adjacent layers can be merged into single records ( since they do not have a physical offset so there ' s no need to keep the physical extents contiguous ) . We can ' t merge deletions from non - adjacent layers since that would cause issues in situations like this . Merging the two deletions in layers 0 and 2 would either result in the middle extent being fully occluded or not at all ( depending on whether we replaced on the left or right layer ) . At the base layer we should prune deleted extents completely .
pub fn merge(
    left: &MergeLayerIterator<'_, ObjectKey, ObjectValue>,
    right: &MergeLayerIterator<'_, ObjectKey, ObjectValue>,
) -> MergeResult<ObjectKey, ObjectValue> {
    if left.key().object_id != right.key().object_id {
        return MergeResult::EmitLeft;
    }
    match (left.key(), right.key(), left.value(), right.value()) {
        (
            ObjectKey {
                object_id,
                data: ObjectKeyData::Attribute(left_attr_id, AttributeKey::Extent(left_extent_key)),
            },
            ObjectKey {
                object_id: _,
                data:
                    ObjectKeyData::Attribute(right_attr_id, AttributeKey::Extent(right_extent_key)),
            },
            ObjectValue::Extent(left_extent),
            ObjectValue::Extent(right_extent),
        ) if left_attr_id == right_attr_id => {
            if let (None, None) = (left_extent.device_offset, right_extent.device_offset) {
                if (left.layer_index as i32 - right.layer_index as i32).abs() == 1 {
                    // Two deletions in adjacent layers can be merged.
                    return merge_deleted_extents(
                        *object_id,
                        *left_attr_id,
                        left_extent_key,
                        right_extent_key,
                    );
                }
            }
            return merge_extents(
                *object_id,
                *left_attr_id,
                left.layer_index,
                right.layer_index,
                left_extent_key,
                right_extent_key,
                left_extent,
                right_extent,
            );
        }
        (ObjectKey { data: ObjectKeyData::Tombstone, .. }, _, _, _) => {
            MergeResult::Other { emit: None, left: Keep, right: Discard }
        }
        (left_key, right_key, _, _) if left_key == right_key => {
            MergeResult::Other { emit: None, left: Keep, right: Discard }
        }
        _ => MergeResult::EmitLeft,
    }
}
pub fn merge ( left : & MergeLayerIterator < ' _ , ObjectKey , ObjectValue > , right : & MergeLayerIterator < ' _ , ObjectKey , ObjectValue > , ) -> MergeResult < ObjectKey , ObjectValue > { if left . key ( ) . object_id != right . key ( ) . object_id { return MergeResult :: EmitLeft ; } match ( left . key ( ) , right . key ( ) , left . value ( ) , right . value ( ) ) { ( ObjectKey { object_id , data : ObjectKeyData :: Attribute ( left_attr_id , AttributeKey :: Extent ( left_extent_key ) ) , } , ObjectKey { object_id : _ , data : ObjectKeyData :: Attribute ( right_attr_id , AttributeKey :: Extent ( right_extent_key ) ) , } , ObjectValue :: Extent ( left_extent ) , ObjectValue :: Extent ( right_extent ) , ) if left_attr_id == right_attr_id => { if let ( None , None ) = ( left_extent . device_offset , right_extent . device_offset ) { if ( left . layer_index as i32 - right . layer_index as i32 ) . abs ( ) == 1 { // Two deletions in adjacent layers can be merged. return merge_deleted_extents ( * object_id , * left_attr_id , left_extent_key , right_extent_key , ) ; } } return merge_extents ( * object_id , * left_attr_id , left . layer_index , right . layer_index , left_extent_key , right_extent_key , left_extent , right_extent , ) ; } ( ObjectKey { data : ObjectKeyData :: Tombstone , .. } , _ , _ , _ ) => { MergeResult :: Other { emit : None , left : Keep , right : Discard } } ( left_key , right_key , _ , _ ) if left_key == right_key => { MergeResult :: Other { emit : None , left : Keep , right : Discard } } _ => MergeResult :: EmitLeft , } }
Merge function for items in the object store.
Merge function for items in the object store .
left
&MergeLayerIterator<'_, ObjectKey, ObjectValue>
right
&MergeLayerIterator<'_, ObjectKey, ObjectValue>