Semantics of Table Scan

A “scan” retrieves all fresh records from a Spiral Table satisfying user-specified conditions. A fresh record is one whose cells are also fresh. A cell contains a value for a particular column and key at a particular time. A cell is fresh if it is the latest cell for its column and key. In the negative: there does not exist a cell for the same column and key with a newer (larger) time. We use the term record to refer to the values for each column at a particular key. In the relational model, this would be called a row.

While we may logically think of a Spiral table as a collection of cells, the most recent of which define the table’s records, a table is physically comprised of fragments. Fragments, which are also described in the Spiral Table format document, contain a series of records whose columns are a subset of the column group schema. In particular, while all records in a fragment have the same schema, that schema may lack all but one of a column group’s columns. As a consequence, assembling the fresh record for a given key may require reading every fragment containing that key, even very old ones. The fresh record is then assembled by selecting the newest cell for each column of the given key.

We sometimes conceive of a Spiral table as a collection of cells in a three-dimensional space with the axes: keys, columns, and time. For any particular key, time, and column, there is at most one cell. The state of the table at some time, t, is defined by “projecting” all cells at time t or earlier onto time t. You may also think of each cell casting a shadow towards the plane at time t, obscures any earlier cell with the same key and column. After projecting, a table might still have gaps. Those gaps are filled in with the null value. This is the reason why every Spiral column is nullable.

Key Filtration

A scan may have a user-specified key predicate. Keys not matching that predicate are not included in the scan. In the three-dimensional analogy, a key predicate eliminates an entire column-by-time plane of cells whose keys fail the predicate.

Column Filtration

A scan may specify a non-empty set of columns to include. In the three-dimensional analogy, this excludes the entire key-by-time plane of cells for each column.

Time Filtration

A scan may specify an interval of time to include. This is an advanced feature whose use complicates the idea of a “fresh” record. In particular, time filtration limits which cells are considered when assembling fresh records. A cell is fresh within a time interval if there is no newer cell for the same key and column within that interval. Notice that in addition to hiding more recent updates, this can cause entire keys to not exist by hiding cells whose time is before the interval.

Value Filtration

Unlike the three previous filters, value filtration is defined in terms of the fresh records of a table. In the three-dimensional analogy, it is defined in terms of the table after “projecting” the cells: eliminating any non-fresh cells and filling in missing cells with nulls.

Value filtration excludes keys based on the values of the key’s cells. For example, consider a table with key key, columns a and b, and these fresh records:

The value filter a >= b excludes the second record:

Value filtration operates on the table after projection: that is, once all fresh records are assembled and missing values are filled with null. This ensures the filter is applied to the most up-to-date and complete view of each row. Applying the filter directly to cells—rather than to the projected records—can lead to incorrect results, as it may inadvertently resurrect stale values. Consider scanning the following table with the value filter a < 10:

The table:

The fresh records:

The value-filtered fresh records:

In contrast, directly applying the value filter a < 10 to the cells yields these cells:

Whose fresh records are not the same! Notice that a stale cell for key three and column a has become fresh: