Make Merge queries more consistent and robust

We ought to be using a transaction on InnoDB and REPLACE INTO on MyISAM. Neither will operate correctly and well on both engines. We could optimize to use INSERT ... ON DUPLICATE KEY UPDATE if the key is equivalent to a unique key.

Oh for the love of Pete... MergeQuery was designed to model INSERT ODKU.

REPLACE INTO AFAIK does two queries internally, so it's not truly atomic. (It does a delete/insert every time.)

I'm not sure I follow what Damien is saying in the first case above. The value specified in key() is getting used. The different failure logic on multi-column keys is a problem, though. I'd almost prefer to convert our degenerate case (used by PostgreSQL and SQLite) to match MySQL's behavior, since it's the only one with a native implementation.

wow, so the entire MergeQuery layer doesn't work as epected ha? (#301036: Optimize Merge queries in Postgres driver)

We the use of #669794: Use savepoints for nested transactions we could make the default MergeQuery work atomically and be used by all three layers.

REPLACE INTO AFAIK does two queries internally, so it's not truly atomic. (It does a delete/insert every time.)

Atomicity is generally irrelevant in a system with MyISAM.

Even at that, then, I've generally been warned away from REPLACE INTO because internally it morphs into "DELETE... INSERT" rather than doing a single operation. That has other odd things it does to the table and indexes and query cache. (It's been a long time since I used it so I don't recall what exactly the issue was, just that I was encouraged by other MySQLites to use ODKU instead.)

What's REPLACE's semantics with the table Damien posted in #4?

Alternative solution: we could use INSERT ... ON DUPLICATE KEY UPDATE... in the only case it works (key() has only one column, which is the only UNIQUE/PRIMARY KEY of the table) [this is the more frequent case], or else fall-back to the parent implementation.

That's exactly what I suggested here:

We could optimize to use INSERT ... ON DUPLICATE KEY UPDATE if the key is equivalent to a unique key.

Or we can change MergeQuery's defined behavior to only work with keys that are enforced as UNIQUE in the database. That would make the default/PostgreSQL/sqlite implementations go *beyond* the defined behavior. This solution may be best because MergeQuery mostly makes sense only for unique keys.

If changing the defined behavior of MergeQuery to match its current actual behavior resolves this issue, I am happy with that approach. Far and away the most common use case for it is when the key field(s) is/are the primary key of the table, which shouldn't have a problem either way.

Why not use savepoints proposed in #669794: Use savepoints for nested transactions
If transactions enabled by default whole try-catch could be in transaction. On myisam we never have atomic actions

We originally used transactions in the original DBTNG patch, but they broke horribly because one b0rked query would cause the entire transaction to need to be rolled back. We cannot use a transaction here unless we have save points implemented. (I'm assuming that will let this approach work, anyway.)

Patch #11 breaks UI - after each page I get another page with

PDOException: SQLSTATE[25P02]: In failed sql transaction: 7 ERROR: current transaction is aborted, commands ignored until end of transaction block: UPDATE p_sessions SET uid=:db_update_placeholder_0, cache=:db_update_placeholder_1, hostname=:db_update_placeholder_2, session=:db_update_placeholder_3, timestamp=:db_update_placeholder_4 WHERE (sid = :db_condition_placeholder_0) ; Array ( [target] => default [return] => 2 [already_prepared] => 1 ) in _drupal_session_write() (line 168 of /var/www/d7/includes/session.inc).

Same here, on a different table.

PDOException: SQLSTATE[25P02]: In failed sql transaction: 7 ERROR: current transaction is aborted, commands ignored until end of transaction block: DELETE FROM {semaphore} WHERE (name = :db_condition_placeholder_0) AND (value = :db_condition_placeholder_1) ; Array ( [:db_condition_placeholder_0] => menu_rebuild [:db_condition_placeholder_1] => 16455391364ba2ed67066644.51457089 ) in lock_release() (line 227 of /Library/WebServer/Documents/drupal7/includes/lock.inc).

re #13 - we have savepoints now. can we get a new patch here?

I'm wondering, doesn't "INSERT, if failed, UPDATE" classify as using Exceptions for flow control which is a bad thing not to mention that it is *slow* (throwing exceptions always is).

I mean, the "fail" will not happen seldom, we use db_merge() for session/variable/cache saving so the chances are imho quite high that we throw an exception on most page loads, and saving a admin page with dozens of settings would result in dozens of variable_set() and therefor dozens of thrown exceptions? This atleast needs benchmarks for those cases...

Maybe something like the following pseudo-code might work, I assume it's still faster than throwing exceptions:

try {
  if (SELECT 1 FROM ...) {
    UPDATE
  }
  else {
    INSERT
  }
}
catch (Exception $e) {
  // if we have a duplicate key exception, we had a race condition. In that case, isn't the behavior unspecified anyway? Who is supposed to win? the first? the latter?
  // Anyway, we could still try a UPDATE or throw a proper Exception, indicating that we hade a race condition.
}

Another approach might be to assume that we update more often than insert and insert if we had no affected rows but this is afaik problematic too, because affected_rows != rows_matched_by_update_conditions so we'd still need a SELECT 1 FROM query and that would result in the worst case of three queries for new entries but fast update queries.

Yes, exceptions are a poor use here for various reasons. Berdir is correct.

If we can't use ODKU (which is very sad, because it's a really really nice approach; are we sure we can't make it work?), the base implementation already has a no-exception implementation that is fine aside from being always 2 queries and not perfectly atomic. Any driver-specific implementation needs to be better than the default or it's not worth it.

So the options I see are:

1) Throw out MergeQuery_mysql entirely; everyone uses the 2 query approach.

