Struct Table

pub struct Table {
    pub indexes: BTreeMap<IndexId, TableIndex>,
    pub schema: Arc<TableSchema>,
    pub row_count: u64,
    /* private fields */
}

A database table containing the row schema, the rows, and indices.

The table stores the rows into a page manager and uses an internal map to ensure that no identical row is stored more than once.

Fields

indexes: BTreeMap<IndexId, TableIndex>

The indices associated with a set of columns of the table.

schema: Arc<TableSchema>

The schema of the table, from which the type, and other details are derived.

row_count: u64

Stores number of rows present in table.

Implementations

impl Table

pub fn new(schema: Arc<TableSchema>, squashed_offset: SquashedOffset) -> Self

Creates a new empty table with the given schema and squashed_offset.

pub fn is_scheduler(&self) -> bool

Returns whether this is a scheduler table.

pub unsafe fn check_unique_constraints<'a, I: Iterator<Item = (&'a IndexId, &'a TableIndex)>>( &'a self, row: RowRef<'_>, adapt: impl FnOnce(Iter<'a, IndexId, TableIndex>) -> I, is_deleted: impl FnMut(RowPointer) -> bool, ) -> Result<(), UniqueConstraintViolation>

Check if the row conflicts with any unique index on self, and if there is a conflict, return Err.

is_deleted is a predicate which, for a given row pointer, returns true if and only if that row should be ignored. While checking unique constraints against the committed state, MutTxId::insert will ignore rows which are listed in the delete table.

Safety

row.row_layout() == self.row_layout() must hold.

pub fn insert<'a>( &'a mut self, pool: &PagePool, blob_store: &'a mut dyn BlobStore, row: &ProductValue, ) -> Result<(Option<RowHash>, RowRef<'a>), InsertError>

Insert a row into this table, storing its large var-len members in the blob_store.

On success, returns the hash, if any, of the newly-inserted row, and a RowRef referring to the row.s The hash is only computed if this table has a PointerMap, i.e., does not have any unique indexes. If the table has unique indexes, the returned Option<RowHash> will be None.

When a row equal to row already exists in self, returns InsertError::Duplicate(existing_row_pointer), where existing_row_pointer is a RowPointer which identifies the existing row. In this case, the duplicate is not inserted, but internal data structures may be altered in ways that affect performance and fragmentation.

TODO(error-handling): describe errors from write_row_to_pages and return meaningful errors.

pub fn insert_physically_pv<'a>( &'a mut self, pool: &PagePool, blob_store: &'a mut dyn BlobStore, row: &ProductValue, ) -> Result<(RowRef<'a>, BlobNumBytes), Error>

Physically inserts row into the page without inserting it logically into the pointer map.

This is useful when we need to insert a row temporarily to get back a RowPointer. A call to this method should be followed by a call to [delete_internal_skip_pointer_map].

pub fn insert_physically_bsatn<'a>( &'a mut self, pool: &PagePool, blob_store: &'a mut dyn BlobStore, row: &[u8], ) -> Result<(RowRef<'a>, BlobNumBytes), Error>

Physically insert a row, encoded in BSATN, into this table, storing its large var-len members in the blob_store.

On success, returns the hash of the newly-inserted row, and a RowRef referring to the row.

This does not check for set semantic or unique constraints.

This is also useful when we need to insert a row temporarily to get back a RowPointer. In this case, A call to this method should be followed by a call to [delete_internal_skip_pointer_map].

When row is not valid BSATN at the table’s row type, an error is returned and there will be nothing for the caller to revert.

pub unsafe fn sequence_triggers_for<'a>( &'a self, blob_store: &'a dyn BlobStore, row: RowPointer, ) -> (ColList, SeqIdList)

Returns all the columns with sequences that need generation for this row.

Safety

self.is_row_present(row) must hold.

pub unsafe fn write_gen_val_to_col( &mut self, col_id: ColId, ptr: RowPointer, seq_val: i128, )

