sql: add non-trivial implementations of FOR UPDATE, FOR NO KEY UPDATE, FOR SHARE, FOR NO KEY SHARE

[jordanlewis]

#40206 added parsing for the various row-level lock modes, and treats them like no-ops. This is acceptable for CockroachDB, which only supports SERIALIZABLE transactions, because from a client's perspective there's no way to observe whether any particular transaction needed to be restarted because of a conflict on the rows that were declared as FOR UPDATE, or because of some other conflict - the transaction will have to be restarted in either case.

This issue tracks improving this behavior for performance reasons. There's ongoing work in core to support at least some of these semantics.

[nvanbenschoten]

The issue lists four lock types, which are documented in PG's docs here. Here are a few takeways from thinking about how these will play into CRDB in the future:

1. CRDB does not distinguish between locking on a KV's key and locking its key and value. Because of that, I think it makes sense to upgrade all FOR NO KEY [SHARE/UPDATE] variants to its corresponding FOR [SHARE/UPDATE] locking mode. This is correct per PG's lock conflict table. The only false conflict it introduces is between FOR NO KEY UPDATE and FOR KEY SHARE. I don't think this is worth worrying about, especially because of the next point.
2. We can leave the FOR SHARE locking mode as a no-op, as CRDB's default concurrency control scheme is already similar to this. We wouldn't want to upgrade these locking modes to FOR UPGRADE and introduce synthetic conflicts between multiple FOR SHARE locking modes. This might cause deadlocks in user applications.
3. If/when we eventually introduce read-locks at the KV level, the FOR SHARE locking mode should line up with their semantics.

In addition to supporting these locking modes, we'll also want to use the same approach that Postgres uses for using these locking modes in UPDATE and DELETE statements. From Postgres' docs:

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.

CockroachDB implements serializability, so this is not needed for correctness, but acquiring these locks implicitly in UPDATE and DELETE statements has the potential to:

1. reduce transaction retries
2. improve performance by reducing thrashing and enforcing better queueing

[sumeerbhola]

1. CRDB does not distinguish between locking on a KV's key and locking its key and value. Because of that, I think it makes sense to upgrade all FOR NO KEY [SHARE/UPDATE] variants to its corresponding FOR [SHARE/UPDATE] locking mode. This is correct per PG's lock conflict table. The only false conflict it introduces is between FOR NO KEY UPDATE and FOR NO KEY SHARE. I don't think this is worth worrying about, especially because of the next point.

nit: I assume you meant FOR KEY SHARE.

2. We can leave the FOR SHARE locking mode as a no-op, as CRDB's default concurrency control scheme is already similar to this. We wouldn't want to upgrade these locking modes to FOR UPGRADE and introduce synthetic conflicts between multiple FOR SHARE locking modes. This might cause deadlocks in user applications.
3. If/when we eventually introduce read-locks at the KV level, the FOR SHARE locking mode should line up with their semantics.

I'm not clear about how not "worth worrying about" is not contradicted by bullet 3 -- if upgrading KEY SHARE to SHARE (for a transaction that is reading keys) and NO KEY UPDATE to UPDATE (for a transaction that is updating the non key columns) can introduce deadlocks when FOR SHARE is implemented with locking, isn't that something to be concerned about?

[nvanbenschoten]

nit: I assume you meant FOR KEY SHARE.

Yes, updated.

isn't that something to be concerned about?

I had the same thought when writing this. There is a bit of a contradiction in this reasoning, as you pointed out. We don't want to weaken these locking modes any further because then they become no-ops and not useful to expose. However, we don't want to strengthen them because then that presents the possibility of creating unexpected deadlocks for unsuspecting users. We also likely don't want to actually support them properly as that would be a large undertaking.

The way I've been reconciling this is that in my mind there are two primary row-level locking classes (SHARE and UPDATE) and each class contains two locking modes differentiated by the KEY vs. NO KEY distinction. This secondary distinction feels like a Postgres implementation detail. For instance, there is no such secondary distinction in MySQL: https://dev.mysql.com/doc/refman/8.0/en/innodb-locking-reads.html. It also doesn't map to CockroachDB today.