2) Make MergeQuery_mysql use ODKU for the single-key case and fall back to parent for the multi-key case. Most of our merge queries are single key, I think, so that gets us atomicity in the common case at least.

3) Figure out if REPLACE INTO would actually work and be preferable to ODKU. I'm uncertain if it would.

4) ?

I think I'm leaning toward #2 right now.

Here's a stab at approach #2.

I suspect the failing test is assuming the old, technically wrong behavior and it just needs to be updated. Someone who knows that system please confirm and reroll. :-)

#19: 715108-mysql-merge.patch queued for re-testing.

Updated: sorry. please delete this post.

Ok, the issue is that we have a discrepancy between the code and the database configuration, which is actually the issue that DamZ pointed out in the initial issue (this already fails on PostgreSQL)

- In our code, we assume that sid and ssid are not duplicate on their own, but only if they occur together.

- However, in the database, we have a PRIMARY KEY on sid and a UNIQUE INDEX on ssid. So if either one of these values is duplicated, the query fails.

I first tried to make a PRIMARY KEY on both columns, but that didn't work because of multiple NULL values in ssid (apparently, doesn't make any sense to me). So the current patch just converts the UNIQUE index to a normal index. I'm a but confused as I can't find a update function that adds ssid as it doesn't seem to exist in D6 at all... ?

Anyway, the updated patch should pass now, but we might want another fix here, I'm not sure.....

EDIT: Me writes strange stuff, I need sleep...

Also, can we really assume that there is a PRIMARY KEY/UNIQUE INDEX on the provided $key? Nobody stops someone from calling it with a $key that is not I'd say....

per andypost, marking #301036: Optimize Merge queries in Postgres driver as duplicate, issues are close enough they should be fixed together even if they're not exactly the same fix.

On which planet mysql and postgresql issues are duplicates?

Maybe on this one when they need the same code to be fixed? :)

This patch uses the default implementation for MySQL when there is more then one key which should be merged on. That means that MySQL does have the same atomic issues as PostgresQL. I don't think that we can actually optimize the Merge on PostgreSQL but we at least need a way to make it atomic or have a way to handle conflicts.

As I explained in #17, try insert and if an exception is thrown, update is not a good idea but we probably need a try/catch to handle the cases where we have a conflict. I still have no idea what should happen then.. Break since we don't know the expected behavior? Let the first insert win and don't update? Execute an update?

I am not familiar with SELECT FOR UPDATE. Is that ANSI SQL? (If not, it shouldn't be in the base implementation but I'm open to it in driver-specific implementations if it works.)

I used Google, so correct my if something of the following is wrong....

- To use SELECT FOR UPDATE, we need a transaction, So we need to start one if there isn't any yet. I don't think we'd need a save point since we don't want to roll back, we just want the locking to persist at least until the end of the function