Writes seq_val to the column at col_id in the row identified by ptr.

Truncates the seq_val to fit the type of the column.

Safety

• self.is_row_present(row) must hold.
• col_id must be a valid column, with a primitive integer type, of the row type.

pub unsafe fn confirm_insertion<'a, const CHECK_SAME_ROW: bool>( &'a mut self, blob_store: &'a mut dyn BlobStore, ptr: RowPointer, blob_bytes: BlobNumBytes, ) -> Result<(Option<RowHash>, RowPointer), InsertError>

Performs all the checks necessary after having fully decided on a rows contents.

This includes inserting the row into any applicable indices and/or the pointer map.

On Ok(_), statistics of the table are also updated, and the ptr still points to a valid row, and otherwise not.

If CHECK_SAME_ROW holds, an identical row will be treated as a set-semantic duplicate. Otherwise, it will be treated as a unique constraint violation. However, false should only be passed if it’s known beforehand that there is no identical row.

Safety

self.is_row_present(row) must hold.

pub unsafe fn confirm_update<'a>( &'a mut self, blob_store: &'a mut dyn BlobStore, new_ptr: RowPointer, old_ptr: RowPointer, blob_bytes_added: BlobNumBytes, ) -> Result<RowPointer, InsertError>

Confirms a row update, after first updating indices and checking constraints.

On Ok(_):

• the statistics of the table are also updated,
• the ptr still points to a valid row.

Otherwise, on Err(_):

• ptr will not point to a valid row,
• the statistics won’t be updated.

Safety

self.is_row_present(new_row) and self.is_row_present(old_row) must hold.

pub unsafe fn find_same_row_via_pointer_map( target_table: &Table, needle_table: &Table, needle_bs: &dyn BlobStore, needle_ptr: RowPointer, row_hash: Option<RowHash>, ) -> (RowHash, Option<RowPointer>)

Using the PointerMap, searches target_table for a row equal to needle_table[needle_ptr].

Rows are compared for equality by eq_row_in_page.

Lazily computes the row hash if needed and returns it, or uses the one provided, if any.

Used for detecting set-semantic duplicates when inserting into tables without any unique constraints.

Does nothing and always returns None if target_table does not have a PointerMap, in which case the caller should instead use Self::find_same_row_via_unique_index.

Note that we don’t need the blob store to compute equality, as content-addressing means it’s sufficient to compare the hashes of large blobs. (If we see a collision in BlobHash we have bigger problems.)

Safety

• target_table and needle_table must have the same row_layout.
• needle_table.is_row_present(needle_ptr).

pub unsafe fn eq_row_in_page( target_table: &Table, target_ptr: RowPointer, needle_table: &Table, needle_ptr: RowPointer, ) -> bool

Returns whether the row target_ptr in target_table is exactly equal to the row needle_ptr in needle_ptr.

Safety

• target_table and needle_table must have the same row_layout.
• target_table.is_row_present(target_ptr).
• needle_table.is_row_present(needle_ptr).

pub unsafe fn find_same_row( target_table: &Table, needle_table: &Table, needle_bs: &dyn BlobStore, needle_ptr: RowPointer, row_hash: Option<RowHash>, ) -> (Option<RowHash>, Option<RowPointer>)

Searches target_table for a row equal to needle_table[needle_ptr], and returns the RowPointer to that row in target_table, if it exists.

Searches using the PointerMap or a unique index, as appropriate for the table.

Lazily computes the row hash if needed and returns it, or uses the one provided, if any.

Safety

• target_table and needle_table must have the same row_layout.
• needle_table.is_row_present(needle_ptr) must hold.

pub fn get_row_ref<'a>( &'a self, blob_store: &'a dyn BlobStore, ptr: RowPointer, ) -> Option<RowRef<'a>>

Returns a RowRef for ptr or None if the row isn’t present.

pub unsafe fn get_row_ref_unchecked<'a>( &'a self, blob_store: &'a dyn BlobStore, ptr: RowPointer, ) -> RowRef<'a>

