Why Sybase/SQL Server/DB2 SERIALIZABLE is not serializable

[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.

[tengiz]

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.

У меня опять появляется ощущение, что из-за вольностей с терминологией и аббревиатурами мы не понимаем, что мы обсуждаем. Поэтому давайте я попробую привести всё к общему знаменателю:

* 2PL - это 2 phase locking protocol, суть которого в том, что стратегия работы с блокировками состоит в друх фазах: фаза накопления блокировок и фаза освобождения блокировок. Фазы обязаны сделовать именно в этом порядке. Точка. Больше ничего 2PL не утверждает.

* Что конкретно блокировать и в каких случаях - это уже слегка другая история - но одно свойство протокола всегда остаётся в силе: вне зависимости от наличия или отсутствия предикатных блокировок, индексных блокировок, многоуровневых блокировок, блокировок диапазонов ключей, etc. суть 2PL всегда одна и таже - две чёткие фазы работы с блокировками строго следующие друг за другом - начало транзакции, накопление блокировок, затем освобождение блокировок и конец транзакции.

* Есть как минимум две разновидности 2PL протокола - Conservative a.k.a Static 2PL и Strict 2PL:

- Conservative/Static 2PL: все объекты, участвующие в транзакции известны заранее, поэтому все необходимые блокировки берутся сразу одним махом (первая фаза), затем делаются все необходимые манипуляции с данными, как только работа с каким-то подмножеством данных завершается (так как заранее всё известно, то мы точно знаем, что в этой транзакции это подмножествно данных никогда больше трогаться не будет), блокировки, ассоциированные с этим подможеством, могут быть немедленно освобождены (началась вторая фаза), к концу работы транзакции все блокировки постепенно освобождаются. Ни одна из известных мне популярных коммерческих SQL СУБД (включая Sybase) эту разновидность 2PL не использует и никогда не использовала.

- Strict 2PL: заранее ничего не известно, ни набор операций, ни множество объектов затронутых операциями, поэтому блокировки набираются по мере необходимости, и освобождаются только при явном конце транзакции. Все известные мне коммерческие SQL СУБД (включая Sybase) используют эту разновидность 2PL. Ещё раз специально оговариювась, разновидности 2PL не имеют отношения к тому, что конкретно блокируется - объекты, предикаты, ключи, диапазоны и пр. Суть протокола - две фазы работы с любыми блокировками.

Отсюда вопрос:

vc, когда Вы говорите S2PL - Вы что имеете в виду Static 2PL (это как я Вас понимал, но теперь уже сомневаюсь) или Strict 2PL? И почему Вы жёстко увязываете 2PL с тем, что блокируется?

[vc]

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.

....

- Strict 2PL: заранее ничего не известно, ни набор операций, ни множество объектов затронутых операциями, поэтому блокировки набираются по мере необходимости, и освобождаются только при явном конце транзакции. Все известные мне коммерческие SQL СУБД (включая Sybase) используют эту разновидность 2PL. Ещё раз специально оговариювась, разновидности 2PL не имеют отношения к тому, что конкретно блокируется - объекты, предикаты, ключи, диапазоны и пр. Суть протокола - две фазы работы с любыми блокировками.

Отсюда вопрос:

vc, когда Вы говорите S2PL - Вы что имеете в виду Static 2PL (это как я Вас понимал, но теперь уже сомневаюсь) или Strict 2PL? И почему Вы жёстко увязываете 2PL с тем, что блокируется?

I've always meant Strict 2PL. (as I wrote in the message you've quoted). Sorry for any possible ambiguity, it's entirely my fault.

И почему Вы жёстко увязываете 2PL с тем, что блокируется?

I don't. I've just been saying that Strict 2PL when applied to r/w operations over some data items (the traditional serializabilty subject) guarantees serializable histories for static data sets without requiring any additional mechanism like index range locking.

[tengiz]

I've just been saying that Strict 2PL when applied to r/w operations over some data items (the traditional serializabilty subject) guarantees serializable histories for static data sets without requiring any additional mechanism like index range locking.

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

[tengiz]

