Why Sybase/SQL Server/DB2 SERIALIZABLE is not serializable

[vc]

vc - во-первых, я полагаю, что Ваше возражение не по существу. Исходные транзакции можно переписать иначе, например вот так:

if (select count (*) from t1 where col < 0) = 0 then update t set col = -col where col = 1

But the re-write does not change the fact that every row (the entire table) would have to be inspected and threfore locked without any need for an additional mechanism such as predicate locking. Your new SQL is fully equivalent to the original one in terms of transaction history conflicts.

Предикатная блокировка не зависит от наличия или отсутствия реальных данных. Поэтому "predicate locking would have to lock *potential* not real rows" - это тавтология. Предикатная блокировка по определениею блокирует предикат, на основе которого делается доступ к данным вне зависимости от наличия или отсутствия удовлетворяющих предикату данных.

I fully agree with the above. My point (which you are disputing) is that predicate locking is not needed *if* the database is static, 2PL with its locking *existing* data woud be enough. Predicate locking was 'invented' precisely to handle insert/delete phantoms.

A history with any permutation of all the reads preceding the writes would deadlock, therefore, for your example, 2PL alone would be sufficient. In other words, locking the existing data is enough to ensure serializability which is a subtle but crucial difference from the phantom inserts/deletes...

Нет, неверно.

I am not sure what part of my statement you consider incorrect. Could you please clarify ?

Ровно та же самая техника (блокировка целой таблицы) позволяет избежать фантомов в случае insert/delete. В любом случае нужно как-то учитывать данные, которые не удовлетворяют условиям отбора сейчас, но могут удовлетворять позже. Поэтому если мы разрешаем использовать табличные блокировки (а они по сути нужны только тогда, когда нет предикатных блокировок реализованных любым способом), то никакой разницы между insert/delete или update нет.

It's true that predicate locking (or its implemented subsets) are enough to ensure serializability but again that's not the point I was trying to make. I believe I showed that the example you presented can be handled by a 2PL scheduler without need for predicate locking of any kind. If you think it's not so, please show where the mistake is.

[tengiz]

It's true that predicate locking (or its implemented subsets) are enough to ensure serializability but again that's not the point I was trying to make. I believe I showed that the example you presented can be handled by a 2PL scheduler without need for predicate locking of any kind. If you think it's not so, please show where the mistake is.

vc, табличная блокировка - это частный случай предикатной блокировки, когда предикатом является просто константное логическое выражение всегда дающее резальтатом TRUE. Поэтому говорить, о 2PL без предикатных блокировок, но имея в виду, что табличные блокировки разрешены - несколько странно. И именно поэтому 2PL без предикатных блокировок (и без частного их случая в виде табличных блокировок) не будет правильно работать со сценариями типа того, который мы разбираем. Вне зависимости от того используем мы delete/insert или ограничиваемся только update (который всегда логически сводится к delete/insert).

[vc]

It's true that predicate locking (or its implemented subsets) are enough to ensure serializability but again that's not the point I was trying to make. I believe I showed that the example you presented can be handled by a 2PL scheduler without need for predicate locking of any kind. If you think it's not so, please show where the mistake is.

vc, табличная блокировка - это частный случай предикатной блокировки, когда предикатом является просто константное логическое выражение всегда дающее резальтатом TRUE. Поэтому говорить, о 2PL без предикатных блокировок, но имея в виду, что табличные блокировки разрешены - несколько странно. И именно поэтому 2PL без предикатных блокировок (и без частного их случая в виде табличных блокировок) не будет правильно работать со сценариями типа того, который мы разбираем. Вне зависимости от того используем мы delete/insert или ограничиваемся только update (который всегда логически сводится к delete/insert).

Sorry, I was sloppy in my descriptions. What I've always meant is that 'not exists' /'count(*)' in your examples will scan each row and as a result will use row-level locks which are equivalent to using a table lock due to a full table scan. Never did I mean that a 'true' table lock is needed (I am aware as I've said several times that a table level lock is a crude implementation of predicate locking, the subtler variety being key range locking). None is needed (in addition to row locks) in order to ensure serializability in your examples.

[tengiz]

