Clarify the design and usage of row id and row address

[niebayes]

I've read the blog post on Move-Stable Row IDs, but I'm still a bit unclear about the design and semantics of row id and row address. I've also noticed that these concepts seem to be messed up in the codebase.

Could we clarify the intended design of row id vs row address, particularly in the following areas:

1. Are row ids or row addresses stored in the fragment files?
2. Are row ids or row addresses stored in the index files?
3. How is the row id index updated when there's a row update or a compaction?
4. What is the expected procedure for performing a Take operation using row id / row address?
5. How the design relates to the lance file format?
6. Does this design also fit other file format, like parquet?

[niebayes]

Very appreciate someone could help me resolve these questions

[wjones127]

Row addresses have a simple definition: They are a location of a row, determined by the formula fragment_id << 32 + offset_in_fragment.

Row ids are unique identifiers for the rows. But how they are generated depends on the configuration of the dataset. There's three styles:

1. Address-style - The row ids are just row addresses. This means that row ids aren't stable when data is moved (or updated).
2. Move-stable - The row ids are auto-incrementing u64 ids, which are saved in the dataset. This is described in the Move-stable row id docs. They are stable when moved, but not when updated.
3. Primary keys (planned) - The row ids are similar to move-stable, but also stable after updates. This is discussed here: Stable Row ID #3694

So sometimes in the codebase we talk about row ids and addresses being the same thing in the codebase. The reason is they often are the same values, but conceptually they shouldn't be treated the same.

[wjones127]

1. Are row ids or row addresses stored in the fragment files?

Row ids aren't stored in the data files. Where they are stored depends on style. For row addresses, they are implicit and not stored anywhere.

Move stable row ids are stored in the manifest. Each fragment is assigned a row id sequence. This sequence provides a mapping from row id, to offset in the fragment.

2. Are row ids or row addresses stored in the index files?

Row ids are stored in the index files. As discussed above, sometimes the row addresses are the same as row ids.

3. How is the row id index updated when there's a row update or a compaction?

For address-style, they are not updated. Rows are moved, and the address changes.

For move-stable, during compaction we tracking the mapping of old location to new location, and rebuild the row id sequence for the fragments that have been compacted.

We don't currently implement stable row ids under updates. That is planned in #3694

4. What is the expected procedure for performing a Take operation using row id / row address?

Row ids are first converted to row addresses. Then you can translate the row addresses into offsets in each fragments. They use those offsets with the file readers to get the rows.

5. How the design relates to the lance file format?
6. Does this design also fit other file format, like parquet?

It's specific to the Lance table format. It doesn't relate at all to the lance file format. In theory, you could add support to Lance table format for Parquet files as data files, but given Parquet is slower for random access, it wouldn't work that well with secondary indexes.

[niebayes]

Thanks! Very helpful.

[jleibs]

Could you clarify:

not necessarily stable after a row is updated

What constitutes an "update"? Specifically if I add a new column to the dataset and leave the value as implicitly null does the row stay stable?

[wjones127]

What constitutes an "update"? Specifically if I add a new column to the dataset and leave the value as implicitly null does the row stay stable?

Well, what I really mean here by update is that the row address / physical location changes and the values may have changed.

Adding a new column keeps the row in the same location / fragment, so it doesn't change the row id.

Doing an update query will, since the old row is tombstoned and the new row is placed in a new fragment.

[majin1102]

From my view:

1. row_id is assigned and generated by manifest(every commit time throught the next_row_id field). row_id marks the uniqueness of each row of data. like the auto incremented id in database

2. row_address is the nature physical identity of each row, which does't have a generating phase. (fragement_id + row_sequence constructs), like the pointer of variables or the physical address of one row in database.

I hope someone can correct me if I describe incorrectly