sql/kv: support FOR NO KEY UPDATE and FOR KEY SHARE

[nvanbenschoten]

Originally tracked in https://github.com/cockroachdb/cockroach/issues/40205.

We added support for the FOR UPDATE explicit locking mode in https://github.com/cockroachdb/cockroach/pull/45701. In doing so, we aliased FOR NO KEY UPDATE to FOR UPDATE and FOR KEY SHARE to FOR SHARE.

Context: https://www.postgresql.org/docs/current/explicit-locking.html

Row-Level Lock Modes

FOR UPDATE
FOR UPDATE causes the rows retrieved by the SELECT statement to be locked as though for update. This prevents them from being locked, modified or deleted by other transactions until the current transaction ends. That is, other transactions that attempt UPDATE, DELETE, SELECT FOR UPDATE, SELECT FOR NO KEY UPDATE, SELECT FOR SHARE or SELECT FOR KEY SHARE of these rows will be blocked until the current transaction ends; conversely, SELECT FOR UPDATE will wait for a concurrent transaction that has run any of those commands on the same row, and will then lock and return the updated row (or no row, if the row was deleted). Within a REPEATABLE READ or SERIALIZABLE transaction, however, an error will be thrown if a row to be locked has changed since the transaction started. For further discussion see Section 13.4.

The FOR UPDATE lock mode is also acquired by any DELETE on a row, and also by an UPDATE that modifies the values on certain columns. Currently, the set of columns considered for the UPDATE case are those that have a unique index on them that can be used in a foreign key (so partial indexes and expressional indexes are not considered), but this may change in the future.

FOR NO KEY UPDATE
Behaves similarly to FOR UPDATE, except that the lock acquired is weaker: this lock will not block SELECT FOR KEY SHARE commands that attempt to acquire a lock on the same rows. This lock mode is also acquired by any UPDATE that does not acquire a FOR UPDATE lock.

FOR SHARE
Behaves similarly to FOR NO KEY UPDATE, except that it acquires a shared lock rather than exclusive lock on each retrieved row. A shared lock blocks other transactions from performing UPDATE, DELETE, SELECT FOR UPDATE or SELECT FOR NO KEY UPDATE on these rows, but it does not prevent them from performing SELECT FOR SHARE or SELECT FOR KEY SHARE.

FOR KEY SHARE
Behaves similarly to FOR SHARE, except that the lock is weaker: SELECT FOR UPDATE is blocked, but not SELECT FOR NO KEY UPDATE. A key-shared lock blocks other transactions from performing DELETE or any UPDATE that changes the key values, but not other UPDATE, and neither does it prevent SELECT FOR NO KEY UPDATE, SELECT FOR SHARE, or SELECT FOR KEY SHARE.

Motivation

The FOR NO KEY UPDATE and FOR KEY SHARE locking modes were added to PostgreSQL in https://github.com/postgres/postgres/commit/0ac5ad5134f2769ccbaefec73844f8504c4d6182. The motivation for these weaker locking modes is to reduce contention between updates to an existing row and foreign key lookups (existence checks) on existing rows.

This is an important optimization for certain workloads, and we should explore adding it to CockroachDB. Doing so would require some work in SQL to properly expose these as explicit locking modes and to use these weaker locking modes where possible implicitly (e.g. during value-only UPDATEs and during FK checks). Doing so would also require a lot of work in KV to expose and properly obey these weaker locking modes. This would require changes to the lock-table, to the latch manager, and to the timestamp cache.

Alternatives: Column Families

Column families can currently be used to a similar effect. We are currently exploring (https://github.com/cockroachdb/cockroach/issues/46758) the use of GetRequests directed at only the sentinel column family of a row when performing foreign key lookups. If/when we make that change, expressing each row as a first column family containing all columns in the primary key and a second column family containing all other columns would have the same effect as if we made this larger change.

Jira issue: CRDB-3949

[andreimatei]

We are currently exploring (#46758) the use of GetRequests directed at only the sentinel column family of a row when performing foreign key lookups.

46758 doesn't seem to talk about this sentinel column. Maybe it's a great idea; can you say more? I forgot if there always is a sentinel col fam; is there? Any downsides here? Can you remind me when this col fam is written to?

[nvanbenschoten]

46758 doesn't seem to talk about this sentinel column.

This was actually tracked in https://github.com/cockroachdb/cockroach/issues/30852, and it looks like @RaduBerinde already addressed it in https://github.com/cockroachdb/cockroach/pull/42572!

So the general idea is to essentially do what we do in https://github.com/cockroachdb/cockroach/pull/30624 – put all dynamic columns in a table into their own column families.

I forgot if there always is a sentinel col fam

Kind of. By default, it includes every column in the table. So by default, there's a 1:1 mapping between rows and keys.

Any downsides here?

Two big downsides: inserting and deleting rows from the table now needs to touch multiple keys and scanning rows from the table now needs to scan over multiple keys. There's also the associated bookkeeping cost of extra kvs.

[nvanbenschoten]

Interestingly, VLDB 2020's best paper discusses contended in-memory transaction processing and references an optimization in OCC and MVCC systems that they call "timestamp splitting". The optimization splits the read and write timestamps of database records to avoid false contention between transactions that touch mutually exclusive subsets of columns in a record. It ends up being exactly what we're talking about here with column families. They even reference using "timestamp splitting" in YCSB and TPC-C, which we did in https://github.com/cockroachdb/cockroach/pull/32704 and https://github.com/cockroachdb/cockroach/pull/30624, respectively.