Sorry, I was sloppy in my descriptions. What I've always meant is that 'not exists' /'count(*)' in your examples will scan each row and as a result will use row-level locks which are equivalent to using a table lock due to a full table scan. Never did I mean that a 'true' table lock is needed (I am aware as I've said several times that a table level lock is a crude implementation of predicate locking, the subtler variety being key range locking). None is needed (in addition to row locks) in order to ensure serializability in your examples.

vc, ok, поправка понятна, однако она по сути мало что меняет в выводе. Давайте ещё раз посмотрим на запрос, о котором мы говорили: (select count (*) from t where col < 0). Если я Вас правильно понимаю, то для того, чтобы всё правильно отработало в отсутствии delete/insert вы предлагаете наложить блокировки на ВCЕ строки в таблице, а не только те, для которых col < 0 (иначе не будет сериализованного выполнения). Т.е. мы вынуждены проигронировать предикат при сканировании (хотя при вычислении результата count(*) предикат, естественно, будет приниматься во внимание).

Но отсюда немедленно неутешительный вывод, что для того, чтобы это всё работало как нам хочется, ЛЮБАЯ операция сканирования данных - для update, для select - неважно, должна будет просканировать и наложить блокировки на все строки всех таблиц участвующих в запросах вне зависимости от наличия или отсутствия предикатов и вне зависимости от того удовлетворяют ли строки предикатам или нет. Другими словами мы только что полностью отменили индексы - ведь нам всё равно всегда придётся сканировать целые таблицы. Согласитесь, это не совсем, мягко говоря, удобно.

[vc]

Давайте ещё раз посмотрим на запрос, о котором мы говорили: (select count (*) from t where col < 0). Если я Вас правильно понимаю, то для того, чтобы всё правильно отработало в отсутствии delete/insert вы предлагаете наложить блокировки на ВCЕ строки в таблице, а не только те, для которых col < 0 (иначе не будет сериализованного выполнения). Т.е. мы вынуждены проигронировать предикат при сканировании (хотя при вычислении результата count(*) предикат, естественно, будет приниматься во внимание).

I should stop taking those shortcuts...

I do not suggest locking all the rows but only those participating in the transactions.

The 'participating' word needs a little clarification. Let's reason from the point of view of an abstract S2PL scheduler. Those 'exists' or 'count(*) == 0' are a bit misleading because they imply that rows satisfying col < 0 are participants whilst the exact opposite is true -- the complement subset is the actual transaction participant. In our case, it just happens so that the complement equals the whole table (if the 'not exists' predicate is true, obviously). Our abstract S2PL picks the rows one by one in some way and places R locks on them. The way it does this is not defined in the S2PL protocol, the optimization through indexes or whatever is up to the implementor. Let's just pretend that there is a way to grab rows efficiently (in the case of a small subset) in some magical way, without requiring to scan the whole set.

So for 'not exists (select * from t where col < 0)' to be true the whole table has to satisfy col >=0. The same goes true for 'count(*)==0'. The idea is that a SQL predicate(s) (not to be confused with predicate locking ;) describes rows participating in a transaction. I believe it's the only reasonable interpretation if we want to express what is going on in serializability theory terms.

If you accept this line of reasoning, then it's clear that some histories will succed and some will dead-lock thus implementing 'true' serializability without resorting to predicate locking.

[tengiz]

vc, небольшая коррекция исходной задачи и мы опять получаем проблему при реализации serializable для delete/insert free транзакций если мы принципиально не хотим пользоваться табличными блокировками:

if (select count (*) from t where col < 0) between 5 and 10 then do some stuff...

В этом случае уже не получится сказать, что дополнительное предикату col < 0 множество строк совпадает с множество всех строк таблицы. Но, тем не менее, нам опять придётся блокировать все строки таблицы t. Просто потому, что и множество строк, которые удовлетворяют предикату, а также и множество строк, которые удовлетворяют дополнительному предикату, гарантированно должны остаться стабильными. А когда некое подможество объединяется с дополнительным ему подмножеством, то ясно, что результат всегда будет одним и тем же - всё множество.

[vc]

vc, небольшая коррекция исходной задачи и мы опять получаем проблему при реализации serializable для delete/insert free транзакций если мы принципиально не хотим пользоваться табличными блокировками:

if (select count (*) from t where col < 0) between 5 and 10 then do some stuff...

Correct me if I am wrong but 'traditional' serializability theory deals with r/w operations over subsets that are members of the same poset with respect to inclusion.

If my recollection is right, then, as before, we need to express the above condition in this (complementary) way:

if (select count (*) from t where col >= 0) between .. and .. then do some stuff [over subsets belonging to the same inclusion poset as the subset defined by the 'col >=0' predicate]...

Clearly, predicate locking, theoretically, would alow queries whose predicates are not restricted in this manner.

[tengiz]

vc, боюсь, что я начинаю терять нить дискусси. Давайте попробуем всё-таки определиться и чётко обозначить что мы обсуждаем. Во-первых, обработка транзакций и реляцонная теория - вещи ортогональные и полностью независимые. Я использую SQL в примерах только потому, что это самый популярный способ общения с современными системами обработки транзакций.

Во-вторых, суть обещаний, которые дают систем обработки транзакций очень проста: если программы, манипулирующие данными (любым способом, написанные на любом языке) работают правильно в единственном экземпляре, то система обработки транзакций гарантирует, что любая их параллельно работающая комбинация тоже будет работать правильно. Откуда сразу следует, что искусственных ограничений на то, что могут и чего не могут делать эти программы практически нет.

В том, числе и ограничения, которое Вы сформулировали, если я его правильно понимаю, а именно - условый оператор может работать с любыми данными, ветвления условного оператора могут работать с любыми данными, совершенно никак не связанными с подмножеством, которое фигурирует в условии. Возвращаясь к нашему примеру - do some stuff может делать всё, что угодно, причём с любыми данными.

Понятно, что наличие подобных ограничений может существенно упростить реализацию систем обработки транзакций и/или обеспечить лучшую производительность, etc. Для чего, по сути, и были придуманы "уровни изоляции", отличные от идеальной изоляции. Но формальная теория не имеет таких ограничений. Причём, как я уже говорил, практически с самого начала. Теоретическая работа описывающая проблему фантомов и её решение при помощи предикатных блокировок была опубликована аж в 1976 году.

[tengiz]

Кстати - заглянул в книгу Грея об обработке транзакций и в книгу Бернштайна об изоляции чтобы уточнить исторические определения статических и динамичских баз данных. Insert/deletе операции о которых там идёт речь на самом деле имеют очень опосредованное отношение к SQL insert/delete. "Статическая" база данных имеет дело со статическим набором объектов - объекты не появляются и не уничтожаются, а также никаким образом не могут меняться так, чтобы из-за изменения исключались бы и попадали бы в поле зрения транзакций. В СУБД поддерживающей хотя бы SQL оператор UPDATE и WHERE clause для SELECT/UPDATE, строки таблиц в принципе не могут считаться объектами в смысле "статической" базы. Для того, чтобы SQL СУДБ была "статической" нужно наложить серьёзные ограничения на возможные операции, что в итоге практически перечеркнуло бы полезность SQL в большинстве приложений.

[vc]

vc, боюсь, что я начинаю терять нить дискусси. Давайте попробуем всё-таки определиться и чётко обозначить что мы обсуждаем.

We are discussing the fact (I believe) that an S2PL scheduler by itself ensures serializable histories for static databases. However, there are at least two restrictions:

1. The database should be static. Maybe 'should be' is too stong a statement, the traditional serializability theory simply says nothing about inserts. It just talks about reads and writes of the existing data. However, as soon as we try to reason about inserts (writing new data), S2PL won't ensure serializability any more (phantoms).

2. If we want to use another more powerful language, like SQL, to describe our transactions, we have to preserve the original simplistic serializability theory language (SL) semantics since otherwise serializability theory is not applicable any more and any discussion becomes meaningless.

SL's vocabulary contains {read, write, precedence, conflict}.

A translation example:

if (select count (*) from t where col < 0) between 5 and 10 then do some stuff...

