Why Sybase/SQL Server/DB2 SERIALIZABLE is not serializable

[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, а потом троешься в выпавших топиках

[vc]

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 мы говорим?

Yes, the funny thing is that our 'disagreement' stems from the fact that I've been trying to stay within the confines of the standard serializability theory (r/w over a possibly infinite static set of data items with conflicts defined over those two operations) whilst you, implicitly, extended the data items to subsets and conflicts between the latter. I was a bit surprised by the whole discussion as I'd been pretty sure you knew about the standard serializability limitations. As usual, I can blame only my poor writing skills for the misunderstanding. Sorry and thank you..