So I think we have two choices here:

1. reject the KEY/NO KEY specifier and only accept the FOR SHARE and FOR UPDATE. This isn't a terrible option as I highly doubt people use KEY/NO KEY frequently in practice. However, it does prevent people who currently do use these specifiers from running on CRDB without modification to their code.
2. ignore uses of the KEY/NO KEY specifier and document that it is ignored and that only the primary row-level locking classes are considered. This does create the opportunity for deadlock if a user has built their application in such a way that they are using these clauses for correctness and not just performance. However, it does not force people who are using the specifiers for performance only from needing to modify their code.

I think a strong argument could be made for both approached. @rafiss I'm curious if you have an opinion here.

Also, to add a little more context here, KEY/NO KEY were added to PG in this commit: postgres/postgres@0ac5ad5 and the motivation was primarily so that they could be used internally by PG to improve concurrency between UPDATEs that did not modify the key-portion of a row and FK checks. Interestingly, our attempt to solve the same problem is through the use of column families. To this day, PG does still occasionally ignore the KEY/NO KEY specifiers and collapse locking modes along locking classes. This is most common when interfacing with foreign data wrappers: https://github.com/postgres/postgres/blob/1281a5c907b41e992a66deb13c3aa61888a62268/contrib/postgres_fdw/deparse.c#L1274.

[rafiss]

I did a very unscientific Github search to see how often the various syntaxes appear in public codebases:

SELECT FROM "FOR UPDATE" - 523,512
SELECT FROM "FOR NO KEY UPDATE" - 4,602
SELECT FROM "FOR SHARE" - 112,272
SELECT FROM "FOR KEY SHARE" - 8,796

That is useful data that suggests that many people probably would not be affected by either choice. But apart from that, another consideration is to figure out if any ORMs generate queries with the KEY/NO KEY specifiers. I would guess none do it by default, and those that do support it probably see similar proportions of usage as above. For what it's worth, looking at some of the ORMs we are focusing on right now: Hibernate does not support it but has an open issue for it, and Django also does not support it but has an open issue/PR. For both of these we are creating a CockroachDB dialect/adapter, so if these issues ever do get implemented we should still be able to avoid using the KEY/NO KEY specifiers with CockroachDB, if necessary.

So I think my vote is for option 1 -- rejecting the KEY/NO KEY specifiers, and also adding telemetry on how often the unimplemented syntax is used. I worry that ignoring them (even with documentation elsewhere) will not be obvious to users, and I would claim that deadlocks happening randomly at runtime are worse than syntax errors happening deterministically at runtime. Though I'm definitely open to being convinced otherwise, and my position isn't held very strongly.

I do want other stakeholders to weigh in. My understanding is that we usually only go with the "accept the syntax but ignore it" approach if the syntax in question has no meaning in CockroachDB and causes no behavior change... which arguably does apply in this case.

[nvanbenschoten]

Thanks for gathering those numbers and finding references to this in Hibernate and Django Rafi!

I also have conflicted opinions here, but I'm actually leaning towards option 2 for the following reasons:

• after looking at some of the uses in Github, it looks like this will come up almost exclusively in ORM test suites. Rejecting these modes will prevent some tests from succeeding when they otherwise could.
• The Github search also confirmed that there is precedence for treating these two strengths the same. See: "This is still correct but less efficient (will conflict more often than required)."
• the two ORM discussions you posted confirm that people look at these primarily as performance optimizations.
• I suspect that any developer who would actually depend on the subtleties of these locking modes would be more comfortable reading our documentation on it than developers who observe them being rejected and don't understand the difference between the modes.
• It's worth keeping in mind that we do have transaction deadlock detection, so this wouldn't cause an application to deadlock indefinitely. Instead, applications would get transaction aborted errors if their use of these locking modes does cause deadlocks.

Also, keep in mind that for the next release we won't even perform any FOR SHARE locking at all, so we don't need to resolve this immediately.