We cannot offer a translation at this stage because we do not know what 'do some stuff' is (I'll elaborate on why we need to know that later). Let's assume it's 'update t where col >0.

Then the SQL can be translated as:

if count(read(Xi|col >= 0)) between ...; /* we have to invert the predicate in order to create a *conflict* with concurrent writes */; write(Xi|col>0);

The reason we need to know what 'do stuff' is that we have to determine whether the original statement can be re-stated in such a way as to create conflicts, a crucial component of S2PL. Generally speaking, we can ensure that conflicts are in place when the subsets on which read/write operate are a partial order with respect to the 'subset of' operation. In other words, only SQLs where all the predicates define ( or can be re-stated to define) such subsets can be analyzed in terms of serializability theory.

Во-первых, обработка транзакций и реляцонная теория - вещи ортогональные и полностью независимые. Я использую SQL в примерах только потому, что это самый популярный способ общения с современными системами обработки транзакций.

I've talked all the time about transactions, not a word was said about relational theory. When I mentioned sets, I was trying to describe how to re-formulate a SQL so that it could be analyzed using serializability theory.

Во-вторых, суть обещаний, которые дают систем обработки транзакций очень проста: если программы, манипулирующие данными (любым способом, написанные на любом языке) работают правильно в единственном экземпляре, то система обработки транзакций гарантирует, что любая их параллельно работающая комбинация тоже будет работать правильно. Откуда сразу следует, что искусственных ограничений на то, что могут и чего не могут делать эти программы практически нет.

Informally yes you are right. Unfortunately S2PL theory, the cornerstone of all the locking schedulers, limits the set of serializable transactions to conflict serializable only with an additional restriction being that the database' had better be static.

Но формальная теория не имеет таких ограничений.

If by formal theory you mean S2PL, see above regarding restrictions.

Теоретическая работа описывающая проблему фантомов и её решение при помощи предикатных блокировок была опубликована аж в 1976 году.

Well yes Eswaran and others indeed published their work in 1976. However, whilst theoretically interesting, generic predicate locking implementation has at least two problems: detecting conflicts is very expensive and concurrency is not great. What we have today are partial implementations either via entire table locking or key-range locking (if you are lucky to have an appropriate index and the optimizer decides to use it).

Besides, predicate locking is an addition to S2PL so that we cannot say there is some elegant unified serializability theory. Instead, we have rather an eclectic architecture created to ensure decent concurrency in lower isolation modes through S2PL plus serializability via table/index locking under Serializable IL.

[vc]

"Статическая" база данных имеет дело со статическим набором объектов - объекты не появляются и не уничтожаются, а также никаким образом не могут меняться так, чтобы из-за изменения исключались бы и попадали бы в поле зрения транзакций.

Well no 'write' == 'update'. It's predicates that can be a problem with respect to S2PL.

В СУБД поддерживающей хотя бы SQL оператор UPDATE и WHERE clause для SELECT/UPDATE, строки таблиц в принципе не могут считаться объектами в смысле "статической" базы. Для того, чтобы SQL СУДБ была "статической" нужно наложить серьёзные ограничения на возможные операции, что в итоге практически перечеркнуло бы полезность SQL в большинстве приложений.

We need to impose restictions only on predicates, not on the operations themselves (see my previous message). I am not sure how restrictive those might be. Perhaps you would come up with an example.

[tengiz]

We are discussing the fact (I believe) that an S2PL scheduler by itself ensures serializable histories for static databases. However, there are at least two restrictions:...

Я думаю, что обсуждение этого теперь уже архаизма не очень интересно. Ограничения и проблемы того, что Вы называете S2PL давно известны и преодолены, современные системы его не используют, более того, ни одна популярная коммерческая блокировочная SQL СУБД вообще никогда S2PL не использовала. В чём цель обсуждения чего-то что уже давно устрарело и неактуально?

SL's vocabulary contains {read, write, precedence, conflict}.

Вы пропустили ещё один verb в словаре - send message, о чём будет пара слов ниже.

We cannot offer a translation at this stage because we do not know what 'do some stuff' is (I'll elaborate on why we need to know that later). Let's assume it's 'update t where col >0.

Вот здесь и вылезает send message, который и портит всю картину. Если Вы не хотите ограничиться прокрустовым ложем по сути бесполезных в практическом смысле систем с заранее известным линейным (без ветвлений) набором операций в транзакции, или хуже того, с заранее известным набором readset/writeset, то тогда Вам придётся транслировать SQL оператор в условном выражении до того, как Вы будете знать, что произойдёт в случае когда выражение true или false - что означает, что придётся делать трансляцию такой, чтобы не было потом проблем ни с одной ветвью условного оператора (и даже ни с одним последующим оператором в транзакции, иначе непонятно, как это всё вообще можно использовать в интерактивных системах.) Как мы уже видели, это всего будет означать, что a) придётся прочитать все строки из таблицы t; б) придётся наложить блокировки на всё, что будет прочитано из таблицы вне зависимости от того, удовлетворяет ли оно предикатам или нет.