И ещё пара слов насчёт того, как старый Sybase (и, соответственно, SQL Server до версии 6.5 включительно) мог обеспечивать строгую сериализуемость без специальных усилий на реализацию предикатных блокировок (когда у этих продуктов ещё не было row/key-level блокировок, а минимальной единицей блокирования была страница). Дело в том, что физическая структура индексов со связами между соседними логическими страницами фактически реализует диапазонные блокировки, когда это необходимо. Протоколы блокировок для serializable, в результате, были гениально простыми, практически не отличались от протокола дла repeatable read и были заметно проще для понимания, чем те, что используются сейчас в современных версиях SQL Server, DB2 или Sybase.

[vc]

I've just been saying that Strict 2PL when applied to r/w operations over some data items (the traditional serializabilty subject) guarantees serializable histories for static data sets without requiring any additional mechanism like index range locking.

vc, но это верно только для практичевски неприменимого подможества SQL операций, о чём у нас идёт речь уже вторую страницу. .

I quite agree that the SQL subset amenable to serialization theory is rather tiny. However, the current serialization theory is the best we have. It has nothing to say about predicates; the seriliazability theorem does not take into consideration phantoms at all, etc. One cannot claim that some locking scheduler has a firm theoretical foundation without reformulating the statement in terms of the rather limited current serializability theory or extending the latter properly to permit a statement like that. Probably I should have said this from the very beginning and just refused to discuss the SQL statements you've presented as intractable by the theory -- we would not have wasted all those pages ;)

Speaking of key range locking, as far as I am aware, there is no formal proof yet that key range locking ensures serilizability (I am pretty sure it does). At least the DB2 key range locking implementation does not comply with Strict 2PL due to the fact that locking a key on delete does not last until commit (which may be OK but there is no proof that it's OK). See Mohan, C., "Concurrency Control and Recovery Methods for B+-Tree Indexes: ARIES/KVL and ARIES/IM".

As to SQL Server 2K, it appears that its REPEATABLE READ is just a faithful implementation of Strict 2PL with all the problems thereof. Its SERIALIZABLE merely adds key range locking if possible or table locking otherwise in order to ensure serializable histories. These last remarks are simply a call for criticism/clarification ;)

[vc]

И ещё пара слов насчёт того, как старый Sybase (и, соответственно, SQL Server до версии 6.5 включительно) мог обеспечивать строгую сериализуемость без специальных усилий на реализацию предикатных блокировок (когда у этих продуктов ещё не было row/key-level блокировок, а минимальной единицей блокирования была страница).

Yeah, that's the one (Sybase) I had to deal with quite a while ago. It was very much serializable being serial most of the time.

[tengiz]

However, the current serialization theory is the best we have. It has nothing to say about predicates; the seriliazability theorem does not take into consideration phantoms at all, etc. One cannot claim that some locking scheduler has a firm theoretical foundation without reformulating the statement in terms of the rather limited current serializability theory or extending the latter properly to permit a statement like that.

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

Позволю себе напомнить, что с точки зрения протокола использующего диапазонные блокировки, ресурсом, на который можно наложить блокировку, кроме собственно значения ключа, является такой полуинтервал - (предыдущее значение ключа, значение ключа], включая и "логически", но не физически удалённые ключи и диапазоны ими порождаемые. Соответственно, объектом манипуляции с точки зрения операций блокирования, чтения и записи тоже является диапазон ключа. Особенностью таких диапазонов является тот факт, что любой индекс содержит как минимум один полуинтервал - (минус бесконечность, максимально возможное значение ключа] в случае когда индекс пуст. Добавление реальных записей в индекс всего лишь дробит исходный полуинтервал. Собственно ключ считается ресурсом, подчинённым диапазону (который подчинён странице, etc.), что сразу сводит такую схему к обычным многоуровневым блокировкам.

Кроме того вот уже почти как 15 лет назад появилось расширение формальной теории на многуровневые транзакции - что по факту и происходит когда используется multigranular locking в сочетании с механизмом "коротких" блокировок aka latches и где "внутренние" транзакции могут быть зафиксированы до того, как это сделает главная транзакция и для некоторых из ресурсов которых возможно немедленное освобождение блокировок. Возможно именно это Вас и смутило в работе Мохана.

[vc]

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

