How to UPDATE data without locking every record the search encounters? We have the following database specifications:
version: 10.1.47-MariaDB-0ubuntu0.18.04.1
innodb_version: 5.6.49-89.0
tx_isolation: READ-COMMITTED
innodb_strict_mode: ON
sql_mode: NO_AUTO_CREATE_USER,NO_ENGINE_SUBSTITUTION
autocommit: ON

We have the problem that we lock too many data entries in the table, which causes deadlocks. Here is our example.
The first query we run:
UPDATE a SET col4 = 3 WHERE col1 = 1 AND col2 = 2 AND col3  = 3;
We have single column indexes on all the columns. According to the docs: this will set an exclusive next-key lock on every record the search encounters.
So the next UPDATE statement will be waiting for the previous one, although the matching final result records are not overlapping. This is because the index on col1.
UPDATE a SET col4 = 2 WHERE col1 = 1 AND col2 = 9999;
I would like to lock only the final result records and not &quot;every record the search encounters&quot;. Splitting the query into a SELECT and an UPDATE by primary key gives me that result, but then a racing condition can happen between the SELECT and the UPDATE. Combining those in a transaction also doesn't help, as every SELECT is a consistent read.
How would you design a process like this, where I can run an UPDATE statement, without locking every record the search encounters?
UPDATE a SET col4 = 3 WHERE col1 = 1 AND col2 = 2 AND col3  = 3;

Needs this composite index:
INDEX(col1, col2, col3)  -- in any order

So, if you start it with col1, col2 (in either order), that index will also work nicely for
UPDATE a SET col4 = 2 WHERE col1 = 1 AND col2 = 9999;

If, by &quot;We have indexes on all the columns&quot; you mean single-column indexes, then those are wasted and in the way.  MySQL will use only one index.  It will pick among (col1), (col2), (col3) looking for the most selective.  Then it will scan all the rows with, say col1 = 1.  This is likely to be a lot more rows than you need to UPDATE.
With the composite index I recommend, it will go straight to the row(s) that match all of the WHERE clause.  This will be many fewer rows, thereby decreasing the likelihood of a deadlock.  Also, it will be much faster, which also decreases the chance of a deadlock.
Regardless, your could should check for errors and re-run any transaction that hits a deadlock.