Package io.deephaven.engine.table.impl.sources.regioned

Interface RegionedColumnSource<DATA_TYPE>

All Superinterfaces:
ChunkSource<Values>, ChunkSource.WithPrev<Values>, ColumnSource<DATA_TYPE>, DeferredGroupingColumnSource<DATA_TYPE>, ElementSource<DATA_TYPE>, FillContextMaker, GetContextMaker, ImmutableColumnSource<DATA_TYPE>, Releasable, TupleExporter<DATA_TYPE>, TupleSource<DATA_TYPE>
@VisibleForTesting public interface RegionedColumnSource<DATA_TYPE> extends DeferredGroupingColumnSource<DATA_TYPE>, ImmutableColumnSource<DATA_TYPE>

Regioned column source interface.

source tables can be thought of a tree of partitions with table locations at the leaf nodes. When building the RowSet for such a table, we statically partition the available element address space from [0, 9223372036854775807L (2^63-1)].

We constrain the size at these leaf nodes in order to support a partitioning of the element address space into region index and sub-region row index. In order to make the calculations as inexpensive as possible, this is done by assigning some bits of each row key (element address) to the region index, and the remaining bits to the sub-region row index.

This type of address space allocation allows very cheap O(1) element access. Denser alternatives tend to introduce more complication and/or O(log n) lookups.

Currently, region indices use 20 and region offsets use 43, allowing tables to consist of 1048576 locations with 8796093022208L each.

  • Field Details

    • REGION_INDEX_ADDRESS_BITS

      static final int REGION_INDEX_ADDRESS_BITS
      Address bits allocated to the region index.
      See Also:

    • SUB_REGION_ROW_INDEX_ADDRESS_BITS

      static final int SUB_REGION_ROW_INDEX_ADDRESS_BITS
      Address bits allocated to the sub-region row index.

      Note that we do not use the sign bit, as negative row keys are not permitted (or used to signify the null key).

      See Also:

    • MAXIMUM_REGION_COUNT

      static final int MAXIMUM_REGION_COUNT
      The maximum number of regions that may be addressed.
      See Also:

    • REGION_CAPACITY_IN_ELEMENTS

      static final long REGION_CAPACITY_IN_ELEMENTS
      The size used for *all* regions.
      See Also:

    • ROW_KEY_TO_SUB_REGION_ROW_INDEX_MASK

      static final long ROW_KEY_TO_SUB_REGION_ROW_INDEX_MASK
      The mask for converting from a row key to a sub-region row index.
      See Also:

  • Method Details

    • getFirstRowKey

      static long getFirstRowKey(int regionIndex)
      Get the first element row key for a region index.
      Returns:
      The first element row key for a region index

    • getLastRowKey

      static long getLastRowKey(int regionIndex)
      Get the last element row key for a region index.
      Returns:
      The last element row key for a region index

    • getRowKey

      static long getRowKey(int regionIndex, long regionOffset)
      Get the element row key implied by a region index and a region offset.
      Returns:
      The element row key for a particular region offset of a region index

    • addRegion

      int addRegion(@NotNull @NotNull ColumnDefinition<?> columnDefinition, @NotNull @NotNull ColumnLocation columnLocation)

      Add a region to this regioned column source.

      Elements in this region are ordered after elements in other regions added previously.

      Parameters:
      columnDefinition - The column definition for this column source (potentially varies by region)
      columnLocation - The column location for the region being added
      Returns:
      The index assigned to the added region

    • invalidateRegion

      void invalidateRegion(int regionIndex)
      Invalidate the specified region. An invalidated region will throw an exception on any read attempt if it cannot be completed consistently and correctly.
      Parameters:
      regionIndex - the region to invalidate