For example, it's assumed that generic predicate locking happens "all at once" for a given predicate while with key range locking a transaction may take a partial set of S index range locks, then collide with another transaction performing a row update, and would need to wait, whilst some other transactions' X lock attempts may wait on the first transaction's S locks gotten so far. As far as I know, there is no rigorous treatment of this scenario as yet.

Кроме того вот уже почти как 15 лет назад появилось расширение формальной теории на многуровневые транзакции - что по факту и происходит когда используется multigranular locking в сочетании с механизмом "коротких" блокировок aka latches и где "внутренние" транзакции могут быть зафиксированы до того, как это сделает главная транзакция и для некоторых из ресурсов которых возможно немедленное освобождение блокировок. Возможно именно это Вас и смутило в работе Мохана.

Yeah, he talks about latching the index leaf node until a insert/delete completes but again in an informal way.

To put it simply, there is no "extended locking theorem" proof that takes into account key range locking explicitly. What we have now is just the simple stuff about Strict 2PL ensuring serializability for static databases. If I am wrong and there is some formal treatment of time-extended index-based locking, please point me to the text.

[tengiz]

vc,

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

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

Как только доберусь до работы - постараюсь найти и выложить ссылки на соответствующие тексты.

P.S. Похоже у Вас уже не осталось сомнений в том, классическая теория полноценно применима к предикатным блокировкам тоже (для чего всего лишь нужно в словаре вместо data item говорить data set defined by a predicate) - судя по последнему сообщению единственная проблема - сводимость неатомарного накопления диапазонных блокировок к предикатным.

[vc]

судя по последнему сообщению единственная проблема - сводимость неатомарного накопления диапазонных блокировок к предикатным.

That's the main problem, yes. Informally, I was convinced when I read Mohan's stuff some years ago that key range locking does what it claims to do. I'd like to see a formal proof. Until I see one, I imagine it's more correct to say that key range locking sometimes produces the same results as straight predicate locking would. It's incorrect to say that key range locking is an implementation of some useful predicate locking functionality subset until there is a formal proof of this statement. I'd also be happy with a proof that key range locking (without any refernce to predicate locking) ensures only serializable schedules. So far I have not seen one.

I've just taken a look at Bernstein's online book and could not find any discussion of PL or key-range locking (unless I missed something which very well may be the case).

My interest, although strong, is purely theoretical since I cannot get too excited with key-range locking that appears to be the sate-of-the-art even today, 20 years after it was conceived. It's a clever idea, no doubt, but its dependency on having indexes diminishes its practicality in too many cases.

Let me also apologize for the usual detour our conversation took. When you posted the original two SQLs, I'd realized that that they cannot be handled as stated by a vanilla Strict 2PL scheduler and I had been trying, several times, to re-state them so that they produced conflicting operations in order to be amenable to Strict 2PL. Now, I do not think it was a correct approach to the problem. As I said before, a correct response should have been that the statements cannot be analyzed within the confines of the traditional serializability theory.

[tengiz]

That's the main problem, yes. Informally, I was convinced when I read Mohan's stuff some years ago that key range locking does what it claims to do. I'd like to see a formal proof. Until I see one, I imagine it's more correct to say that key range locking sometimes produces the same results as straight predicate locking would. It's incorrect to say that key range locking is an implementation of some useful predicate locking functionality subset until there is a formal proof of this statement. I'd also be happy with a proof that key range locking (without any refernce to predicate locking) ensures only serializable schedules. So far I have not seen one.

Вот обещанные ссылки на работы по формализму применяемому для многоуровневых транзакций (где атомарные действия на одном уровне являются на самом деле многошаговой суб-тразнакцией на следующем):

1. A theoretical foundation of multi-level concurrency control by Gerhard Weikum - June 1985 - Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems.

2. A model for concurrency in nested transactions systems - Catriel Beeri, Philip A. Bernstein, Nathan Goodman - April 1989 - Journal of the ACM (JACM), Volume 36 Issue 2.

Работу Papadimitriou я пока не нашёл, но попробую ещё поискать. Также Вам может быть интересно найти вот такую статью с глубокомысленным названием:

Bernstein, P.A., N. Goodman, and M.Y. Lai, "Laying Phantoms to Rest (by Understanding the Interactions Between Schedulers and Translators in a Database System)," Proc. 1981 IEEE COMPSAC Conf., Oct. 1981.