Assumes ptr is a present row in self and returns a RowRef to it.

Safety

The requirement is that self.is_row_present(ptr) must hold. That is, ptr must refer to a row within self which was previously inserted and has not been deleted since.

This means:

• The PageIndex of ptr must be in-bounds for self.pages.
• The PageOffset of ptr must be properly aligned for the row type of self, and must refer to a valid, live row in that page.
• The SquashedOffset of ptr must match self.squashed_offset.

Showing that ptr was the result of a call to [Table::insert(table, ..)] and has not been passed to [Table::delete(table, ..)] is sufficient to demonstrate all of these properties.

pub unsafe fn delete_internal_skip_pointer_map( &mut self, blob_store: &mut dyn BlobStore, ptr: RowPointer, ) -> BlobNumBytes

Deletes a row in the page manager without deleting it logically in the pointer map.

Safety

ptr must point to a valid, live row in this table.

pub fn delete<'a, R>( &'a mut self, blob_store: &'a mut dyn BlobStore, ptr: RowPointer, before: impl for<'b> FnOnce(RowRef<'b>) -> R, ) -> Option<R>

Deletes the row identified by ptr from the table.

The function before is run on the to-be-deleted row, if it is present, before deleting. This enables callers to extract the deleted row. E.g. applying deletes when squashing/merging a transaction into the committed state passes |row| row.to_product_value() as before so that the resulting ProductValues can be passed to the subscription evaluator.

pub fn delete_equal_row( &mut self, pool: &PagePool, blob_store: &mut dyn BlobStore, row: &ProductValue, ) -> Result<Option<RowPointer>, Error>

If a row exists in self which matches row by Table::find_same_row, delete that row.

If a matching row was found, returns the pointer to that row. The returned pointer is now invalid, as the row to which it referred has been deleted.

This operation works by temporarily inserting the row into self, checking find_same_row on the newly-inserted row, deleting the matching row if it exists, then deleting the temporary insertion.

pub fn get_row_type(&self) -> &ProductType

Returns the row type for rows in this table.

pub fn get_schema(&self) -> &Arc<TableSchema>

Returns the schema for this table.

pub fn with_mut_schema<R>( &mut self, with: impl FnOnce(&mut TableSchema) -> R, ) -> R

Runs a mutation on the TableSchema of this table.

This uses a clone-on-write mechanism. If none but self refers to the schema, then the mutation will be in-place. Otherwise, the schema must be cloned, mutated, and then the cloned version is written back to the table.

pub fn new_index( &self, algo: &IndexAlgorithm, is_unique: bool, ) -> Result<TableIndex, InvalidFieldError>

Returns a new TableIndex for table.

pub unsafe fn insert_index( &mut self, blob_store: &dyn BlobStore, index_id: IndexId, index: TableIndex, )

Inserts a new index into the table.

The index will be populated using the rows of the table.

Panics

Panics if any row would violate index’s unique constraint, if it has one.

Safety

Caller must promise that index was constructed with the same row type/layout as this table.

pub unsafe fn add_index( &mut self, index_id: IndexId, index: TableIndex, ) -> Option<PointerMap>

Adds an index to the table without populating.

Safety

Caller must promise that index was constructed with the same row type/layout as this table.

pub fn delete_index( &mut self, blob_store: &dyn BlobStore, index_id: IndexId, pointer_map: Option<PointerMap>, ) -> Option<(TableIndex, IndexSchema)>

Removes an index from the table.

Returns whether an index existed with index_id.

pub fn scan_rows<'a>( &'a self, blob_store: &'a dyn BlobStore, ) -> TableScanIter<'a>

Returns an iterator over all the rows of self, yielded as [RefRef]s.

pub fn get_index_by_id_with_table<'a>( &'a self, blob_store: &'a dyn BlobStore, index_id: IndexId, ) -> Option<TableAndIndex<'a>>

Returns this table combined with the index for IndexId, if any.

pub fn get_index_by_id(&self, index_id: IndexId) -> Option<&TableIndex>

Returns the TableIndex for this IndexId.

pub fn get_index_by_cols_with_table<'a>( &'a self, blob_store: &'a dyn BlobStore, cols: &ColList, ) -> Option<TableAndIndex<'a>>

Returns this table combined with the first index with cols, if any.

pub fn get_index_by_cols( &self, cols: &ColList, ) -> Option<(IndexId, &TableIndex)>

Returns the first TableIndex with the given ColList.

pub fn clone_structure(&self, squashed_offset: SquashedOffset) -> Self

Clones the structure of this table into a new one with the same schema, visitor program, and indices. The new table will be completely empty and will use the given squashed_offset instead of that of self.

pub fn bytes_occupied_overestimate(&self) -> usize

Returns the number of bytes occupied by the pages and the blob store. Note that result can be more than the actual physical size occupied by the table because the blob store implementation can do internal optimizations. For more details, refer to the documentation of self.blob_store_bytes.

pub unsafe fn set_pages( &mut self, pages: Vec<Box<Page>>, blob_store: &dyn BlobStore, )

Reset the internal storage of self to be pages.

This recomputes the pointer map based on the pages, but does not recompute indexes.

Used when restoring from a snapshot.

Safety

The schema of rows stored in the pages must exactly match self.schema and self.inner.row_layout.

pub fn consume_for_merge( self, ) -> (Arc<TableSchema>, impl Iterator<Item = (IndexId, TableIndex)>, impl Iterator<Item = Box<Page>>)

Consumes the table, returning some constituents needed for merge.

pub fn num_rows(&self) -> u64

Returns the number of rows resident in this table.

This method runs in constant time.

pub fn bytes_used_by_rows(&self) -> u64

Returns the number of bytes used by rows resident in this table.

This includes data bytes, padding bytes and some overhead bytes, as described in the docs for Page::bytes_used_by_rows, but does not include:

• Unallocated space within pages.
• Per-page overhead (e.g. page headers).
• Table overhead (e.g. the RowTypeLayout, PointerMap, [Schema] &c).
• Indexes.
• Large blobs in the BlobStore.

Of these, the caller should inspect the blob store in order to account for memory usage by large blobs, and call Self::bytes_used_by_index_keys to account for indexes, but we intend to eat all the other overheads when billing.

pub fn num_indices(&self) -> usize

Returns the number of indices in this table.

pub fn num_rows_in_indexes(&self) -> u64

Returns the number of rows (or RowPointers, more accurately) stored in indexes by this table.

This method runs in constant time.

pub fn bytes_used_by_index_keys(&self) -> u64

Returns the number of bytes used by keys stored in indexes by this table.

This method scales in runtime with the number of indexes in the table, but not with the number of pages or rows.

Key size is measured using a metric called “key size” or “data size,” which is intended to capture the number of live user-supplied bytes, not including representational overhead. This is distinct from the BFLATN size measured by Self::bytes_used_by_rows. See the trait [crate::btree_index::KeySize] for specifics on the metric measured.

impl Table

pub fn build_error_unique( &self, index: &TableIndex, index_id: IndexId, value: AlgebraicValue, ) -> UniqueConstraintViolation

Returns a unique constraint violation error for the given index and the value that would have been duplicated.

pub fn row_size(&self) -> Size

Returns the row size for a row in the table.

pub fn iter_pages_with_hashes(&mut self) -> impl Iterator<Item = (Hash, &Page)>

Iterates over each Page in this table, ensuring that its hash is computed before yielding it.

Used when capturing a snapshot.

Trait Implementations

impl Debug for Table

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl MemoryUsage for Table

fn heap_usage(&self) -> usize

The heap memory usage of this type. The default implementation returns 0.

impl PartialEq for Table

fn eq(&self, other: &Table) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Eq for Table

impl StructuralPartialEq for Table