- I have not found any information that FOR UPDATE is ANSI SQL, but it seems to be supported by almost every dbms (read: MySQL, PostgreSQL, Oracle, DB2 not sure about others) except SQL Server (http://stackoverflow.com/questions/1483725/select-for-update-with-sql-se...)

So what about the following:

We keep the default implementation, document that it is not guaranteed to be atomic and implement the SELECT FOR UPDATE for PostgreSQL and MySQL if count(keys) is > 1 (maybe always since there is no guarantee that the key is a primary or unique key...)

So what about this? IT will apply to both MySQL and PostgreSQL and is about as close to atomic as we can get (especially for PostgreSQL)

PostgreSQL Docs:

If the FOR UPDATE or FOR SHARE clause is specified, the SELECT statement locks the selected rows against concurrent updates.

Awesome. Patch attached.

This looks good. Can we mark #301036: Optimize Merge queries in Postgres driver as a duplicate (again)?

After all, the patch in #35 actually only addresses the PostgreSQL issue, not this one. We need to at least add the bits from #24 back.

Repeating my question from #25, can we safely assume that there is a UNIQUE or PRIMARY KEY on the defined key for MySQL? It isn't really the expected behavior imho, since you are not required to define your keys as UNIQUE/PRIMARY, according to the definition, are you?

Adding a merged patch of #35 and #24 and also a version which always uses the default merge query implementation, just for testing....

Ok, I either did something wrong ( AFAIK not, I used the same code as in #24, which passed) or current implementation does not work very well :)

Ok, updated the implementation..

- Using fetchField() instead of fetch() (the latter always equals to TRUE)
- The patch did not add any arguments but dropped the countQuery() call. adding an "1" expression

I do now get strange undefined index plid in menu.module (5x for every test function), not sure if it is a local issue. Trying with the test bot... Only attaching the always patch.

Ok, I think I agree :)

The "always" patch is basically the same as droping MergeQuery_mysql completely, I always call parent::execute(). I just made it like this to easier switch between both approaches.

OK, I'm confused. Why are we discussing Postgres in a MySQL issue in the MySQL component? :-)

As I understand it, in the single-key case MySQL's ODKU implementation *does* work. It's when there's multiple keys that things get screwy.

Postgres is its own odd animal that may need a stored procedure.

And now we're talking about a more optimized generic implementation as well.

These all sound like separate issues to me. Can someone explain why we can't just apply #24 and then deal with the generic fallback and Postgres implementation in separate issues where they belong, and which already exist?

Crell, its my understanding that at least, MySQL and PostgreSQL can use the same code here. Hence the reason why #301036: Optimize Merge queries in Postgres driver could be a duplicate

OK, so ODKU only works if we're using the primary key(s) of the table as our key fields. Are there any cases where we'd actually want to do otherwise?

I don't mean to harp on ODKU, but it did serve as the original model for the Merge API and it's a single-query implementation. Remember that one of the most common merge queries we run is cache writes, which can be long queries. So anything we can do to keep down the size and quantity of the queries is a good thing.

- We only send the keys twice, they should not be that big...

- Benchmarks would be good however, to have an idea of the impact...

- But first, we need a working patch :)

- Maybe we can get away with documenting that the key needs a PK or UK but even then we need a working, atomic way for multiple keys

It's not the key size that is the issue; it's the other fields, like the cache value, which can be over a megabyte. We want to make sure we don't send that twice.

Yes, and we only send them once, so it's fine? That's what I wrote above. We only ever execute a SELECT (with only the keys as condition, obviously) and then either a INSERT OR an UPDATE.

OK, I looked over the most recent patch. I think I get what's going on there, but I don't get why it's failing so many tests. Is someone still working on this?

Could this be it?

diff --git modules/system/system.install modules/system/system.install
index 0d73c64..0693dd5 100644
--- modules/system/system.install
+++ modules/system/system.install
@@ -1393,8 +1393,6 @@ function system_schema() {
     'indexes' => array(
       'timestamp' => array('timestamp'),
       'uid' => array('uid'),
-    ),
-    'unique keys' => array(
       'ssid' => array('ssid'),
     ),
     'foreign keys' => array(

See #24, that was at least back then required and necessary.

@DamZ: #40 *did* use the default implementation, there was a hardcoded call to the parent implementation, I just didn't delete the whole file to make it easier to switch when testing.

But that DELETE/TRUNCATE change might do the trick.

There is a speed difference between those, obviously.

I called the same db_merge() query 5000 times, below are the results:

Without patch:

Needed: 3.00339s
Needed: 3.08914s
Needed: 3.11475s

Average time per query:
0.0006s

With patch:

Needed: 11.22645
Needed: 10.78288
Needed: 10.87379

Average time per query:
0.00214s

The code, if someone wants to reproduce this:

function conc_test_page()
{
  $start = microtime(true);
  for ($i = 0; $i < 5000; $i++) {
    db_merge('variable')
      ->key(array('name' => 'conc_test_variable'))
      ->fields(array('value' => serialize('value_' . $i)))
      ->execute();
  }

  return t('Needed: %time', array('%time' => round(microtime(true) - $start, 5)));
}

wow a DB isue that yanks a unique key from ssid. Is that still necessary? Also what's with ->addExpression('1') ? If that's necessary then a big, big fat comment is necessary.

The unique key only on ssid is definitly wrong, but changing it to a normal key is probably wrong too but was the only solution I could get working. Defining the PK on sid and ssid gave me errors.

Would hate to stall this issue, care to enlighten me why ssid unique is wrong?

sessions has been fixed! Go :) Note that I have not changed anything on the patch just rerolled without the system.install hunk which now obviously fails.

Um sorry, not yet, I had a question above for the addExpression('1')

I like it too :)

