Skip to content

Remap Oracle API

RemapOracle

Bases: NamedTuple

An oracle that answers where an index has moved during a bulk edit.

Because swap-and-pop edits move row indices, references (like foreign keys) need to be remapped to their new physical locations. This oracle provides the mapping rules for a specific table during a transaction commit.

Attributes:

Name Type Description
set_null_unlinks_sorted ndarray

Sorted array of indices that should be set to null.
deletions_sorted ndarray

Sorted array of deleted row indices.
moves_from ndarray

Sorted array of original row indices that were relocated.
moves_to ndarray

The new physical indices corresponding to moves_from.
moves_to_sorted ndarray

A sorted version of moves_to for fast collision checks.
addition_destinations ndarray

Array of indices where new staged rows were placed.
staged_indices_start int

The index where staged (newly added) rows begin.
new_size int

The total physical size of the table after the edit.
missing_index_sentinel int

The integer sentinel representing a missing link.
Source code in src/packed_data_structures/remap_oracle.py 
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class RemapOracle(NamedTuple):
    """An oracle that answers where an index has moved during a bulk edit.

    Because swap-and-pop edits move row indices, references (like foreign keys)
    need to be remapped to their new physical locations. This oracle provides
    the mapping rules for a specific table during a transaction commit.

    Attributes:
        set_null_unlinks_sorted (np.ndarray): Sorted array of indices that should be set to null.
        deletions_sorted (np.ndarray): Sorted array of deleted row indices.
        moves_from (np.ndarray): Sorted array of original row indices that were relocated.
        moves_to (np.ndarray): The new physical indices corresponding to `moves_from`.
        moves_to_sorted (np.ndarray): A sorted version of `moves_to` for fast collision checks.
        addition_destinations (np.ndarray): Array of indices where new staged rows were placed.
        staged_indices_start (int): The index where staged (newly added) rows begin.
        new_size (int): The total physical size of the table after the edit.
        missing_index_sentinel (int): The integer sentinel representing a missing link.
    """

    set_null_unlinks_sorted: np.ndarray
    deletions_sorted: np.ndarray
    moves_from: np.ndarray
    moves_to: np.ndarray
    moves_to_sorted: np.ndarray
    addition_destinations: np.ndarray
    staged_indices_start: int
    new_size: int
    missing_index_sentinel: int

oracle_resolve 

oracle_resolve(idx: int, oracle: RemapOracle) -> int

Translates a single index through a RemapOracle.

This resolves
  • staged indices (newly added entries)
  • moved indices (swap-and-pop relocations)
  • overwritten indices
  • explicit deletions

Parameters:

Name Type Description Default
idx int

The original index to resolve.

 required
oracle RemapOracle

The oracle containing mapping rules.

 required

Returns:

Name Type Description
int int

The final physical index, or the missing sentinel if deleted/voided.
Source code in src/packed_data_structures/remap_oracle.py 
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
@nb.njit(inline="always")
def oracle_resolve(idx: int, oracle: RemapOracle) -> int:
    """Translates a single index through a RemapOracle.

    This resolves:
      - staged indices (newly added entries)
      - moved indices (swap-and-pop relocations)
      - overwritten indices
      - explicit deletions

    Args:
        idx (int): The original index to resolve.
        oracle (RemapOracle): The oracle containing mapping rules.

    Returns:
        int: The final physical index, or the missing sentinel if deleted/voided.
    """
    o = oracle
    missing_idx = o.missing_index_sentinel

    # Staged IDs (New Additions)
    if idx >= o.staged_indices_start:
        offset = idx - o.staged_indices_start
        if offset < len(o.addition_destinations):
            return int(o.addition_destinations[offset])
        return missing_idx

    # Explicit Deletions
    if len(o.deletions_sorted) > 0:
        # Optimization: fast range check before binary search
        if o.deletions_sorted[0] <= idx <= o.deletions_sorted[-1]:
            i_del = np.searchsorted(o.deletions_sorted, idx)
            if i_del < len(o.deletions_sorted) and o.deletions_sorted[i_del] == idx:
                return missing_idx

    # Moves (Did I move?)
    if len(o.moves_from) > 0:
        if o.moves_from[0] <= idx <= o.moves_from[-1]:
            i_move = np.searchsorted(o.moves_from, idx)
            if i_move < len(o.moves_from) and o.moves_from[i_move] == idx:
                return int(o.moves_to[i_move])

    if _ENABLE_DEFENSIVE_CHECKS:  # pragma: no cover
        # Overwritten by Move (Did someone move here?)
        if len(o.moves_to_sorted) > 0:
            if o.moves_to_sorted[0] <= idx <= o.moves_to_sorted[-1]:
                i_over = np.searchsorted(o.moves_to_sorted, idx)
                if i_over < len(o.moves_to_sorted) and o.moves_to_sorted[i_over] == idx:
                    return missing_idx

        # Overwritten by Addition (Did an addition land here?)
        if len(o.addition_destinations) > 0:
            if o.addition_destinations[0] <= idx <= o.addition_destinations[-1]:
                i_add = np.searchsorted(o.addition_destinations, idx)
                if (
                    i_add < len(o.addition_destinations)
                    and o.addition_destinations[i_add] == idx
                ):
                    return missing_idx

        # Truncation (Array shrunk)
        if idx >= o.new_size:
            return missing_idx

    return idx

oracle_resolve_array 

oracle_resolve_array(
    values: ndarray,
    oracle: RemapOracle,
    inplace: bool = False,
) -> np.ndarray

Translate a list of indices through a RemapOracle.

Parameters:

Name Type Description Default
values ndarray

Array of indices referencing the oracle's table.

 required
oracle RemapOracle

RemapOracle for the referenced table.

 required
inplace bool

Preform the update in-place on the provided values array.

 False

Returns:

Type Description
ndarray

np.ndarray: Array with all indices translated to final physical indices.
Source code in src/packed_data_structures/remap_oracle.py 
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
@nb.njit(cache=True, parallel=True)
def oracle_resolve_array(
    values: np.ndarray,
    oracle: RemapOracle,
    inplace: bool = False,
) -> np.ndarray:
    """Translate a list of indices through a RemapOracle.

    Args:
        values (np.ndarray): Array of indices referencing the oracle's table.
        oracle (RemapOracle): RemapOracle for the referenced table.
        inplace (bool): Preform the update in-place on the provided values array.

    Returns:
        np.ndarray: Array with all indices translated to final physical indices.
    """
    if not inplace:
        out = np.zeros_like(values)
    else:
        out = values

    missing = oracle.missing_index_sentinel

    for i in nb.prange(len(values)):  # ty:ignore[not-iterable]
        v = values[i]
        if v == missing:
            out[i] = missing
        else:
            out[i] = oracle_resolve(v, oracle)

    return out