Struct DisplacedTable 

pub struct DisplacedTable { /* private fields */ }

A special table backed by a union-find used to efficiently implement egglog-style canonicaliztion.

To canonicalize columns, we need to efficiently discover values that have ceased to be canonical. To do that we keep a table of displaced values:

This table has three columns:

1. (the only key): a value that is no longer canonical in the equivalence relation.
2. The canonical value of the equivalence class.
3. The timestamp at which the key stopped being canonical.

We do not store the second value explicitly: instead, we compute it on-the-fly using a union-find data-structure.

This is related to the ‘Leader’ encoding in some versions of egglog: Displaced is a version of Leader that only stores ids when they cease to be canonical. Rows are also “automatically updated” with the current leader, rather than requiring the DB to replay history or canonicalize redundant values in the table.

To union new ids l, and r, stage an update Displaced(l, r, ts) where ts is the current timestamp. Note that all tie-breaks and other encoding decisions are made internally, so there may not literally be a row added with this value.

Implementations

impl DisplacedTable

pub fn underlying_uf(&self) -> &UnionFind<Value>

Trait Implementations

impl Clone for DisplacedTable

fn clone(&self) -> Self

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Default for DisplacedTable

fn default() -> Self

Returns the “default value” for a type.

impl Table for DisplacedTable

fn dyn_clone(&self) -> Box<dyn Table>

A variant of clone that returns a boxed trait object; this trait object must contain all of the data associated with the current table.

fn as_any(&self) -> &dyn Any

A boilerplate method to make it easier to downcast values of Table.

fn spec(&self) -> TableSpec

The schema of the table.

fn rebuilder<'a>(&'a self, cols: &[ColumnId]) -> Option<Box<dyn Rebuilder + 'a>>

If this table can perform a table-level rebuild, construct a Rebuilder for it.

fn clear(&mut self)

Clear all table contents. If the table is nonempty, this will change the generation of the table. This method also clears any pending data.

fn all(&self) -> Subset

Get a subset corresponding to all rows in the table.

fn len(&self) -> usize

Get the length of the table.

fn version(&self) -> TableVersion

Get the current version for the table. RowIds and Subsets are only valid for a given major generation.

fn updates_since(&self, offset: Offset) -> Subset

Get the subset of the table that has appeared since the last offset.

fn scan_generic_bounded( &self, subset: SubsetRef<'_>, start: Offset, n: usize, cs: &[Constraint], f: impl FnMut(RowId, &[Value]), ) -> Option<Offset>

where Self: Sized,

Iterate over the given subset of the table, starting at an opaque start token, ending after up to n rows, returning the next start token if more rows remain. Only invoke f on rows that match the given constraints.

fn refine_one(&self, subset: Subset, c: &Constraint) -> Subset

Filter a given subset of the table for the rows matching the single constraint.

fn fast_subset(&self, constraint: &Constraint) -> Option<Subset>

An optional method for quickly generating a subset from a constraint. The standard use-case here is to apply constraints based on a column that is known to be sorted.

fn get_row(&self, key: &[Value]) -> Option<Row>

Look up a single row by the given key values, if it is in the table.

fn get_row_column(&self, key: &[Value], col: ColumnId) -> Option<Value>

Look up the given column of single row by the given key values, if it is in the table.

fn new_buffer(&self) -> Box<dyn MutationBuffer>

Create a new buffer for staging mutations on this table.

fn merge(&mut self, _: &mut ExecutionState<'_>) -> TableChange

Merge any updates to the table, and potentially update the generation for the table.

fn apply_rebuild( &mut self, _table_id: TableId, _table: &WrappedTable, _next_ts: Value, _exec_state: &mut ExecutionState<'_>, )

Rebuild the table according to the given Rebuilder implemented by table, if there is one. Applying a rebuild can cause more mutations to be buffered, which can in turn be flushed by a call to Table::merge.

fn is_empty(&self) -> bool

Check if the table is empty.

fn scan_generic(&self, subset: SubsetRef<'_>, f: impl FnMut(RowId, &[Value]))

where Self: Sized,

Iterate over the given subset of the table.

fn refine_live(&self, subset: Subset) -> Subset

Filter a given subset of the table for the rows that are live

fn refine(&self, subset: Subset, cs: &[Constraint]) -> Subset

Filter a given subset of the table for the rows matching the given constraints.

fn split_fast_slow( &self, cs: &[Constraint], ) -> (Subset, Pooled<Vec<Constraint>>, Pooled<Vec<Constraint>>)

A helper routine that leverages the existing fast_subset method to preprocess a set of constraints into “fast” and “slow” ones, returning the subet of indexes that match the fast one.