I want to have a look at this tonight when I get home before it gets committed. Flagging for myself.

The complete "SELECT 1 FOR UPDATE" query should move inside the try { block. Right now it's partially inside it, partially outside.

Also, this comment makes no sense at all: // Only run the update if there are no fields or expressions to update.

Since the default implementation is now non-sucky, we should remove the comment block that says "this is sucky, real drivers should reimplement it". :-)

I talked with chx and DamZ in IRC and DamZ should be fixing these shortly. It's sad that we can't use ODKU, but we go with what works.

Also, retitling.

Looks good to me. The bot shouldn't have any problems either, I wager.

Dries, if you'd care to do the honors?

I'm not 100% sure, but doesn't "FOR UPDATE" (in contrast to LOCK IN SHARE MODE" lock the row for reading too, so the second SELECT will wait until the first transaction is commited and then see the updated row and try an update from the beginning?

// Retry the select query, if it returns a row, ignore the error and continue with the update query below.
if ($this->connection->query($sql, $arguments)->fetchField()) {
  throw $e;
}

I think the if needs a ! because this re-throws the error instead of ignoring if a row is returned.

Committed to CVS HEAD. Thanks.

After this patch I cannot install Drupal using sqlite.

SQLSTATE[HY000]: General error: 1 near "FOR": syntax error

http://www.sqlite.org/cvstrac/wiki?p=UnsupportedSql

SELECT ... FOR UPDATE OF ... is not supported. This is understandable considering the mechanics of SQLite in that row locking is redundant as the entire database is locked when updating any bit of it. However, it would be good if a future version of SQLite supports it for SQL interchageability reasons if nothing else. The only functionality required is to ensure a "RESERVED" lock is placed on the database if not already there.

1) We should just write an alternate version for SQLite that skips the FOR UPDATE part and accept that it's non-atomic.

2) This is why we need at least some level of testing framework for SQLite and Postgres.

3) I hate databases.

after this patch, an existing HEAD install has a fatal:

Fatal error: Cannot redeclare class InsertQuery_mysql in ~/drupal-7/includes/database/mysql/query.inc on line
88 Call Stack: 0.0003 57396 1. {main}() ~/drupal-7/index.php:0 0.0111 505184 2. drupal_bootstrap()

Follow-up issue: #839006: SPL autoloader should use require_once to be more robust.

#94 looks OK to me on visual inspection. The comment on the class, though, should also mention that as a result of the lack of FOR UPDATE support its Merge implementation may not be atomic.

We should also get one of the SQLite maintainers to try running it and give it a nod of approval.

Let's try that.

Oops. Didn't mean to tag that.

Fixed all issues for me. There are unrelated sqlite issues throughout this codebase, however, and I believe this will only be the beginning of our woes. Modules will be developed with mysql in mind, and alternative engines will suffer. Anyway, it works.

Nice docs! I asked Damien to take a look.

Max K: If you find other problems with Drupal's SQLite support, please by all means file bug reports about them! (if they don't already exist ;)) We seem to have a really hard time finding SQLite testers, and I'm sure the bugs would get fixed much faster if you were able to chime in on issues with your test results (and if you can write patches to help solve the issues, even better!).

Furthermore, if we were able to get the full test suite passing on SQLite, we'd be able to set up an automated testbot that would constantly test patches to make sure we don't break SQLite going forward. There's a crew working on this for Pgsql already. Would be great to have some folks dedicated to this on the SQLite side!

Update-fail-Insert was the standard logic in D6. That fails in D7 because of PDO, which returns the rows modified, not matched, by a query. We only tested that with MySQL but I think it's across PDO. Merge queries were introduced in the original DBTNG patch exactly for that reason.