I've just taken a look at Bernstein's online book and could not find any discussion of PL or key-range locking (unless I missed something which very well may be the case).

Если речь идёт о Concurrency Control and Recovery in Database Systems - то я думаю, что требовать слишком многого от университеского учебника (пусть даже и одного из самых лучших) не стоит. Тем не менее, предикатные блокировки там обсуждаются, а также и реализация их частного случая посредством индексных (не диапазонных) блокировок.

My interest, although strong, is purely theoretical since I cannot get too excited with key-range locking that appears to be the sate-of-the-art even today, 20 years after it was conceived. It's a clever idea, no doubt, but its dependency on having indexes diminishes its practicality in too many cases.

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

Let me also apologize for the usual detour our conversation took. When you posted the original two SQLs, I'd realized that that they cannot be handled as stated by a vanilla Strict 2PL scheduler and I had been trying, several times, to re-state them so that they produced conflicting operations in order to be amenable to Strict 2PL. Now, I do not think it was a correct approach to the problem. As I said before, a correct response should have been that the statements cannot be analyzed within the confines of the traditional serializability theory.

Давайте всё же попробуем эти примеры ещё раз препарировать: vanilla Strict 2PL scheduler прекрасно позволяет провести анализ любых сценариев. Именно это я пытался сделать, подразумевая по умолчанию, что мы друг друга понимаем. Единственное уточнение - как я уже говорил - замените все упоминания data item/object на data set defined by a predicate во всех операциях (read, write, lock), обобщите понятие конфликта на наличие пересечения data sets defined by predicates, сведите SQL insert/delete/update к data set write / data set state change - больше ничего делать не нужно. Проблема аккуратного учёта фатномов волшебным образом испарится. Формальная часть с доказательствами корректности алгоритмов 2PL без циклов абсолютно не менятся при этой замене.

[Dmitry67]

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

Интересно что это не афишируется BOL и об этом вообще мало кто из практиков знает

Многие маленькие таблицы не индексируют 'потому что так все равно мало записей'
Исли ьаблица меняется то... особенно полезно индексировать пустые таблицы

[tengiz]

Интересно что это не афишируется BOL и об этом вообще мало кто из практиков знает

"А Вас, Штирлиц, я попрошу остаться..." (с)

Похоже, что мы Вас и Вашу контору вычислили . Наблюдательный alex_127 раскопал в отчёте троих наших коллег, съездивших на SIGMOD в Париж, подозрительно знакомые "вести с полей", а точнее вопросы и пожелания троих представителей некоего тамошнего ISV...

Что касается BOL и афиширования - если я правильно помню, есть несколько публичных whitepapers на тему оптимизации приложений на SQL Server, где эта тема подробно разбирается для любознательных практиков. Другое дело - и с этим я полностью согласен, хотя наши попытки что-то изменить пока не увенчались успехом, - информация и BOL и вообще online документация организованы крайне неудобно.

[katit]

информация и BOL и вообще online документация организованы крайне неудобно.

<off>
BOL организован лучше всего осталього (IMO)
Я-бы сказал что очень удобно
</off>

[tengiz]

BOL организован лучше всего осталього (IMO)

То, что остальное ещё хуже, чем BOL я вполне могу согласиться

Вы когда-нибудь видели документацию по SQL Server 6.0/6.5, а ещё лучше, документацию по версии 4.21? Так вот, по сравнению с теми книгами то что сейчас - это просто набор статей сваленных в кучу и кое-как связанных ссылками. После внимательного ознакомления в течение длительного времени вполне можно с этим освоиться, но система, согласно которой структурирован материал в BOL, настолько перпедникулярна моей логике, что я до сих пор тупо смотрю в оглавлене не зная куда точно мне нужно ткнуться, чтобы найти ответы на время от времени возникающие у меня вопросы на темы, напрямую не связанные с функциональностью сервера, за которую я непосредственно отвечаю. В итоге мне проще пройтись по коридорам, найти нужного мне человека или группу людей и выпытать у них как точно работает та или иная фича.

[vc]