Informally yes you are right. Unfortunately S2PL theory, the cornerstone of all the locking schedulers, limits the set of serializable transactions to conflict serializable only with an additional restriction being that the database' had better be static.

Это формальное определение сериализуемости, данное наиболее общим образом. Опять же, S2PL в приложении к СУБД и неактуальна, и малополезна. Она в конексте реляционных СУБД имеет сейчас лишь педагогическую или историческую ценность.

Besides, predicate locking is an addition to S2PL so that we cannot say there is some elegant unified serializability theory. Instead, we have rather an eclectic architecture created to ensure decent concurrency in lower isolation modes through S2PL plus serializability via table/index locking under Serializable IL

vc - это уже как Вам угодно, а дело вкуса - личное дело каждого. На мой взгляд блокировочные алоритмы изоляции транзакций очень даже элегантны и компактны. Но самое главное - они корректны и гарантируют строгую сериализацию. Действительно, при этом они по факту разрешают только некое подмножество всех вероятных серилаизованных историй. Но если вспомнить, что для полезного использования изоляции есть ограничения на возможные истории, совершенно не зависящие от реализации - например разумное ограничение на отсутствие каскадных откатов, то выяснится, что ограничения имеющие причиной собственно блокировочность алгоритма не так уж и страшны.

[tengiz]

Well no 'write' == 'update'.

Прошу прощения но, я не уверен, что я это понял.

We need to impose restictions only on predicates, not on the operations themselves (see my previous message). I am not sure how restrictive those might be. Perhaps you would come up with an example.

vc, в статической базе выбор объектов для чтения/изменения делается не на основе динамических свойств объектов, а на основе, если угодно, их неизменяемых "имён" (identity, key, etc.). Т.е. для того, чтобы приложение написанное на SQL можно было реализовать на S2PL системе, ограничения для гарантированной сериализуемости должны быть следующими: 1) строки не вставляются и не удаляются; 2) ключи никогда не меняются; 3) предикаты можно использовать любые, но индексы можно использовать только для первичных ключей. Согласитесь - это очень жёсткие ограничения.

[vc]

We are discussing the fact (I believe) that an S2PL scheduler by itself ensures serializable histories for static databases. However, there are at least two restrictions:...

Я думаю, что обсуждение этого теперь уже архаизма не очень интересно. Ограничения и проблемы того, что Вы называете S2PL давно известны и преодолены, современные системы его не используют, более того, ни одна популярная коммерческая блокировочная SQL СУБД вообще никогда S2PL не использовала. В чём цель обсуждения чего-то что уже давно устрарело и неактуально?

Now, this is interesting. I'd readily admit that I may be completely wrong here but my recollection is that at least Sybase had claimed that strict 2PL is what its implementation was. If this is not so, then what exact locking protocol is used by say SQL Server and where I can find a proof of its correctness ?

Please point me to some source that describes how exactly the S2PL limitations have been solved.

[vc]

Well no 'write' == 'update'.

Прошу прощения но, я не уверен, что я это понял.

Should have written: "Well, no, 'write' is the same as 'update' ".

Т.е. для того, чтобы приложение написанное на SQL можно было реализовать на S2PL системе, ограничения для гарантированной сериализуемости должны быть следующими: 1) строки не вставляются и не удаляются; 2) ключи никогда не меняются; 3) предикаты можно использовать любые, но индексы можно использовать только для первичных ключей. Согласитесь - это очень жёсткие ограничения.

I do not understand why we need (2) and (3). I claimed that in addition to (1), predicates have to be restricted due to the limitations of the theoretical apparatus, traditional serializability theory, I am familiar with.