That also needlessly complicates the code and adds a third query. We started this issue with one query. Let's not go to three.

Unless UPDATE/SELECT 1/INSERT is considerably faster than what is in HEAD now, let's leave well enough alone. All we need here is a working SQLite-specific version and then we can close this critical. Anything else is for a separate non-critical issue, if at all.

+++ includes/database/sqlite/query.inc
@@ -116,6 +119,65 @@ class UpdateQuery_sqlite extends UpdateQuery {
+ * The first UPDATE query with acquire a RESERVED lock on the database.

I guess that should read ... will acquire...

37 critical left. Go review some!

I would like to understand why do we need FOR UPDATE in the default implementation. If there is an existing record and two processes race for writing that record, there is official word on which one should win. If there is no existing record, we have code that already deals with racing INSERTs. What's the FOR UPDATE for? What's the use case? What are trying to solve here?

Damian, doesn't that sqlite implementation make it non-atomic? Or can SQLite only ever have one connection to it?

I am talking of the default, not the SQLite implementation. What is "atomic" when you are firing one query? Again, what is the reason we so need a lock here?

With the july2.drupal7.dev it didnt install with sqlite but with 108# patch from damien it did install perfectly. Will test more later.

I'm just working off the summary of the issue chx gave me, but here are my thoughts. We can model potential MERGE race conditions as effects on the row being updated between SELECT and INSERT/UPDATE. Let's say there are two threads, A and B.

## Scenario: other thread deletes the row

A: SELECT (with decision to UPDATE)
B: DELETE
A: UPDATE

This results in the same data, even if we lock, as this:

A: SELECT (with decision to UPDATE)
A: UPDATE
B: DELETE

## Scenario: other thread updates the row

A: SELECT (with decision to UPDATE)
B: UPDATE
A: UPDATE

This results in the same data, even if we lock, as this:

B: UPDATE
A: SELECT (with decision to UPDATE)
A: UPDATE

## Scenario: other thread inserts the row

A: SELECT (with decision to INSERT)
B: INSERT
A: INSERT (which fails)
A: UPDATE (because our code falls back to UPDATE on INSERT failure)

This results in the same data, even if we lock, as this:

B: INSERT
A: SELECT (with decision to INSERT)
A: UPDATE

So, in all possible race conditions, our code could have equivalent behavior -- even with locking and proper behavior -- if thread B has queries scheduled certain ways relative to thread A's queries.

To be concise, I also support dropping the FOR UPDATE from the MERGE implementation. FOR UPDATE functions as a pessimistic lock, making us pay the cost of locking even though race conditions should be rare. Switching strategy to UPDATE from INSERT on failure functions as an optimistic lock, making us pay a larger cost for race conditions but only in the rare scenarios they occur.

@Damien Tournoud

I did discuss two threads updating different columns with chx, but it turned out to not be relevant to the issue as long as we have the optimistic locking logic (try UPDATE if INSERT fails). The scenario I was afraid of was thread A INSERTing into col1 and thread B INSERTing into col2 when both had intended to MERGE. That would be a real race condition because no ordering of the operations with FOR UPDATE locking would result in a row with only one of such columns filled. (Proper locking would always result in the latter thread using an UPDATE and resulting in a row with both columns filled.)

The orderings you're suggesting are included in "...if thread B has queries scheduled certain ways relative to thread A's queries." If you have thread A and B running the updates you mention, there's no reason the first ordering is more or less correct than the second.

The question I'm answering is, "If we remove FOR UPDATE locking, what unique race conditions do we introduce that we didn't have before?" Yes, threads will clobber each other's data. But, it looks like we don't introduce any unique scenarios of clobbering data by dropping FOR UPDATE locking.

webchick: You asked for it, you got it. Consider me part of the sqlite testing squadron.

#108 works for me. Recommending implementation, since locking, despite the performance hit, is the correct approach here. Although the update on fail may handle most race conditions (except, possibly some edge cases we're not considering) this does not address what would happen in the unlikely event of a three-way race. Regardless of the astronomically low chance of such an event occurring, we cannot have logic like Ubercart handling sensitive information on top of a foundation that is not fundamentally secure.

Let's commit #108, as that brings us up to SQLite feature parity with MySQL and Postgres. That ends the criticality of this issue and we can mark it fixed and be done with it.

We can then continue refining merge queries over here: #844186: Clarify merge queries

Sounds good. Committed #108 to HEAD.

Max K: YAY! :D