[

My interest, although strong, is purely theoretical since I cannot get too excited with key-range locking that appears to be the sate-of-the-art even today, 20 years after it was conceived. It's a clever idea, no doubt, but its dependency on having indexes diminishes its practicality in too many cases.

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

Well, minimalism is a good point but you create indexes when you want to improve performance. With key-range locking you'd want indexes on all possible predicate columns even though you know that full-table scan with a given predicate is preferable, These 'unnecessary' indexes will impact write performance for obvious reasons. But let's skip this one as the interesting stuff goes below:

Давайте всё же попробуем эти примеры ещё раз препарировать: vanilla Strict 2PL scheduler прекрасно позволяет провести анализ любых сценариев. Именно это я пытался сделать, подразумевая по умолчанию, что мы друг друга понимаем. Единственное уточнение - как я уже говорил - замените все упоминания data item/object на data set defined by a predicate во всех операциях (read, write, lock), обобщите понятие конфликта на наличие пересечения data sets defined by predicates, сведите SQL insert/delete/update к data set write / data set state change - больше ничего делать не нужно. Проблема аккуратного учёта фатномов волшебным образом испарится. Формальная часть с доказательствами корректности алгоритмов 2PL без циклов абсолютно не менятся при этой замене.

OK. Let's do it. I think you are treating the original serializability theory too liberally and I am not sure one can do that.

As I said before, the vocabulary contains 'r', 'w', 'precede', a conflict matrix and nothing more. 'r'/'w' should be atomic. Now, just a couple of problems with your extension:

1. Substituting subsets defined by predicates for data items. How do you propose to ensure atomicity for say a 'read' over a subset defined by a predicate ?

2. Generalizing data item conflicts to subset intersection.. Well, you surely can see that this leads directly to predicate locking, "a rose by any other name would smell as sweet" dont you agree, (p1&p2 == true) that's the very definition of a predicate conflict. When we have predicate locking we are gods. But we don't so we are not.

Please respond to these two questions/objections and I'll tackle other points later as they depend on your answer.

Thanks.

[tengiz]

1. Substituting subsets defined by predicates for data items. How do you propose to ensure atomicity for say a 'read' over a subset defined by a predicate ?

Атомарность отдельных r/w для анализа сериализуемости не нужна (мы же не собираемся анализиовать recoverability?). Это автоматически обеспечивается протоколом блокирования, если мы предполагаем, что блокировка накладывается до того, как выполнятеся операция r/w.

2. Generalizing data item conflicts to subset intersection.. Well, you surely can see that this leads directly to predicate locking, "a rose by any other name would smell as sweet" dont you agree, (p1&p2 == true) that's the very definition of a predicate conflict. When we have predicate locking we are gods. But we don't so we are not.

vc - я опять не понимаю - мы что обсуждаем? На каком уровне абстракции? Способность классической теоретической модели быть адекватной абстрактной задаче анализа сериализуемости, (тогда наличие практически пригодной с точки зрения производительности и реализумости схемы предикатных блокировок абсолютно неважно)? И, соответственно, показать (или опровергнуть), что абстрактный механизм 2PL в состоянии гарантировать сериализуемость?

Или пытаемся проанализировать как реальные протоколы реальных СУБД реально оказываются в состоянии обеспечить true serializable? В таком случае я бы попросил Вас сначала ознакомиться с концепцией многоуровневых транзакций, о которых мы уже некоторое время говорим ( SQL Server и DB2 это активнейшим образом используют в том числе и для recoverability.) Имеется формальный аналитический аппарат, который позволяет разбирать и доказывать корректность сценариев, где top nested action не является атомарным, а сам является многошаговой транзакцией.

Кроме того, нам придётся затратить время на хотя бы поверхностное ознакомление с дополнительной концепцией - multigranular locking и доказательствами её корректности. Несколькими сообщениями выше я писал, что диапазонные блокировки сводятся к multigranular locking - если Вы убедитесь, что multigranular two phase locking работает правильно (способен гарантировать true serializable), то дальше останутся только вопросы по тому, как точно модель диапазонных блокировок ложится на MGL.

Вы действительно хотите настолько подробно с этим разбираться прямо здесь, на Привете?

[vc]

<added>

vc wrote:
1. Substituting subsets defined by predicates for data items. How do you propose to ensure atomicity for say a 'read' over a subset defined by a predicate ?

Атомарность отдельных r/w для анализа сериализуемости не нужна (мы же не собираемся анализиовать recoverability?). Это автоматически обеспечивается протоколом блокирования, если мы предполагаем, что блокировка накладывается до того, как выполнятеся операция r/w.

OK, fair enough, I agree.


</added>

vc - я опять не понимаю - мы что обсуждаем? На каком уровне абстракции? Способность классической теоретической модели быть адекватной абстрактной задаче анализа сериализуемости, (тогда наличие практически пригодной с точки зрения производительности и реализумости схемы предикатных блокировок абсолютно неважно)? И, соответственно, показать (или опровергнуть), что абстрактный механизм 2PL в состоянии гарантировать сериализуемость?

I am objecting to your rather unsound extension of the starndard serializability theory. When you start talking about subset conflicts, you are essentially using predicate locking metaphor which I find a little disingenuous. Let's use the assumption that we do not have predicate locking and we do not have key range locking. Let's reason from there. As soon as we introduce either, there is nothing to discuss as there is no problem to solve any more, either machanism will handle it.

Или пытаемся проанализировать как реальные протоколы реальных СУБД реально оказываются в состоянии обеспечить true serializable? В таком случае я бы попросил Вас сначала ознакомиться с концепцией многоуровневых транзакций, о которых мы уже некоторое время говорим ( SQL Server и DB2 это активнейшим образом используют в том числе и для recoverability.) Имеется формальный аналитический аппарат, который позволяет разбирать и доказывать корректность сценариев, где top nested action не является атомарным, а сам является многошаговой транзакцией.

Кроме того, нам придётся затратить время на хотя бы поверхностное ознакомление с дополнительной концепцией - multigranular locking и доказательствами её корректности. Несколькими сообщениями выше я писал, что диапазонные блокировки сводятся к multigranular locking - если Вы убедитесь, что multigranular two phase locking работает правильно (способен гарантировать true serializable), то дальше останутся только вопросы по тому, как точно модель диапазонных блокировок ложится на MGL.

Вы действительно хотите настолько подробно с этим разбираться прямо здесь, на Привете?

No need to do that -- I know all this stuff already. Moreover, MGL is irrelevant at this level of abstraction -- it's just an implementation detail. Let's talk about solving our little quizz within the standard serializability theory, but without relying on tricks like PL or key-range locking.


Thanks.

[tengiz]

I am objecting to your rather unsound extension of the starndard serializability theory. When you start talking about subset conflicts, you are essentially using predicate locking metaphor which I find a little disingenuous. Let's use the assumption that we do not have predicate locking and we do not have key range locking. Let's reason from there. As soon as we introduce either, there is nothing to discuss as there is no problem to solve any more, either machanism will handle it...

...Let's talk about solving our little quizz within the standard serializability theory, but without relying on tricks like PL or key-range locking.

Тогда я думаю что обсуждать нам больше нечего - у нас наступило долгожданное взаимопонимание - без предикатных блокировок реализованных в любом виде, 2PL в общем случае не работает и пригодна только для специальных случаев, давно потерявших актуальность. А как только мы вводим в арсенал предикатные блокировки (несмотря на остутствие качественной, в смысле высокопроизводительной и разумной по ресурсам, их реализации в прямом виде - блокировки диапазонов индексов в любом виде не в счёт) или, что абсолютно эквивалентно, расширяем определение атомарного объекта манипуляции до множеств объектов, заданных предикатами - то всё становится на свои места. Зачем только намеренно сужать область действия модели, выбрасывая из неё существенную часть, я, честно говоря, не понимаю. Заведомо понятно, что сценарии где возможны любые виды фантомов не могут быть гарантированно правильно проанализированы таким аппаратом.

Может, я просто зевнул, о каком точно quizz мы говорим?

[Dmitry67]

Похоже, что мы Вас и Вашу контору вычислили . Наблюдательный alex_127 раскопал в отчёте троих наших коллег, съездивших на SIGMOD в Париж, подозрительно знакомые "вести с полей", а точнее вопросы и пожелания троих представителей некоего тамошнего ISV...

Я раскрыт ! глотает таблетку цианистого калия

Что касается BOL, то я там оглавлением вообще не пользуюсь, сразу search, а потом троешься в выпавших топиках