Megano Blog

Advanced Техники Помогающие Избегать и Находить Deadlocks в .NET Приложениях.

2013-08-02T06:20:00.000-07:00

Advanced Техники Помогающие Избегать и Находить Deadlocks в .NET Приложениях.

Оригинал статьи: http://msdn.microsoft.com/ru-ru/magazine/cc163618%28en-us%29.aspx

Автор статьи: Joe Duffy

Автор перевода: Александр Кобелев

Прочитав эту статью, вы разберетесь в причинах возникновения deadlock, узнаете, что они бывают разных типов, и в самом конце будет небольшая пошаговая инструкция, пройдя все шаги которой, вы научитесь находить deadlock в живых .net приложениях.

За основу взята статья Advanced Techniques To Avoid And Detect Deadlocks In .NET Apps. Однако, переведена лишь ее теоритическая часть, оставшаяся часть (использующая C++ и CLR hosting API) доступна в оригинальной статье, вместо нее, вам будет предложена пошаговая инструкция по обнаружению deadlocks без использования C++.

Так же, в тексте статьи вы найдете ссылки на справочные ресурсы, а вот в таких выделенных блоках вы встретите мои дополнительные пояснения.

Александр Кобелев.

Эта статья рассматривает:

Причины возникновения deadlocks
Методику lock leveling, помогающую избегать deadlocks
Обнаружение deadlocks и их устранение
Обзор CLR hosting API для подключения и обнаружения deadlocks

Для статьи доступен исходный код: Deadlocks.exe(188 KB) (оригинальный исходный код разработанный под Visual Studio 2005)

Зависшее приложение это одна из самых неприятных ситуаций, с которой пользователь может столкнуться. Их ужасно трудно найти при тестировании перед поставкой приложения, и еще труднее отлаживать после развертывания приложения. В отличие от необработанного исключения, зависание не создает crash dump, и не приводит к срабатыванию специальной логики (например, уведомление разработчика о произошедшей ошибке). Пользователи часто завершают процессы зависших приложений, до того как вы будете в силах получить дамп памяти, для последующего анализа и локализации проблемы.

Зависания могут быть как периодические, так и постоянные, они могут возникнуть как результат медленных Input/Output операций, или при обработке сложных / долгих алгоритмов, так и при взаимоисключающем доступе к ресурсу. В любом случае это снижает отзывчивость приложения и может привести к подвисаниям. К примеру: код, который блокирует выполнение GUI потока, может помешать текущей обработке пользовательского ввода и обработке системных событий, в результате приложение подвиснет и система отобразит его как "Not Responding". Даже программы без графического интерфейса могут страдать от проблем отзывчивости, при использовании общих ресурсов или при выполнении Inter-Thread, Inter-Process или сетевых взаимодействий. Самый худший тип зависания - когда приложение подвисает намертво и никогда не возобновит своей работы, другими словами deadlock.

Разработка приложений с большой конкуренцией, используя стандартные Windows® средства - потоки и блокировки, это задача, гораздо труднее, чем может показаться на первый взгляд. Стоит всего лишь забыть заблокировать данные доступные нескольким потокам и это может привести к необработанному исключению (в лучшем случае), или к повреждению данных.

Поврежденные данные это не только не читаемые данные, а так же неверные, ложные данные. Рассмотрим вымышленный пример: предположим, мы производим пуск ракеты, со спутниками "Глонасс" на борту.
В первой ступени у ракеты находится 3 двигателя, для отстрела ступени нужно, чтобы все двигатели полностью выработали свое горючее. Когда двигатель вырабатывает горючее, он увеличивает общий счетчик отключившихся двигателей на единицу, изначально счетчик равен нулю. Отстрел ступени происходит как только счетчик достигает значения 3. Счетчик в нашем случае не блокируется, а потоки, которые следят за состоянием двигателей, используют метод Increment.
По поводу методов Increment (i++) и Decrement (i--) в MSDN можно найти следующую информацию:
Методы Increment (i++) и Decrement (i--) увеличивают или уменьшают значение переменной и сохраняют результат в одной операции. На большинстве компьютеров увеличение значения переменной не является атомарной операцией, а требует следующих шагов:

Загрузить значение из переменной экземпляра в регистр.
Увеличить или уменьшить значение.
Сохранить значение в переменной экземпляра.

http://msdn.microsoft.com/ru-ru/library/system.threading.interlocked.aspx
Исходя из вышесказанного, предположим, что первый двигатель отработал чуть раньше других и успешно увеличил значение счетчика на 1 и теперь он равен 1. Двигатели 2 и 3 одновременно выработали свое горючее:

Поток двигателя 2 Загружает значение из счетчика(равное 1) в регистр.
Поток двигателя 2 Увеличивает значение на 1.
Планировщик потоков прерывает работу потока двигателя 2 и отдает управление потоку двигателя 3 (Второй поток не успевает сохранить измененное значение счетчика)
Поток двигателя 3 загружает значение из счетчика (равное 1, так как второй поток не успел сохранить измененное значение) в регистр.
Поток двигателя 3 Увеличивает значение на 1.
Поток двигателя 3 сохраняет значение(равное 2) в переменной счетчика.
Планировщик потоков возвращает управление потоку двигателя 2
Поток двигателя 2 возвращается к тому моменту, где его прервал планировщик потоков и сохраняет значение (равное 2) в переменной счетчика.
Все двигатели выработали свое горючее, данные счетчика повреждены (ложны), счетчик равен 2, отстрела ступени не происходит, ракета падает...

Существует компромисс между coarse-grained locking (крупнозернистость, http://design-pattern.ru/patterns/coarse-grained-lock.html , плюсы: простота и стойкость данных, минусы: снижает возможность применения параллелизма) и fine-grained locking (мелкозернистость, плюсы: высокая возможность параллелизма; минусы: требует более продуманной архитектуры, большое количество блокировок, больше предрасположено к появлению ошибок). Сегменты кода различной "зернистости", каждый раз, при получении и освобождении блокировок склонны взаимодействовать друг с другом непредсказуемым образом. Если ваша система ничего не делает для сдерживания deadlocks, то даже самые незначительные ошибки, при проектировании блокировок, склонны мешать взаимодействию внутри программы.

Сегодняшние модели программирования, требуют, чтобы программист думал о том, что в течение выполнения программы, методы могут выполняться не по порядку. Когда программа начинает вести себя непредсказуемо, то бывает чрезвычайно сложно воспроизвести шаги, приведшие к инциденту. Deadlocks, более заметны, чем гонка методов (в простейшем случае программа просто повиснет), но так же сложны в локализации проблемы и в устранении. Вы можете найти deadlocks в процессе выполнения тестов, но наиболее вероятно, что большинство из них будет дремать до поставки продукта, и впоследствии будут "радовать" ничего не подозревающего пользователя.

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

Deadlocks 101

Deadlock возникает, когда несколько конкурирующих потоков ждут один другого для возобновления своей работы. Если это звучит как парадокс, то так оно и есть.

К примеру:

Есть 2 общих ресурса А и В
Есть 2 потока, которым для работы нужны оба ресурса одновременно
Поток 1 запустился и успел захватить ресурс А
Поток 2 запустился и успел захватить ресурс В
Поток 1 не может продолжать своей работы, так как ресурс В ему в данный момент не доступен
Поток 1 не отпуская ресурс А засыпает, в ожидании освобождения ресурса В
Поток 2 не может продолжать своей работы, так как ресурс А ему в данный момент не доступен
Поток 2 не отпуская ресурс В засыпает, в ожидании освобождения ресурса А
Deadlock!

Пример кода (deadlock почти в 100% случаях). Когда вызывается метод Thread.Start() мы всего лишь уведомляем систему что хотим запустить поток как можно скорее, теоретически, второй поток может запуститься уже после того, как первый закончит свою работу.

using System;

using System.Threading;

namespace SimpleDeadlock

{

class Program

{

static object a = new object();

static object b = new object();

public static void MethodOne()

{

lock (a)

{

Thread.Sleep(100);

lock (b)

{

Console.WriteLine("Никогда не будет выведено на консоль (поток 1)");

}

public static void MethodTwo()

{

lock (b)

{

Thread.Sleep(100);

lock (a)

{

Console.WriteLine("Никогда не будет выведено на консоль (поток 2)");

}

static void Main(string[] args)

{

ThreadStart entryPointThread1 = MethodOne;

ThreadStart entryPointThread2 = MethodTwo;

Thread one = new Thread(MethodOne);

Thread two = new Thread(MethodTwo);

one.Start();

two.Start();

Console.WriteLine("Основной поток закончил работу.");

}

Существует четыре основных условия, которые должны совпасть, чтобы произошел deadlock:

Система должна поддерживать Mutual Exclusion (Взаимоисключение)

http://en.wikipedia.org/wiki/Mutual_exclusion

Когда один поток завладел общим ресурсом, другой поток не может завладеть им. Это относится не только к большинству критических секций, но так же и к GUI в Windows. Каждое окно принадлежит одному потоку, который несет полную ответственность за обработку входящих сообщений. Ошибки с Mutual Exclusion при проектировании, могут привести к потере отзывчивости приложения (в лучшем случае) или к deadlock.

Поток уже владеющий, каким то ресурсом, должен иметь возможность впадать в неограниченное ожидание. Например, когда поток, вошедший в критическую секцию, имеет возможность завладеть еще одной критической секцией, и если она занята - впасть в ожидание. Это вполне ожидаемый результат, если вторая критическая секция удерживается другим потоком.

Ресурсы не могут быть насильно забраны от их текущих владельцев. Однако, в некоторых ситуациях это возможно, когда ссора за ресурс была замечена системой. Например, в сложных системах управления базами данных (СУБД). Но это не выход для блокируемых объектов в управляемом коде.

Условие замкнутого ожидания. Замкнутое ожидание происходит в случае, если цепочка из двух или более потоков ждут освобождения ресурсов заблокированных потоками, находящимися в этой цепочке. Также это относится к одному единственному потоку, если он пытается заблокировать ресурс, который невозможно повторно заблокировать, в этом случае поток сам себе создаст deadlock. Однако большинство ресурсов можно заблокировать повторно, что ликвидирует возможность deadlock в одном потоке.

Любой программист, работавший с пессимистичными алгоритмами ( http://ru.wikipedia.org/wiki/Блокировка_(СУБД) ) должен понимать как происходят deadlocks. Если пессимистичный алгоритм при попытке доступа обнаруживает, что ресурс уже занят, то он переходит в ожидание, и ждет до тех пор, пока ресурс не станет свободным (к примеру, блокировки). В сравнении с оптимистичными алгоритмами, пытающимися выполнить работу с риском возникновения разногласия данных, которые будут выявлены позже, например, при фиксации транзакции. Пессимистичный алгоритм много легче реализовать, потому что он более распространен и уже встроен в платформы, по сравнению с оптимистичными технологиями, как правило пессимистичный алгоритм принимает форму монитора (в C# конструкция lock; Visual Basic® SyncLock) mutex ( http://ru.wikipedia.org/wiki/Мьютекс ) или Win32® CRITICAL_SECTION.

Lock-free ( http://ru.wikipedia.org/wiki/Неблокирующая_синхронизация ) алгоритмы, способные обнаружить и реагировать на конкуренцию за ресурсы, являются довольно распространенными для программного обеспечения системного уровня. Эти алгоритмы часто избегают совместного входа в критическую секцию, выбирая livelock вместо deadlock. Livelock тоже представляет проблему для параллельного кода, однако она вызвана fine-grained конкурентностью. Результат Livelock - программа работает, но вхолостую. Проиллюстрировать эффект можно следующим образом - Двое встречаются лицом к лицу. Каждый из них пытается обойти другого, но сдвигаются постоянно в одну и ту же сторону, и никто из них не может пройти вперед.

Следующая иллюстрация демонстрирует, как может произойти deadlock, вообразите последовательность событий:

Поток 1 блокирует ресурс А
Поток 2 блокирует ресурс В
Поток 1 пытается заблокировать ресурс В, но он уже заблокирован потоком 2 и поток 1 впадает в ожидание, пока ресурс В не освободится
Поток 2 пытается заблокировать ресурс А, но он уже заблокирован потоком 1 и поток 2 впадает в ожидание, пока ресурс А не освободится

В этом случае потоки заблокируются и никогда не проснутся. Следующий C# код демонстрирует данную ситуацию:

object lockA = new object();

object lockB = new object();

//Thread 1 void t1() { lock (lockA) { lock (lockB) { /* ... */ } } }

//Thread 2 void t2() { lock (lockB) { lock (lockA) { /* ... */ } } }

Иллюстрация 2 демонстрирует 6 возможных вариантов гонки потоков между двумя потоками. Только в 2 случаях (1 и 4) не наблюдается deadlock. Очень заманчиво сделать вывод, что deadlock произойдет два раза из трех (по тому, что 4 варианта из 6 ведут к deadlock), но это не так, почти всегда будет срабатывать первый вариант, следующим по статистике четвертый и лишь за тем 2,3,5,6 так как временное окно, необходимое для блокировки сразу двух объектов очень мало (в начале LockA и сразу за этим, без какой-либо другой работы, захватить LockB, или наоборот LockB и сразу же LockA), и вероятность того что потоки стартуют одновременно тоже очень мала.

Не заботясь о статистике, если вы будете писать код, как представлено выше, ваша программа всегда будет балансировать на острие ножа. Рано или поздно программа сработает по одному из четырех сценариев ведущими к deadlock, это будет возможно, к примеру из за нового оборудования, которое приобрел заказчик (а вы никогда не тестировали свой продукт с этим оборудованием) или просто статистическая рулетка выдаст один из четырех вариантов.

В приведенном выше примере deadlock достаточно легко идентифицировать и исправить, для этого нужно переписать методы t1 и t2 так, чтобы они захватывали и освобождали блокировки в одном и том же порядке. К примеру с начала всегда захватывается A и лишь за тем B:

object lockA = new object();

object lockB = new object();

//Thread 1 void t1() { lock (lockA) { lock (lockB) { /* ... */ } } }

//Thread 2 void t2() { lock (lockA) { lock (lockB) { /* ... */ } } }

Или наоборот:

object lockA = new object();

object lockB = new object();

//Thread 1 void t1() { lock (lockB) { lock (lockA) { /* ... */ } } }

//Thread 2 void t2() { lock (lockB) { lock (lockA) { /* ... */ } } }

Таким образом, мы избавляемся от так называемого «deadly embrace» (смертельное объятие), если всегда захватывать и освобождать ресурсы в одном и том же порядке - deadlock невозможен. Но давайте рассмотрим вариант метода, где возможен deadlock, но он не так очевиден на первый взгляд:

void Transfer(Account a, Account b, decimal amount)

{

lock (a)

{

lock (b)

{

if (a.Balance < amount) throw new InsufficientFundsException();

a.Balance -= amount; b.Balance += amount;

}

Предположим, кто то пытается перевести $500 с аккаунта #1234 на аккаунт #5678 и в это же время, кто-то другой пытается перевести $1000 с аккаунта #5678 на аккаунт #1234, в этом случае появляются все условия для создания deadlock. Такая неоднозначность с аргументами (как показано выше), когда множество потоков могут передавать одни те же объекты в разные аргументы, может вызвать большую головную боль. К сожалению эта ситуация является очень распространенной, вызовы виртуальных методов, реализованных в пользовательском коде, так же могут произвести серию вызовов, которая может обзавестись блокировками в непредсказуемом порядке. Непредусмотренная комбинация блокировок постоянно рискует появлением deadlock.

Несколько Коварных Примеров Deadlock

Риск возникновения deadlock не ограничивается только взаимоисключающими критическими секциями. Есть и более коварные пути, на которых deadlock может возникнуть в вашей программе. Soft deadlock – когда кажется, что в вашем приложении произошел deadlock, но на самом деле программа просто застряла на выполнении операции с большим временем ожидания или возникли проблемы, мешающие продолжению работы метода. Например, интенсивные алгоритмы, выполняемые в GUI потоке, могут привести к полной потери отзывчивости приложения. В данном случае использования пула потоков было бы лучшим выбором (предпочтительно использовать новый компонент BackgroundWorker появившийся в .NET Framework 2.0).

Очень важно понимание, как скажется на производительности вызов того или иного метода в вашей программе, но на практике это оказывается очень сложным. Операция, которая вызывает другую, чья производительность имеет широкий диапазон времени выполнения, может привести к непредсказуемым задержкам, блокировкам и нагрузкам на процессор. Ситуация становится хуже, когда вызывающий метод до этого заблокировал какой либо общий ресурс, в этом случае, даже очень быстрые методы, в которых предусмотрен доступ до этого ресурса, будут ждать его освобождения. Части вашего приложения, имеющие превосходную производительность в обычных сценариях, могут ее лишиться, к примеру, если что либо произойдет в системном окружении. Сетевой обмен данными – прекрасный пример, обычно он имеет прекрасную производительность, но как только сетевого канала начинает нехватать для всех приложений запущенных на компьютере или сетевое подключение становится недоступным, производительность методов, использующих сетевой обмен, резко падает. Если вы разрабатывали приложения, использующие сетевой обмен, вы наверняка очень тщательно тестировали этот момент, к примеру, как ваше приложение поведет себя, когда вы отключите сетевой кабель от компьютера.

Когда ваш код выполняется в single-threaded apartment (STA http://www.introligator.org/articles/3/84 http://www.rsdn.ru/article/com/apartmnt.xml ) это эквивалентно эксклюзивной блокировке. Только один поток может обновлять GUI окна или выполнять код внутри STA апартамента. Такие потоки владеют очередью сообщений, в которую кладут информацию другие части приложения для последующей обработки. GUI используют эту очередь для получения информации, например запрос на перерисовку или запрос на закрытие окна. COM прокси используют очередь сообщений для вызова методов объектов, принадлежащих апартаментам. Любой код, выполняющийся в STA, ответственен за постоянный сбор и выполнение запросов из очереди сообщений, в противном случае очередь может засориться, что приведет к потере оперативности. В терминах Win32 это означает использование MsgWaitForSingleObject, MsgWaitForMultipleObjects (и их эквиваленты) или CoWaitForMultipleHandles APIs. Другие варианты, такие как WaitForSingleObject или WaitForMultipleObjects (и их эквиваленты) не будут прокачивать входящие сообщения.

Другими словами STA “lock” может быть освобожден только прокачкой очереди сообщений. Приложения, выполняющие операции с непредсказуемой производительностью в GUI потоке, без прокачки сообщений (как было замечено ранее), могут легко привести к deadlock. Хорошо написанные программы производят такую долгую обработку либо где то в другом месте, либо прокачивают сообщения каждый раз перед блокировкой, чтобы избежать проблем с отзывчивостью. К счастью CLR в управляемом коде прокачивает сообщения для вас (через вызовы Monitor.Enter, WaitHandle.WaitOne, FileStream.EndRead, Thread.Join, и так далее) помогая смягчить эту проблему.

Рассмотрим классический пример STA-induced deadlock. Поток работающий в STA апартаментах генерирует большое количество объектов и автоматически для них генерируются Runtime Callable Wrappers (RCWs http://msdn.microsoft.com/ru-ru/library/8bwh56xe.aspx ). Конечно RCWs должны быть утилизированы когда они становятся недоступны, в противном случае произойдет утечка памяти. Но утилизирующий поток CLR так же вынужден использовать прокси к STA чтобы освободить RCWs. Если STA не прокачивает очередь сообщений (к примеру поток заблокирован методами WaitForSingleObject или WaitForMultipleObjects ), то утилизирующий поток застрянет. Если STA перестанет прокачивать, это скажется на утилизирующем потоке, он будет замедляться и медленно наращивать количество ресурсов, которое ему необходимо утилизировать. Это в свою очередь может привести к out-of-memory и приложение упадет, или оно может перезапуститься (например, ASP.Net). Очевидно, что оба этих результата неудовлетворительны.

Фреймворки высокого уровня, такие как Windows Forms, Windows Presentation Foundation и COM скрывают от пользователя большую часть сложностей при работе с STA, однако они все же могут ошибиться и повести себя непредсказуемо, deadlock один из возможных результатов. Такие ошибки могут легко проскочить через этап тестирования приложения и возникнуть только при стрессовых нагрузках.

Различные типы deadlock, к сожалению, требуют различных методов борьбы. Остальная часть статьи будет посвящена исключительно deadlock критической секции. В CLR 2.0 появилась полезная утилита для отлавливания и отладки проблем связанных с STA. Новый Managed Debugging Assistant (MDA), ContextSwitchDeadlock был создан для отслеживания deadlocks включая межапартаментные переходы (cross-Apartment transitions). Если переход занимает более 60 секунд, CLR предполагает что произошел deadlock и натравливает на него MDA. Для более точной информации как включить и работать с MDA смотрите MSDN документацию.

Существует две основные стратегии, полезные при работе с deadlock критической секции.

Избежание взаимоблокировок. Если устранить всего одно из четырех условий возникновения deadlock (описанных выше), deadlock никогда не произойдет. Например, вы можете не блокировать ресурсы (как правило, это не представляется возможным), или устранить круговое ожидание. Это требует некой структурированной дисциплины, которая, к сожалению, может добавить множество накладных расходов при создании параллельного программного обеспечения.

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

Многие разработчики знают о возникновении возможности deadlock на теоретическом уровне, но очень не многие знают, как реально с ними бороться. Давайте взглянем на некоторые решения, которые попадают в обе описанные выше категории.

Избежание deadlocks с техникой Lock Leveling

Довольно распространенный подход для борьбы с deadlock в больших программных системах является техника под названием Lock Leveling (так же известная как Lock Hierarchy или Lock Ordering). Основная стратегия данного подхода заключается в том, что все блокировки имеют некий числовой уровень, так же этот числовой уровень зависит от архитектурного слоя, и после приобретения потоком блокировки он может блокировать ресурсы только более низкого уровня. Например, мы можем назначить общему ресурсу А уровень 10, а общему ресурсу Б уровень 5. Поток, вполне легально может сначала захватить ресурс А, а затем ресурс Б, но если в обратном порядке (так как уровень ресурса А (10) больше чем уровень ресурса Б (5)) произойдет исключение. Такая методика исключает возможность возникновения deadlock

Большое количество современных программных систем используют архитектурные слои (GUI, Business Logic, DAL).

И каждый нижележащий слой ничего не должен знать о вышележащем (к примеру, DAL ничего не знает о Business Logic и не может запускать его методов и так далее, но бывает это правило нарушается). Для того чтобы воспользоваться методикой Lock Leveling нам необходимо так же разделить на логические слои и числовые уровни блокировок, с верху вниз. Предположим в нашем приложении, должно хватить десяти заблокированных ресурсов, на слой, в одном (любом) методе, для его успешного выполнения. GUI - самый верхний слой, его числовые уровни блокировок будут в диапазоне от 30 до 21, Business Logic 20-11, DAL 10-1.

namespace GUI

{

class GuiClass

{

static LeveledLock _lockA = new LeveledLock(30);

static LeveledLock _lockB = new LeveledLock(29);

public void One()

{

using (_lockA.Enter())

{

using (_lockB.Enter())

{

/* -- body -- */

}

static LeveledLock _lockC = new LeveledLock(30);

public void Two()

{

using (_lockC.Enter())

{

One();// Exception

}

В случае вызова метода One все пройдет хорошо, так как в начале, блокируется объект с уровнем 30, а затем с уровнем 29. В случае вызова метода Two произойдет исключение, так как вначале блокируется объект с уровнем 30, следующим же заблокированным объектом, может быть только объект с уровнем 29 и ниже, а в данном случае происходит попытка вызова метода One, который вновь блокирует объект с уровнем 30.

Так же, эта методика повышает архитектурную целостность приложения, к примеру, затрудняет вызовы методов из нижележащего слоя в вышележащих. Предположим, что метод в DAL блокирует ресурс (уровень блокировки в DAL начинается с 10) и после пытается, в нарушении архитектуры, вызвать метод в Business Logic, который в свою очередь тоже блокирует какой либо ресурс (предположим с уровнем блокировки 20), в этом случае произойдет исключение.

Конечно, существуют различные варианты реализации Lock Leveling, в коде к статье (доступен для скачивания) представлен один из них, реализованный на C#. Использование одного экземпляра класса LeveledLock соответствует одной конструкции lock, работа с ним очень похожа на использование методов Enter и Exit класса System.Threading.Monitor. Во время создания экземпляра LeveledLock выставляется его числовой уровень блокировки.

LeveledLock lockA = new LeveledLock(10); LeveledLock lockB = new LeveledLock(5);

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

Реализация методов Enter и Exit класса LeveledLock, происходит с участием вызовов соответствующих методов приватного экземпляра System.Threading.Monitor. Также, с помощью Thread Local Storage (TLS) отслеживается последняя блокировка приобретенная потоком, благодаря этому обеспечивается проверка иерархии блокировок. Таким образом, можно полностью исключить возможность, приобретения блокировок в неправильном порядке. Удаляя возможность замкнутого ожидания, благодаря этому, удаляется любой шанс возникновения deadlock.

Thread 1 void t1() { using (lockA.Enter()) { using (lockB.Enter()) { /* ... */ } } }

Thread 2 void t2() { using (lockB.Enter()) { using (lockA.Enter()) { /* ... */ } } }

При попытке выполнения t2 произойдет LockLevelException исключение, в момент вызова метода lockA.Enter, исключение будет означать, что иерархия блокировок была нарушена. При использовании Lock Leveling, до поставки приложения пользователям, вы должны хорошо протестировать ваше приложение с применением агрессивного тестирования. Необработанное исключение так же неудовлетворительно для пользователей.

Обратите внимание, что метод Enter возвращает объект IDisposable, что позволяет использовать конструкцию using (очень похожую на lock блок). Затем, когда вы покидаете границы using блока, неявно вызывается метод Exit. Есть так же несколько других вариантов создания экземпляра LeveledLock, доступных через параметры конструктора. Параметр reentrant указывает, может ли эта блокировка быть взята повторно тем же потоком, который ей уже владеет (по умолчанию true). Параметр name, это не обязательный параметр, просто имя блокировки, которое может пригодиться при отладке.

По умолчанию intra-level блокировки недоступны, другими словами, если вы у вас заблокирован ресурс A с уровнем 10 и вы попытаетесь заблокировать ресурс C с уровнем 10, то у вас это не получится. Если разрешить подобное поведение, то это бы являлось грубым нарушением иерархии блокировок, как итог, потоки могли бы попытаться приобрести блокировки в различном порядке (A и C или C и A). Вы можете изменить это поведение, использовав перегруженную версию метода Enter, который принимает параметр permitIntraLevel. Но сделав это однажды, вы должны знать, что deadlock отныне возможен в вашем приложении. Тщательно проверяйте ваш код, что бы это явное нарушение иерархии блокировок не привело к deadlock. Но не зависимо от того, как тщательно вы проверили свой код, он никогда не будет таким надежным, как при строгой иерархии блокировок. Используйте эту функцию с особой осторожностью.

Работа с Lock Leveling не проходит без проблем. Динамическая композиция программных компонентов может привести к неожиданным runtime ошибкам. Если низкоуровневые компоненты удерживают блокировку и делают вызов виртуального метода, пользовательского компонента, и этот пользовательский компонент пытается получить блокировку на более высоком уровне, иерархия блокировок будет нарушена и произойдет исключение. Deadlock в этом случае не произойдет, но будет run-time ошибка. Это одна из причин, почему вызов виртуальных методов во время удерживания блокировок считается плохой практикой. Хотя, это лучше, чем риск возникновения deadlock, но это основная причина, почему базы данных не используют эту технику: Они должны поддерживать динамическую композицию пользовательских транзакций.

На практике, многие программные системы к концу разработки используют кучу одноуровневых блокировок, скорее всего, вы найдете в них вызовы использующие permitIntraLevel. Это происходит не из-за того, что разработчики были чрезвычайно умными или осторожными при использовании permitIntraLevel, а по тому, что методика Lock Leveling достаточно трудна и обременительна на практике. Гораздо проще пойти на риск deadlock или сделать вид, что его там нет и быть не может, предполагая, что он не произойдет ни при тестировании, ни после поставки приложения (в нашем случае, положившись на русский авось). Действительно, так поступить много проще, чем потратить несколько часов выполняя необходимый рефакторинг кода. Но хорошо построенные блокировки, при которых время удерживаемого ресурса минимально, а так же, когда при необходимости создаются защитные копии данных, все это может быть использовано, что бы сделать применение Lock Leveling проще.

Много систем использующий Lock Leveling отключают его при поставке приложения (в non-debug builds), чтобы избежать проблем связанных с лишней нагрузкой на производительность. Но это означает, что вы обязаны протестировать ваше приложение, чтобы найти все нарушения иерархии блокировок. Динамические компоненты делают эту задачу чрезвычайно трудной. Если вы выключаете Lock Leveling при поставке приложения, то один не протестированный или непредусмотренный вариант использования может привести к deadlock.

Выявление и прерывание deadlock.

Техники, обсуждаемые ранее, позволяют полностью избегать deadlock. Но обычно, существует большое количество уже написанного кода и этот код довольно трудно полностью адаптировать к использованию Lock Leveling. Обычно, когда появляется deadlock, он будет проявляться как зависшее приложение, которое может не привести к сбору отладочной информации и отправке сообщения разработчику. Но в идеальном случае, если система не может избежать deadlock, то было бы хорошо, чтобы она их обнаруживала и как можно быстрее отправляла отчет, со всеми необходимыми данными, для последующего устранения проблемы. Это возможно и без реализации Lock Leveling в вашем приложении.

Современные базы данных использую свою методику для борьбы с deadlock, но применение этих техник в управляемом приложении довольно сложно на практике. Когда конкурируют транзакции базы данных, пытаясь получить блокировку, ведущую к deadlock, база данных может откатить одну из них, освободить занимаемые ею ресурсы, чтобы другая транзакция могла продолжить работу, как будто ничего и не произошло. Приложение в этом случае может повторить запрос или предоставить возможность решать пользователю «Повтор / Отмена», либо как-то еще отреагировать на откат транзакции.

Но в заурядных приложениях, которые не были изначально подготовлены реагировать на deadlock, сбой (crash) процесса является единственным, что вы можете предпринять.

Управляемый код, находящийся под управлением SQL Server™ 2005 (hosted code) так же, как бонус, приобретает систему обнаружения deadlock, очень похожую на ту, что будет описана ниже. Любой управляемый код, размещенный на SQL Server™ 2005, неявно оборачивается в транзакции, и прекрасно работает со стандартным обнаружением deadlock в базах данных.

Довольно сложный код нужно написать, чтобы он умел обнаруживать deadlock в приложении и при обнаружении пытался, по одной, откатить блокировки. Например, если поток удерживает блокировку A и B и получает deadlock, когда пытается получить блокировку C, можно произвести откат на момент приобретения блокировки B и освободить B, немного подождать, чтобы другие потоки могли выполнить свою работу, потом вновь заблокировать B и попытаться заблокировать C. Если deadlock возникнет вновь, то можно попытаться откатиться до A и освободить ее, затем повторить выполнение метода.

CLR Hosting API может быть использована для введения (inject) собственной логики приобретения и освобождения мониторов. Я использовал эту возможность при создании примера хоста, который находит deadlock и смягчает его последствия (проект доступен в исходном коде к статье). Давайте рассмотрим поближе этот пример и посмотрим, как deadlock detection может работать на практике.

Алгоритмы.

Существует две общепринятых методики, для обнаружения deadlock: timeout-based и graph-based.

Timeout-Based: основано на времени, которое необходимо для получения блокировки.

Предположим, что ресурс А может в теории удерживаться одним потоком не более секунды, этой секунды, по нашему мнению, достаточно что бы сделать любую запланированную работу над ресурсом. К примеру если поток пытается заблокировать и не может получить ресурс А в течении 60 сек, то вероятно, произошел deadlock.

При истечении время ожидания (timeout), вызывающий метод получает извещение. Иногда в виде исключения, в других случаях просто возвращается false (к примеру, в методе Monitor.TryEnter), которое позволяет программе или пользователю среагировать каким либо образом. Пространство имен System.Transactions использует эту модель в классе TransactionScopes, по умолчанию транзакции отменяются если выполнение превышает 60 секунд.

Основным недостатком данного подхода, это то, что deadlock обнаруживается позже, чем следовало бы, или длительные операции могут быть приняты за deadlock и прерваны. Кроме того, в моменты, когда программист решает, как поступить с deadlock, он может просто не знать, как правильно поступить или попытаться вновь взять блокировку, что приведет к бесконечному циклу.

Graph-Based: если у вас есть список потоков, которые находятся в активном ожидании, и перечень заблокированных ими ресурсов, вы можете составить график, показывающий кто кого ждет. Затем можно проанализировать данный график, если потоки в круговом ожидании, то произошел deadlock (однако, если какой либо поток в цикле использует Timeout-Based методику, при правильной реакции потока, deadlock может разрешиться самостоятельно). Это очень надежная стратегия, но довольно дорогостоящая в плане производительности.

В большинстве случаев комбинация этих методик может привести к хорошим результатам. К примеру, если произошел timeout, для проверки вы можете составить график. Это позволяет уменьшить значение timeout и создавать графики только в те моменты, когда в них требуется необходимость. Именно такой подход и применен в примере.

Далее Joe Duffy предлагает создать приложение Host, которое будет использовать CLR hosting API и C++. С помощью получившейся утилиты можно запускать .net приложения через командную строку (например deadhost.exe tests\test1.exe ) и находить deadlocks. Для более полной информации смотрите исходные коды к статье и оригинал статьи. А ниже будет описана более простая, пошаговая инструкция по выявлению deadlock, не только из запущенного приложения, но и с помощью анализа дампа памяти.

WinDbg + SosEx для поиска Deadlock

Для начала необходимо установить Debugging Tools for Windows (windbg.exe)
- Зайдите на страницу https://en.wikipedia.org/wiki/Microsoft_Windows_SDK там есть таблица выпущенных версий Microsoft Windows SDK, со ссылками на скачивание.
- Запустите установку и обязательно отметьте галочкой Debugging Tools
Необходимо скачать Debugging Extension for Managed Code – SosEx, http://www.stevestechspot.com/
Создадим консольное приложение SimpleDeadlock, которое будет впадать в deadlock практически в 100%

using System;

using System.Threading;

namespace SimpleDeadlock

{

    class Program

    {

       static object a = new object();

       static object b = new object();

        public static void MethodOne()

        {

            lock (a)

            {

                Thread.Sleep(100);

                lock (b)

                {

                    Console.WriteLine("Никогда не будет выведено на консоль (поток 1)");

                }

            }

        }

        public static void MethodTwo()

        {

            lock (b)

            {

                Thread.Sleep(100);

                lock (a)

                {

                    Console.WriteLine("Никогда не будет выведено на консоль (поток 2)");

                }

            }

        }

        static void Main(string[] args)

        {

            ThreadStart entryPointThread1 = MethodOne;

            ThreadStart entryPointThread2 = MethodTwo;

            Thread one = new Thread(MethodOne);

            Thread two = new Thread(MethodTwo);

            one.Start();

            two.Start();

            Console.WriteLine("Основной поток закончил работу.");

        }

    }

}
Запустим его и убедимся, что произошел deadlock (приложение повисло)
Запустим Task Manager, с помощью которого узнаем, что приложение 32 битное и его PID
В меню пуск, с помощью поисковой строки находим нужный файл winbdg (в нашем случае x86) и запускаем его
File -> Attack to a Process… -> выбираем наш процесс -> OK.
8. В открывшемся окне вы увидите несколько ошибок *** ERROR: Symbol file could not be found. Defaulted to export symbols for
Для того чтобы получить символы отладки с сервера Microsoft просто введите команду
.sympath SRV*f:\localsymbols*http://msdl.microsoft.com/download/symbols
Далее нужно загрузить расширение отладки SOS в отладчик, с помощью команды
.loadby sos clr
Результат выполнения команды:
Распакуем скачанное нами ранее расширение SosEx (в моем случае я его распаковал по адресу C:\Sosex\32 ) и загрузим его с помощью команды
.load C:\SosEx\32\sosex.dll
Результат выполнения команды:
Все готово к обнаружению deadlock, далее просто выполняем команду
!dlk
Результат выполнения команды:
Зафиксирован 1 deadlock, в нем участвуют потоки 0x3 и 0x4, для того что бы посмотреть стек вызова любого из этих потоков, просто введем команду
~4e !clrstack для потока 0x3
~5e !clrstack для потока 0x4
~4e !clrstack

Из стека вызовов видно, что поток пытается получить блокировку в методе MethodOne
~5e !clrstack

Из стека вызовов видно, что поток пытается получить блокировку в методе MethodTwo

Но что делать, если у вас нет возможности запустить приложение на своем компьютере и присоединить WinDbg к процессу? Вы можете попросить пользователя сделать полный дамп памяти, с помощью утилиты ProcDump, http://technet.microsoft.com/en-us/sysinternals/dd996900.aspx

В нашем случае нам нужен полный дамп 32 битного приложения, для этого подойдет командная строка: procdump -ma 124

-ma Write a dump file with all process memory. The default dump format only includes thread and handle information.

124 – PID процесса

И попросить переслать вам дамп, к примеру, по почте. А дальше все идентично, только подключаться нужно не к процессу, а к дампу памяти.

На этом все, удачи вам и спасибо что прочитали мою статью. Буду рад оставленным комментариям и новым постоянным читателям.

Александр Кобелев.

Перевод дробных чисел в бинарный формат (число с плавающей запятой IEEE 754)

2013-05-26T05:45:00.001-07:00

Перевод дробных чисел в бинарный формат (число с плавающей запятой IEEE 754)

В компьютере перевод происходит по иному, данная статья показывает, как добиться сходного результата на бумаге. В качестве рассматриваемого типа будет использован float, который соответствует типу IEEE754 Single precision 32-bit.

Для чтения статьи вам изначально нужно знать двоичную систему исчисления.

There are 10 types of people in this world: those who understand binary and those who don't.
~Author Unknown

Вы должны легко переводить числа (к примеру, 185) в двоичную систему (10111001).

И значения в следующей таблице не вызывают у вас непонимания:

Степень	Значение
0	1
1	2
2	4
3	8
4	16
5	32
6	64
7	128
…	…

Когда дело касается целочисленных то перевод в бинарный формат довольно легкий процесс, но когда дело доходит до дробных чисел, то форматов великое множество, и каждый раньше тянул одеяло в “истинно правильную” сторону своего личного формата. Но на сцену вышел формат IEEE 754, который принял пальму первенства и держит ее до сих пор.

История IEEE 754:

In 1976 Intel began planning to produce a floating point coprocessor. Dr John Palmer, the manager of the effort, persuaded them that they should try to develop a standard for all their floating point operations. William Kahan was hired as a consultant; he had helped improve the accuracy of Hewlett Packard's calculators. Kahan initially recommended that the floating point base be decimal[8] but the hardware design of the coprocessor was too far advanced to make that change.

The work within Intel worried other vendors, who set up a standardization effort to ensure a 'level playing field'. Kahan attended the second IEEE 754 standards working group meeting, held in November 1977. Here, he received permission from Intel to put forward a draft proposal based on the standard arithmetic part of their design for a coprocessor. The arguments over gradual underflow lasted until 1981 when an expert commissioned by DEC to assess it sided against the dissenters.

Even before it was approved, the draft standard had been implemented by a number of manufacturers.[9][10] The Intel 8087, which was announced in 1980, was the first chip to implement the draft standard.

http://en.wikipedia.org/wiki/IEEE_754-1985

Идеален ли формат IEEE 754? Если верить статье «IEEE754-тика угрожает человечеству» Автора Юровицкий В.М МФТИ, РГСУ http://www.yur.ru/science/computer/IEEE754.htm

То IEEE 754 уже наломал немало дров:

Взрыв ракеты "Пэтриот» в Саудовской Аравии 25 февраля 1991, который привел к гибели 28 человек, связан с ошибками округления.
Взрыв ракеты Ариан-5 сразу после старта при ее первом испытании во Французской Гвиане 4 июня 1996 был следствием переполнения числовой сетки компьютера.
23 августа 1991 в Гандсфиорде в Норвегии затонула нефтяная платформа, что привело к убытку почти в один миллиард долларов. Это, как предполагается, было результатом inaccurate finite element analysis.

Как уверяет автор - в будущем вероятность таких аварий и их тяжесть будет лишь увеличиваться.

Но, IEEE 754 распространен повсеместно, нужно просто знать, что он не идеален и учитывать возможные погрешности при проектировании программ, к которым предъявляются повышенные требования.

Смысл лучше всего постигать на примере, переведем число 185,4375 в бинарный формат IEEE 754.

Для начала нужно перевести целое число (185) в двоичный формат (10111001)

Далее нужно перевести число после запятой (4375) в двоичный формат.

Но делается это не так как с целыми числами. Процесс основан на утверждении, что любая дробь не может быть больше единицы. То есть, какое бы у нас число ни было после запятой, оно всегда будет в пределе от нуля до единицы, дробь 0,4375 не исключение

Для выражения числа в диапазоне от 0 до 1 нам поможет следующая таблица:

Степень	Значение
1/2	0.5
1/4	0.25
1/8	0.125
1/16	0.0625
1/32	0.03125
1/64	0.015625
1/128	0.0078125
…	…

Битовое выражение строится все на том же принципе сумм, но теперь складываем не степени двойки (2,4,8…) а дроби (1/2, 1/4, 1/8…). Число 0,4375 состоит из суммы 0,25+0,125+0,0625. Да, действительно, для простоты примера я заранее подобрал число из суммы этих значений, но не все дроби так легко подбираются. К примеру, попробуйте перевести число 0,2 его невозможно подобрать ровно, а самое близкое значение из суммы дробей будет 0,20000000298023223876953125 .

Итак, число 0,4375 в двоичном формате 01110000

Теперь у нас есть два числа в бинарном формате, целое(10111001) и дробь (01110000) если записать их в строчку, как одно число, то получим 10111001, 01110000 но бинарный формат не поддерживает запятых, только ноли и единицы. Обратимся к формату:

Бинарное представление числа 0,15625 Рисунок из статьи http://en.wikipedia.org/wiki/IEEE_754-1985

· Первый бит это знак: 0 положительное число; 1 отрицательное.

· Зеленая область – экспонента

· Розовая – мантисса

Имея на руках число (185,4375) и его бинарное представление (10111001, 01110000) мы можем легко вычислить знак, мантиссу и экспоненту.

Число 185,4375 положительное, то есть первый бит 0

Далее вычисляем мантиссу (просто убираем запятую между числами 10111001, 01110000) 1011100101110000

При вычислении мантиссы существует несколько правил:

1. Мантисса всегда должна начинаться с единицы, к примеру, возьмем число 5.5, в бинарном формате 5 будет 00000101, а его дробная часть 10000000, запишем его в строчку 00000101,10000000 и вычислим мантиссу 10110000000. Как видите, все ноли до единицы были просто отброшены.

2. Так как для мантиссы используется всего 23 бита, вместо 24 (один бит съел знак числа) и мантисса всегда начинаться с единицы. То первая единица отбрасывается (она всегда подразумевается, хоть и не записывается, но первая единица “как бы” есть всегда). Эта мантисса с отброшенной первой единицей и записывается, что бы различать мантиссы я ее называю “записываемая мантисса”, но это не официальное название. Записываемая мантисса позволяет записать в 23 бита последовательность из 24 бит.

Вернемся к числу 185.4375, его мантисса равна 1011100101110000, на ее основе вычисляем записываемую мантиссу 011100101110000 и записываем ее.

Настало время экспоненты.

Число 185,4375 (10111001, 01110000), его записываемая мантисса 01110010111000000000000. Воображаемо поставим в записываемой мантиссе запятую, так чтобы разделить число на целую и дробную части 0111001,0111000000000000. Не забудьте, что в записываемой мантиссе не указывается первая единица, но она подразумевается, по сути, эта запись 0111001,0111000000000000 = 10111001,0111000000000000. Если подсчитаете, то запятую в записываемой мантиссе мы поставили через 7 битов, число 7 и есть экспонента. Благодаря экспоненте всегда можно выделить из мантиссы целое число и его дробь.

Дальше формат IEEE 754 вновь подкидывает нам пару «НО»:

1. Экспонента может быть как положительной, так и отрицательной (случай с отрицательной экспонентой разберем чуть дальше). Чтобы убрать отрицательные числа из 8ми битной экспоненты, бит отвечающий за 128 изначально выставлен в единицу, максимальная сумма всех оставшихся битов равна 127 это число и есть максимальное значение экспоненты. При максимально возможной отрицательной экспоненте -127 их сумма 128 + (-127) равна единице, благодаря чему компьютер избавляется от необходимости работать с отрицательными числами. Число 127 это максимальное смещение для мантиссы, в любую сторону, как в лево, так и в право.

Казалось бы, все просто используем в экспоненте 10000000 для обозначения нулевого сдвига, диапазон от 100000001 до 11111111 для положительных значений, а диапазон от 011111111 до 00000001 для отрицательных и все отлично, но вылезает второе “НО”.

2. По всей видимости, при разработке стандарта обратили внимание на то, что одно значение в экспоненте не учитывается (00000000), или стояла иная задача, но в итоге, числа с плавающей запятой способны иметь бесконечное значение.

Еще со времен школы нам говорили, что на ноль делить нельзя - результат окажется бесконечностью. А числа с плавающей запятой на ноль делить можно.

Вот простой код на C#

using System;

namespace Infinity

{

class Program

{

static void Main()

{

Console.WriteLine(12345f / 0);

}

В этом коде мы делим число 12345 на ноль. Запись 12345f, говорит о том, что это число типа float которое соответствует типу IEEE754 Single precision 32-bit.

Результат выполнения программы:

На экспоненту это влияет следующим образом – экспонента 11111111 занята бесконечностью и не может представлять 127ый положительный сдвиг. Выходят из этого положения так: экспонента рассчитывается по формуле 128 + сдвиг – 1.

Теперь значения экспоненты:

· 11111111 – бесконечность

· 01111111 – нулевой сдвиг

· 10000000 – 11111110 положительный сдвиг

· 01111110 – 00000000 отрицательный сдвиг

Поэтому экспонента числа 185,4375 рассчитывается 128 + 7 -1 = 134, переводим в двоичный формат 10000111 и записываем.

Мы записали число 185,4375 в бинарном формате IEEE 754

Можно проверить себя на сайте http://www.binaryconvert.com

Разберем случаи с различными экспонентами:

Положительная экспонента бывает, в случае если целое число (не зависимо от знака) больше или равно 2. Пример положительной экспоненты мы рассмотрели с числом 185,4375

Отрицательная экспонента бывает, в случае если целое число равно нулю (не зависимо от знака).

Разберем на примере:

Возьмем число 0,125 переведем его в бинарный формат и запишем в строчку 00000000,00100000.
Получим мантиссу 100000 и вычислим записываемую мантиссу 00000.
Чтобы получить обратно два числа (целое и дробное) нужно сдвинуть записываемую мантиссу на 3 бита вправо это и будет экспонентой, то есть экспонента равна -3.
128 +(-3)-1 = 124 = 01111100
Совместим получившиеся данные в месте и проверим себя:
Знак 0; Экспонента 01111100; Мантисса 00000

Экспонента с нулевым сдвигом бывает, в случае если целое число равно единице (не зависимо от знака).

Разберем на примере:

Возьмем число -1,375 переведем его в бинарный формат и запишем в строчку 00000001,01100000
Получим мантиссу 101100000 и вычислим записываемую мантиссу 01100000
Чтобы получить обратно два числа (целое и дробное) нам не нужно никуда сдвигать запятую, так как она стоит в правильном месте.
128 + 0 – 1 = 127 = 01111111
Совместим получившиеся данные вместе и проверим себя
Знак 1 (так как число отрицательное); Экспонента 01111111; Мантисса 01100000

Бесконечная экспонента бывает при делении на ноль.

Бесконечность бывает как положительная, так и отрицательная:

Обзор был бы неполным,если не упомянуть о NaN.

NaN – Not a Number (не число). http://ru.wikipedia.org/wiki/NaN

К операциям, приводящим к появлению NaN в качестве ответа,относятся:

все математические операции, содержащие NaN в качестве одного из операндов;
деление нуля на ноль;
деление бесконечности на бесконечность;
умножение нуля на бесконечность;
сложение бесконечности с бесконечностью противоположного знака;
вычисление квадратного корня отрицательного числа;
логарифмирование отрицательного числа.

Так же NaN делится на 2 вида:

Quiet NaN
Signaling NaN

http://en.wikipedia.org/wiki/NaN

Quiet NaN – как видно из названия “тихий NaN” является простым NaN и не передает ни какой дополнительной информации. В бинарном представлении это бесконечность с записываемой мантиссой, у которой первый бит выставлен в единицу.

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

Александр Кобелев.

TSQL – PIVOT and UNPUVOT

2013-04-23T03:11:00.000-07:00

TSQL – PIVOT and UNPUVOT

По поводу оператора PIVOT в MSDN сказано:

«Оператор PIVOT разворачивает возвращающее табличное значение выражение, преобразуя уникальные значения одного столбца выражения в несколько выходных столбцов, а также, в случае необходимости, объединяет оставшиеся повторяющиеся значения столбца и отображает их в выходных данных».

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

Конечно, можно развернуть таблицу:

CREATE TABLE Employees(

Name nvarchar(50),

Age int,

Salary int);

INSERT INTO Employees VALUES

('Tom','40','50000'),

('Sam','30','40000'),

('Bob','25','35000');

SELECT * FROM Employees;

С помощью небольшого шаманства (не ломайте сейчас голову над представленным кодом, он вам станет понятен к концу статьи):

SELECT * FROM (

SELECT *

FROM (SELECT * FROM Employees) SourceTable

UNPIVOT(a FOR Properties in (Age,Salary))as UnpivotResultTable) UnpivotTable

PIVOT (

MAX(a) FOR Name in ([Tom],[Sam],[Bob])) PivotTable;

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

Для демонстрации, будем использовать справочник по мониторам, в который входят 515 записей. Чтобы было более интересно, скажу, что это абсолютно реальные данные, одного из популярных кибер гипермаркетов, актуальные на дату написания этой статьи. Данные были получены следующим образом: Абсолютно все мониторы (515 моделей), которые предлагает этот кибер гипермаркет, были выбраны для сравнения друг с другом, и получившаяся таблица преобразована в SQL код:

Код очень большой и поэтому выведен в отдельный файл доступный для скачивания:

https://skydrive.live.com/?cid=3a4fdd8b3b890be4&id=3A4FDD8B3B890BE4!311

зеркало
https://drive.google.com/folderview?id=0B1sG6jmDKzlvYXBFREhPVFJzeXc&usp

Итак, мы имеем таблицу, в которой 14 столбцов и 515 строк технической информации - справочник по мониторам.

Теперь, к примеру, мы можем узнать, какой самый дорогой или самый дешевый монитор:

SELECT Manufacturer, Model, Price

FROM Monitors

WHERE

Price IN (

(SELECT MIN(Price) FROM Monitors),

(SELECT MAX(Price) FROM Monitors));

Но, такой большой объем данных может выдать гораздо более разнообразную и полезную информацию.

С помощью PIVOT в наших силах создать хороший отчет. Например, в справочнике по мониторам указан вес практически каждого из них, но было бы не некорректно уровнять все мониторы под одну гребенку, ведь разные производители используют различные по весу блоки при изготовлении, так же у мониторов разная диагональ. Совершенно естественно, что мониторы с диагональю в 24 дюйма будут тяжелее, чем мониторы с диагональю 17 дюймов.

Следующий SQL запрос, с использованием PIVOT, предоставит в наше распоряжение отчет, который будет рассчитывать средний вес, учитывая все описанные выше нюансы:

SELECT Manufacturer , [17],[19],[24],[27] FROM

( SELECT Manufacturer,Size,Weight

FROM Monitors) AS SourceTable

PIVOT

(AVG (Weight)

FOR Size IN ([17],[19],[24],[27])

) AS PivotTable

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

Порядок составления запроса с инструкций PIVOT можно мысленно разделить на четыре раздела:

1. Составить SELECT запрос, который будет источником данных (SourceTable) для отчета и будет возвращать 2 или более столбцов (Пока мы рассматривали вариант только с тремя столбцами, чуть позже рассмотрим вариант с двумя и четырьмя).

SELECT Manufacturer , [17],[19],[24],[27] FROM

( SELECT Manufacturer,Size,Weight

FROM Monitors) AS SourceTable

PIVOT

(AVG (Weight)

FOR Size IN ([17],[19],[24],[27])

) AS PivotTable

На примере эта часть запроса выделена красным цветом

2. Выбрать столбец в SourceTable, значения строк которого станут столбцами в отчете, и указать конкретные значения. ( К сожалению, мы обязаны заранее задать значения для столбцов, и нет возможности применить что то на подобии звездочки или ALL.)

SELECT Manufacturer , [17],[19],[24],[27] FROM

( SELECT Manufacturer,Size,Weight

FROM Monitors) AS SourceTable

PIVOT

(AVG (Weight)

FOR Size IN ([17],[19],[24],[27])

) AS PivotTable

На примере эта часть запроса выделена красным цветом

3. Выбрать столбец или столбцы, которые будут представлять опорные данные по вертикали и повторить значения для столбцов по горизонтали, указанные в пункте 2 (в этом месте можно так же использовать оператор звездочку)

SELECT Manufacturer , [17],[19],[24],[27] FROM

( SELECT Manufacturer,Size,Weight

FROM Monitors) AS SourceTable

PIVOT

(AVG (Weight)

FOR Size IN ([17],[19],[24],[27])

) AS PivotTable

Или

SELECT * FROM

( SELECT Manufacturer,Size,Weight

FROM Monitors) AS SourceTable

PIVOT

(AVG (Weight)

FOR Size IN ([17],[19],[24],[27])

) AS PivotTable

На примере эта часть запроса выделена красным цветом

4. Теперь каждой ячейке соответствует группа, состоящая из значений единственно оставшегося столбца из SourceTable, который не участвовал ни в разделении на столбцы (Size), ни в опорных данных (Manufacturer). Необходимо применить агрегатную функцию к каждой группе.

SELECT Manufacturer , [17],[19],[24],[27] FROM

( SELECT Manufacturer,Size,Weight

FROM Monitors) AS SourceTable

PIVOT

(AVG (Weight)

FOR Size IN ([17],[19],[24],[27])

) AS PivotTable

На примере эта часть запроса выделена красным цветом

У вас может возникнуть вопрос, что будет, если в третьем пункте не указывать опорных столбцов, а использовать оператор звездочку. В данном случае SQL Server пойдет «от противного» все оставшиеся столбцы, не используемые в агрегатной функции, становятся опорными столбцами.

Перед тем как пойти дальше, рекомендую выполнить несколько упражнений с использованием PIVOT и справочником мониторов:

1. Получите среднее значение стоимости для мониторов каждого производителя, и различными диагоналями.

2. Получите среднее значение стоимости для мониторов с различной разрешающей способностью, и различными диагоналями.

3. Получите среднее значение стоимости для мониторов каждого производителя, и типа матрицы.

Составьте еще пару запросов самостоятельно.

Ранее я упоминал, что пока мы использовали SourceTable только с тремя столбцами, но можно 2 и более, рассмотрим на примерах.

SourceTable с двумя столбцами:

SELECT * FROM

( SELECT Manufacturer,Price

FROM Monitors) AS SourceTable

PIVOT

(MIN (Price)

FOR Manufacturer IN ([ACER],[AOC],[ASUS])

) AS PivotTable

Опорных данных нет, и все результаты идут в одну строчку.

SourceTable с четырьмя и более столбцами:

SELECT Manufacturer, Brightness, [17],[19],[24],[27] FROM

( SELECT Manufacturer,Size,Price, Brightness

FROM Monitors) AS SourceTable

PIVOT

(MIN (Price)

FOR Size IN ([17],[19],[24],[27])

) AS PivotTable

Таким образом мы увеличиваем количество опорных данных, к примеру значения ячейки столбца 17 в 16 строке можно прочитать как «Минимальная стоимость для производителя ASUS с диагональю монитора 17 дюймов и яркостью экрана в 250 кд/м2», а в строке 31 для яркости 300.

Оператор UNPIVOT

В MSN дано определение:

«Оператор UNPIVOT производит действия, обратные PIVOT, преобразуя столбцы возвращающего табличное значение выражения в значения столбца.»

Но является ли UNPIVOT полностью обратной PIVOT, в конструкции PIVOT обязательно использование агрегатной функции, получить исходные значения из результата агрегатной функции нельзя. Так что UNPIVOT ни в коем образе не является полностью обратной PIVOT.

Разберем на таблице Employees (которая была создана нами в самом начале статьи).

SELECT * FROM Employees;

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

SELECT *

FROM

(SELECT * FROM Employees) SourceTable

UNPIVOT(a FOR Properties in (Age,Salary))as UnpivotResultTable

Возьмем первую строку результата из запроса SourceTable

Внутри UNPIVOT, в выражении FOR - IN используются столбцы Age, Salary. Выражение UNPIVOT сводит все значения столбцов использовавшиеся в выражении FOR – IN в два столбца – значение столбца (Column1) и имя столбца (Column2). То есть значение первой строки должно разделиться на две.

В обеих строках значение в столбце Name остается неиспользованным значением из первой строки SourceTable.

Что будет, если мы будем использовать все три столбца, UNPIVOT сведет все значения в 2 столбца, значит, каждая строка SourceTable будет разделена на три.

SELECT * FROM

(SELECT

Name,

CAST(Age AS nvarchar(50)) Age,

CAST(Salary AS nvarchar(50)) Salary

FROM Employees) SourceTable

UNPIVOT

(Column1 FOR Column2 in (Name,Age,Salary)) AS UnpivotResultTable

Результат вполне ожидаемый. Хочется отметить, что нам пришлось воспользоваться функцией CAST, так как все столбцы, указанные в FOR – IN, должны быть одного типа.

Вернитесь к началу статьи и постарайтесь понять, каким образом я повернул таблицу по часовой стрелке и почему назвал это «шаманством».

Александр Кобелев.

TSQL – Over, Ранжирующие функции и нововведения в SQL Server 2012

2013-03-28T03:03:00.000-07:00

TSQL – Over, Ранжирующие функции и нововведения в SQL Server 2012

Предложение Over поддерживается с SQL Sever 2005. Давайте разберемся, какие выгоды мы можем извлечь.

В тестовой базе данных создадим таблицу OrderDetails и заполним ее данными:

CREATE TABLE OrderDetails(

OrderId int,

ProductName nvarchar(50),

Quantity int,

Price int);

INSERT INTO OrderDetails VALUES (1,'Sugar',10,10);

INSERT INTO OrderDetails VALUES (1,'Tea',1,25);

INSERT INTO OrderDetails VALUES (1,'Coffee',3,40);

INSERT INTO OrderDetails VALUES (2,'Coffee',1,50);

INSERT INTO OrderDetails VALUES (3,'Tea',100,19);

INSERT INTO OrderDetails VALUES (3,'Coffee',100,29);

Посмотрим на наши записи в таблице:

SELECT * FROM OrderDetails

Предположим, требуется узнать общее количество товаров в каждом заказе и итоговую стоимость каждого заказа:

SELECT

OrderId,

SUM(Quantity) AS OrderQuantity,

SUM(Quantity * Price) AS OrderPice

FROM OrderDetails

GROUP BY OrderId;

Далее, нужно совместить эти запросы, что бы одновременно посмотреть все записи в OrderDetails, знать общее количество товаров в каждом заказе и итоговую стоимость каждого заказа.

В SQL Server практически всегда можно пойти несколькими путями, к примеру, может возникнуть желание использовать подзапросы:

SELECT *,

(SELECT SUM(Quantity)

FROM OrderDetails

Where OrderId = ord.OrderId) as OrderQuantity,

(SELECT SUM(Quantity * Price)

FROM OrderDetails

Where OrderId = ord.OrderId) as OrderPrice

FROM OrderDetails as ord

Или Join:

SELECT OrderId,

ProductName,

Quantity,Price,

OrderQuantity,

OrderPrice

FROM OrderDetails

JOIN ( SELECT OrderId as Id,

SUM(Quantity) AS OrderQuantity,

SUM(Quantity * Price) AS OrderPrice

FROM OrderDetails

GROUP BY OrderId) AS ord

ON OrderId = ord.Id

Результат в обоих случаях будет:

Конечно, Join по производительности предпочтительнее (IO статистика показывает всего 4 сканирования таблицы), в отличие от подзапросов (13 сканирований).

Теперь добьемся такого же результата, используя предложение Over:

SELECT *,

SUM(Quantity) OVER (PARTITION BY OrderId) AS TotalQuantity,

SUM(Quantity * Price) OVER (PARTITION BY OrderId) AS TotalPrice

FROM OrderDetails

Первое что бросается в глаза - объем кода меньше. По производительности конструкция JOIN и OVER окажется одинаковой, если посмотреть на план запроса, то и он окажется практически идентичным. Но это только в конкретном случае, так как SQL Server ищет наиболее лучший способ для решения поставленной задачи и конструкция OVER дает больше свободы, чем жесткий JOIN.

Что же собственно мы просим от SQL Server, когда используем предложение OVER:

1. Выполни запрос без OVER и получи основной результат.

2. Сгруппируй основной результат, как указано в PARTITION BY.

3. Примени к получившимся группам функцию (функция может быть агрегатной, аналитической, ранжирующей, или NEXT VALUE FOR).

4. Сопоставь результаты функции с основным результатом запроса

Естественно, происходит все совсем не так, SQL Server самостоятельно находит каким образом ему лучше выполнить запрос, но зная эту последовательность, вы всегда сможете предсказать, как будет выглядеть результат запроса.

Можно группировать и без условий, используйте Over() и в группу войдут все строки.

SELECT *,

SUM(Quantity) OVER (PARTITION BY OrderId) AS OrderQuantity,

SUM(Quantity * Price) OVER (PARTITION BY OrderId) AS OrderPrice,

SUM(Quantity * Price) OVER () AllOrdersPrice

FROM OrderDetails

Далее нам потребуется ввести понятие окна. Лучше всего на примере, как думаете, сколько окон было в предыдущем результате? - Целых семь.

Каждое окно выделено красным прямоугольником, розовым цветом обозначены ячейки, находящиеся в столбцах указанных в PARTITION BY (благодаря им и происходит деление на окна), желтым – результат функции для окна.

Выполним запрос:

SELECT *,

SUM(Quantity) OVER () TotalQuantity

FROM OrderDetails

В дополнение к основному запросу будет созданное единственное окно, а результат функции это количество товаров во всех заказах.

Но если слегка изменить запрос и в конструкцию OVER добавить предложение ORDER BY:

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId) OverQuantity

FROM OrderDetails

То результат изменится:

Заметьте – мы не использовали предложение PARTITION BY, то есть наше выражение не делит результат запроса на окна, это до сих пор одно единственное окно.

Чтобы получить такие же результаты на бумаге, нам потребуется последовательно перебрать все строчки в окне и к каждой строке применить формулу расчета общего количества товаров к заказам, у которых OrderId менее(ASC) или равен текущему значению в строке.

Рассчитаем результаты для запроса:

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId DESC) OverQuantity

FROM OrderDetails

ORDER BY OrderId

Тут используется DESC сортировка (от большего к меньшему), по этому результаты будут отличны от предыдущего запроса.

Основной запрос:

SELECT * FROM OrderDetails ORDER BY OrderId

Использовалось предложение OVER без PARTITION, так что окно будет единственным и в него войдут все строки результата.

Сортировка ORDER BY использовалось с параметром DESC (от большего к меньшему) поэтому рассчитывать нужно от шестой строчки результата к первой.

Шестая и пятая строчки – сумма всех товаров для строк, у которых значение OrderId более(DESC) или равно 3.

Четвертая строчка – более или равно 2.

Третья, вторая и первая – более или равно 1.

SQL Server 2012 может еще больше расширить предложение ORDER BY, с помощью ROWS и RANGE предложений.

ROWS означает строки.

RANGE диапазон.

Вернемся к запросу:

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId) OverQuantity

FROM OrderDetails

Так как мы использовали OVER(), то здесь всего одно окно, но в окне используется сортировка по столбцу OrderId. Если рассматривать это окно с позиции ROWS то в нем 6 строк, а с позиции RANGE – 3 диапазона, основанных на уникальных значениях OrderId.

Окно на рисунке выделено красным прямоугольником, диапазоны голубыми прямоугольниками.

SQL Server 2012 дает нам возможность составлять условные предложения ROWS и RANGE в которых можно использовать следующие ограничения:

CURRENT ROW

Указывает на текущую строку или диапазон:

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId ROWS CURRENT ROW) OverQuantity

FROM OrderDetails

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId RANGE CURRENT ROW) OverQuantity

FROM OrderDetails

UNBOUNDED PRECEDING

Указывает, что надо учитывать все строки/диапазоны с первого и по текущий (хорошо подходит для составления промежуточных результатов).

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId ROWS UNBOUNDED PRECEDING) OverQuantity

FROM OrderDetails

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId RANGE UNBOUNDED PRECEDING) OverQuantity

FROM OrderDetails

UNBOUNDED FOLLOWING

Указывает, что надо учитывать все строки/диапазоны с текущего и по последний. Может быть указанным только в предложении BETWEEN как конечная точка.

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId, ProductName ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) OverQuantity

FROM OrderDetails

ORDER BY OrderId, ProductName

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId RANGE BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) OverQuantity

FROM OrderDetails

ORDER BY OrderId

<Integer> PRECEDING

Указывает, что нужно учитывать текущую строку и <Integer> строк до нее. Не допускается в предложении RANGE.

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId ROWS 1 PRECEDING) OverQuantity

FROM OrderDetails

<Integer> FOLLOWING

Указывает, что нужно учитывать диапазон <Integer> строк после текущей строчки. Может быть использовано только в предложении BETWEEN. Не допускается в предложении RANGE.

SELECT *,

SUM(Quantity) OVER (ORDER BY OrderId ROWS BETWEEN 1 FOLLOWING AND 2 FOLLOWING) OverQuantity

FROM OrderDetails

ORDER BY OrderId

BETTWEEN

Используется для указания границ.

Ранжирующие функции

С появлением OVER в SQL Server 2005 так же появились ранжирующие функции, все ранжирующие функции используются с конструкцией ORDER BY.

ROW_NUМBER()

Задает каждой строчке окна уникальный, последовательный номер, начиная с единицы.

SELECT *,

ROW_NUMBER() OVER (ORDER BY OrderId) ROW_NUМBER_SingleWindow,

ROW_NUMBER() OVER (PARTITION BY OrderId ORDER BY OrderId) ROW_NUМBER_ManyWindows

FROM OrderDetails

ORDER BY OrderId

RANK()

Возвращает ранг каждой строки в окне. Ранг для каждого уникального значения столбца или столбцов указанных в ORDER BY вычисляется лишь единожды, при первом нахождении оного. По формуле единица плюс количество строк до строки от начала окна.

SELECT *,

RANK() OVER (ORDER BY OrderId) RANK_Many_OrderId_Values_In_Window,

RANK() OVER (PARTITION BY OrderId ORDER BY OrderId) RANK_Single_OrderId_In_Window

FROM OrderDetails

ORDER BY OrderId

DENSE_RANK()

Возвращает ранг строк в окне без прыжков через значения. Ранг строки равен количеству уникальных значений указанных в ODER BY, предшествующих строке, увеличенному на единицу.

SELECT *,

DENSE_RANK() OVER (ORDER BY OrderId) Many_OrderId_Values_In_Window,

DENSE_RANK() OVER (PARTITION BY OrderId ORDER BY OrderId) Single_OrderId_In_Window

FROM OrderDetails

ORDER BY OrderId

NTILE(<Integer>)

Распределяет строки в окне на заданное количество групп. Группы нумеруются, начиная с единицы. Для каждой строки функция NTILE возвращает номер группы, которой принадлежит строка.

SELECT *,

NTILE(3) OVER (ORDER BY OrderId) NTILE_One_Window,

NTILE(3) OVER (PARTITION BY OrderId ORDER BY OrderId) NTILE_Many_Windows

FROM OrderDetails

ORDER BY OrderId

Александр Кобелев.

TSQL - GROUP BY с операторами ROLLUP и CUBE, и агрегатные функции GROUPING и GROUPING_ID

2013-03-21T03:20:00.000-07:00

TSQL - GROUP BY с операторами ROLLUP и CUBE, и агрегатные функции GROUPING и GROUPING_ID

Простейшее группирование результатов запроса не вызывает никаких сложностей, и SQL Server всегда выдает понятный и ожидаемый результат. Но, когда впервые сталкивается с конструкциями ROLLUP и CUB можно натолкнуться на преграду, так как интуитивно понятными данные конструкции назвать сложно.

ROLLUP и CUBE вставляют в результат статистические строки, что это разберемся далее, сейчас хочу лишь заметить что разница в этих конструкциях только в формуле, благодаря которой они определяют сколько и каких статистических строк вставить.

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

CREATE TABLE WineCellar (

Color nvarchar(50),

Sugar nvarchar(50),

Years int);

INSERT WineCellar VALUES ('White','doux',5);

INSERT WineCellar VALUES ('White','doux',10);

INSERT WineCellar VALUES ('White','sec',5);

INSERT WineCellar VALUES ('White','sec',10);

INSERT WineCellar VALUES ('Red','doux',5);

INSERT WineCellar VALUES ('Red','doux',10);

INSERT WineCellar VALUES ('Red','sec',5);

INSERT WineCellar VALUES ('Red','sec',10);

Ранее я упоминал, что и ROLLUP и CUBE используют некую формулу для предоставления результатов, но не только - они так же предоставляют итоговую строку, это группа в которой включено все множество запроса, и называется она «строка общего итога».

Формулы в ROLLUP и CUBE могут работать только когда идет группировка по нескольким столбцам, если же идет группировка по единственному столбцу, они работать не будут, а в результирующем наборе появится только «строка общего итога»

Если мы выполним SQL запрос:

SELECT Color, Count(*) Count

FROM WineCellar

GROUP BY ROLLUP(Color)

Или:

SELECT Color, Count(*) Count

FROM WineCellar

GROUP BY CUBE(Color)

То результат будет идентичным:

Так как формулы не могут работать, когда группировка происходит только по одному столбцу.

Что же такое «строка общего итога», выполним тот же запрос только без ROLLUP или CUBE

SELECT Color, Count(*) Count

FROM WineCellar

GROUP BY Color

Результатом будет:

Как можно заметить запрос вернул в общей сумме 2 группы по 4 строки в каждой группе, то есть всего запрос вернул 8 строк. Если посмотрим на предыдущий результат, в котором есть «строка общего итога», то можно заметить что последняя группа содержит в себе 8 строк. Другими словами «строка общего итога» это группа, в которой находятся копии всех строк, возвращенных запросом.

Теперь обратим внимание на формулы, по которым работают ROLLUP и CUBE.

ROLLUP один из возможных переводов с английского это сдвиг строк (на экране дисплея), если провести аналогию дальше, то это похоже на битовый сдвиг влево. Рассмотри на примере колонок:

Предположим, есть три исходные колонки A,B,C воображаемо сделаем два сдвига влево. Результатом первого сдвига будет B,C,NULL а результатом второго будет C,NULL,NULL . Делать сдвиги далее не имеет смысла, так как результат будет всегда один NULL,NULL,NULL.

Формула ROLLUP использует эти сдвиги, что бы понять какие результаты от нее требуются.

Попробуем рассчитать самостоятельно результат для запроса:

SELECT Color,Sugar,Years, Count(*) Count

FROM WineCellar

GROUP BY ROLLUP(Color,Sugar,Years)

Итак, первым делом SQL SERVER поймет, что вам требуется сгруппировать результат по колонкам Color,Sugar,Years запрос может выглядеть таким образом:

SELECT Color,Sugar,Years, Count(*) Count

FROM WineCellar

GROUP BY Color,Sugar,Years

Результат:

Так же нам должны предоставить строку общего итога.

Так как мы использовали три столбца для группировки – промежуточные результаты для двух сдвигов, могут быть следующего вида:

SELECT Color,Sugar, Count(*) Count

FROM WineCellar

GROUP BY Color,Sugar

SELECT Color, Count(*) Count

FROM WineCellar

GROUP BY Color

Объединим вручную, в один результат:

Осталось лишь выполнить запрос:

SELECT Color,Sugar,Years, Count(*) Count

FROM WineCellar

GROUP BY ROLLUP(Color,Sugar,Years)

И сравнить результаты:

Немного не то что мы ожидали, но если приглядеться то SQL Server лишь изменил порядок вывода, на более удобный, с его точки зрения.

Перейдем к оператору CUBE

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

То есть, если будет создан запрос, который будет использовать три столбца с оператором CUBE, то в результирующий набор войдет все возможное множество комбинаций этих столбцов.

Рассмотрим на примере:

Для запроса использующего три столбца (A,B,C) в случае ROLLUP в дополнение к основному результату создается «строка общего итога» и результаты для сочетаний (A,B) и (A) в соответствии со сдвигами.

В случае же с CUBE в дополнение к основному результату создается «строка общего итога» и все возможные уникальные вариации для столбцов (A,B);(A,C);(B,C);(A);(B);(C).

Попробуем вновь предугадать результат для запроса:

SELECT Color,Sugar,Years, Count(*) Count

FROM WineCellar

GROUP BY CUBE(Color,Sugar,Years)

Как и в прошлый раз SQL SERVER поймет, что вам требуется сгруппировать результат по колонкам Color,Sugar,Years запрос может выглядеть таким образом:

SELECT Color,Sugar,Years, Count(*) Count

FROM WineCellar

GROUP BY Color,Sugar,Years

Результат:

Так же он подсчитает строку общего итога.

Далее идет целых 6 возможных вариаций со столбцами Color,Sugar,Years

Color + Sugar

SELECT Color,Sugar, Count(*) Count

FROM WineCellar

GROUP BY Color,Sugar

Результат:

Color + Years

SELECT Color,Years, Count(*) Count

FROM WineCellar

GROUP BY Color,Years

Результат:

Sugar + Years

SELECT Sugar,Years, Count(*) Count

FROM WineCellar

GROUP BY Sugar,Years

Результат:

Color

SELECT Color, Count(*) Count

FROM WineCellar

GROUP BY Color

Результат:

Sugar

SELECT Sugar, Count(*) Count

FROM WineCellar

GROUP BY Sugar

Результат:

Years

SELECT Years, Count(*) Count

FROM WineCellar

GROUP BY Years

Результат:

Объединим все результаты вручную:

И сравним с результатом:

SELECT Color,Sugar,Years, Count(*) Count

FROM WineCellar

GROUP BY CUBE(Color,Sugar,Years)

Как можно заметить мы опять ошиблись лишь с последовательностью вывода.

Перейдем к агрегатным функциям GROUPING и GROUPING_ID

Вы наверняка обратили внимание на большое количество NULL значений после того как отработают операторы ROLLUP или CUBE. Так же вы привыкли думать, что NULL это всегда NULL, но не в этом случае. Дело в том, что SQL Server различает NULL как значение в таблице и NULL который был выставлен в результате работы ROLLUP или CUBE.

Чтобы продемонстрировать это, надо изменить нашу таблицу и вставить строку с NULL значениями:

ALTER TABLE WineCellar ALTER COLUMN Color nvarchar(50) NULL;

ALTER TABLE WineCellar ALTER COLUMN Sugar nvarchar(50) NULL;

ALTER TABLE WineCellar ALTER COLUMN Years int NULL;

INSERT WineCellar VALUES (NULL,NULL,NULL);

Агрегатная функция GROUPING проверяет NULL значение, в случае если оно было выставлено в результате работы ROLLUP или CUBE значение будет единица в остальных случаях ноль.

Проверяем:

SELECT Color,Sugar,Years, Count(*) Count,

GROUPING(Color) GROUPING_Color,

GROUPING(Sugar) GROUPING_Sugar,

GROUPING(Years) GROUPING_Years

FROM WineCellar

GROUP BY ROLLUP(Color,Sugar,Years)

Результат:

В отличии от GROUPING для понимания GROUPING_ID необходимо знать про битовые флаги (для ознакомления можно прочесть статью http://skillcoding.com/Default.aspx?id=87 ), так как GROUPING_ID возвращает Integer значение битового флага.

Немного переделаем предыдущий пример:

SELECT Color,Sugar,Years, Count(*) Count,

GROUPING(Color) Color_Bit,

GROUPING(Sugar) Sugar_Bit,

GROUPING(Years) Years_Bit,

GROUPING_ID(Color,Sugar,Years) as BinaryFlag

FROM WineCellar

GROUP BY ROLLUP(Color,Sugar,Years)

Результат:

Как видно из запроса мы указываем - из каких колонок и в какой последовательности проверять NULL значения.

Возьмем для примера десятую строчку. NULL значения в столбце Color нет, в столбце Sugar есть и этот NULL - результат работы ROLLUP. В столбце Years тоже есть NULL значение, которое является результатом работы ROLLUP. В итоге получаем битовый флаг 011, при переводе из двоичной системы в десятеричную получаем тройку, что и отображается в столбце BinaryFlag.

Александр Кобелев.

TSQL – Понимание агрегатных функций: STDEV STDEVP VAR VARP

2013-03-17T08:52:00.000-07:00

TSQL – Понимание агрегатных функций: STDEV STDEVP VAR VARP

Толчком к написанию данной статьи послужила статья «Variance and Standard Deviation» http://www.bullsbetting.com/index.php/variance-and-standard-deviation

Для того что бы начать понадобится ввести термин «популяция». Лучше всего понимаешь его на примере:

Предположим мы занимаемся фермерским делом и уже сняли урожай помидоров. К сожалению, за весь год мы сумели вырастить только три помидора. Первый имеет диаметр 11 сантиметров, второй 12 и последний, наша гордость, целых 16 сантиметров.

Далее мы положили все помидоры в банку и оформляем этикетку, закон требует указать на этикетке средний диаметр помидора. Путем простых калькуляций, мы вычисляем что это (11+12+16)/3 = 13 сантиметров. Но по факту у нас нет ни одного помидора с таким диаметром, зато теперь мы можем рассчитать популяцию для всего нашего урожая. Рассчитывается разница между каждым помидором и средним помидором, эта последовательность разниц и есть популяция. В нашем случае это -2, -1, 3.

Теперь рассмотрим функцию VARP, создадим в тестовой базе данных таблицу Yield и заполним ее:

CREATE TABLE Yield

(

Name nvarchar(50),

Diameter int

)

INSERT Yield VALUES ('Tomato',11);

INSERT Yield VALUES ('Tomato',12);

INSERT Yield VALUES ('Tomato',16);

Расчет популяции этих трех значений будет: -2,-1,3

Как, используя популяцию, можно рассчитать среднюю разницу между помидорами? В начале, напрашивается ответ, сложить все числа популяции и разделить на количество чисел в популяции. Но особенностью популяции является то, что при сложении всех чисел результатом будет ноль. Математики поступают следующим образом - возводят в квадрат каждое число в популяции, и таким образом значение не будет нулем 4+1+9 = 14, затем делим на три 4,666… но этот результат до сих пор в квадрате, выводим корень из 4,6666 …. = 2,160.. То есть среднее изменение диаметра от помидора к помидору около 2,160 сантиметра.

Проверяем, соответствуют ли наши вычисления агрегатной функции VARP (Variant) SQL Server:

SELECT Name, VARP(Diameter) as VARP, SQRT(VARP(Diameter)) as Sqrt_From_VARP

FROM Yield

GROUP BY Name

Name VARP Sqrt_From_VARP

--------------------- ---------------------- ----------------------

Tomato 4.66666666666667 2.16024689946929

(1 row(s) affected)

Как видите, результат оказался ожидаемым.

Чем же отличается VARP от VAR? Дело в том, что VAR использует не всю популяцию для расчетов, а лишь часть, в итоге результат будет менее точным, но расчет произойдет быстрее.

Разница видна даже на такой маленькой таблице (у вас могут получиться другие результаты):

SELECT Name, VAR(Diameter) as VAR, SQRT(VAR(Diameter)) as Sqrt_From_VAR

FROM Yield

GROUP BY Name

Name VAR Sqrt_From_VAR

------------------------ ---------------------- ----------------------

Tomato 7 2.64575131106459

(1 row(s) affected)

Как видите, данные примерны, но не далеки от оригинала. VAR быстрее обработает большую популяцию чем VARP, к тому же, при работе с большей популяцией у VAR возрастет точность, и погрешность будет не сильно велика.

Теперь фраза из MSDN описывающая агрегатную функцию VARP:

«Возвращает статистическую дисперсию для заполнения всех значений в указанном выражении»

Становится понятной, и не нагоняет тоску.

Перейдем к агрегатной функции STDEVP, выполним следующий запрос:

SELECT Name, STDEVP(Diameter) as STDEVP

FROM Yield

GROUP BY Name

Name STDEVP

------------------------ ----------------------

Tomato 2.16024689946929

(1 row(s) affected)

Ничего не напоминает? Правильно – результат STDEVP это SQRT(VARP(Diameter))

Несложно догадаться что:

SELECT Name, STDEV(Diameter) as STDEV

FROM Yield

GROUP BY Name

Name STDEV

--------------------- ----------------------

Tomato 2.64575131106459

(1 row(s) affected)

STDEV это SQRT(VAR(Diameter))

Александр Кобелев.

Знакомство с Google Maps JavaScript API V3 на примерах

2013-03-17T08:43:00.000-07:00

Знакомство с Google Maps JavaScript API V3 на примерах

Сегодня я хочу рассмотреть Google Maps Java Script API Version 3 на конкретных примерах, которые могут быть востребованы в повседневной работе.

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

1. Вам необходимо иметь/зарегистрировать google аккаунт (почта).

2. Переходим по ссылке https://code.google.com/apis/console

3. С лева выбираем закладку Services

4. Находим переключатель Google Maps API v3 и активируем его

5. Отлично, теперь заходим в пункт API Access

6. И забираем свой ключик

Поздравляю! Теперь вы можете пользоваться google maps.

Начнем с простого, но полезного. Разместим на пустой страничке карту и четыре кнопки. На каждую кнопку привяжем по местоположению городов (Санкт-Петербург, Сидней, Нью-Юрк и Лондон). Кликая по каждой кнопке мы будем перемещать карту, и это позволит визуально сравнить размеры городов. Мне довольно любопытно сравнить родной Санкт-Петербург с этими городами, а вы можете немного изменить код и выставить свой город или добавить еще одну кнопку.

Открываем блокнот, создаем файл Cities.html и вставляем следующий код:

<!DOCTYPE html>

<head>

function ShowPositon(x, y) {

var mapOptions = {

center: new google.maps.LatLng(x, y),

zoom: 9,

mapTypeId: google.maps.MapTypeId.ROADMAP

};

var map = new google.maps.Map(document.getElementById("map_canvas"),

mapOptions);

return (false);

}

</script>

</head>

<button onclick="ShowPositon(59.940224, 30.308533)">Saint-Petersburg</button>

<button onclick="ShowPositon(-33.847608, 150.930176)">Sydney</button>

<button onclick="ShowPositon(40.711353, -74.002533)">NewYork</button>

<button onclick="ShowPositon(51.510452, -0.127716)">London</button>

</body>

</html>

Чтобы пример заработал, вам необходимо заменить Your_API_Key на ваш ключик. Вы можете подумать, что опасно размещать в открытую ваш ключ в коде страницы и вы будете на все сто процентов правы, но тут есть одно большое НО:

Если вы зайдете в API Access -> Simple API Access то найдете там пункт в меню “Edit allowed referers...”, с помощью которого можно создать белый список доменных имен, с которых принимаются запросы, в противном случае они отклоняются. По умолчанию список пуст, что разрешает принимать запросы отовсюду.

Итак, все готово к первому запуску, посмотрев результаты можно заметить что Лондон, Сидней и Санкт-Петербург примерно занимают одинаковую площадь, в отличие от Нью-Юрка, который явно лидирует.

Краткий обзор кода:

1. Google Api подключается с помощью ссылки на JavaScript файл и личного ключа. <script type="text/javascript" src="http://maps.googleapis.com/maps/api/js?key=Your_API_Key&sensor=false"></script>

2. Можно изменять настройки карты с помощью объекта mapOptions

3. В названии класса google.maps.LatLng спрятано две аббревиатуры - широта (latitude) и долгота (longitude), собственно их и принимает его конструктор

Теперь поставим собственный, маркер в виде маленького грузовичка и заставим его кататься по прямой от метро «Парк Победы» до «Московская Площадь» я специально выбрал этот маршрут чтоб не сильно думать о логике движения, так как там по прямой.

Создадим новый файл Track.html и скачаем иконку грузовичка Track.png и положим их вместе.

Теперь вставим следующий код:

<!DOCTYPE html>

<html>

<head>

src="http://maps.googleapis.com/maps/api/js?key=AIzaSyBXQROV5YMCERGIIuwxrmaZbBl_Wm4Dy5U&sensor=false">

</script>

var trackMarker;

var lat = 59.8659;

var movingDown = true;

var movingUp = false;

var isMoving = false;

function initialize() {

var mapOptions = {

center: new google.maps.LatLng(59.858889, 30.320849),

zoom: 14,

mapTypeId: google.maps.MapTypeId.ROADMAP

};

var map = new google.maps.Map(document.getElementById("map_canvas"),

mapOptions);

var image = 'track.png';

var myLatLng = new google.maps.LatLng(lat, 30.320807);

trackMarker = new google.maps.Marker({

position: myLatLng,

map: map,

icon: image

});

}

function move() {

if (lat > 59.866) {

endDrive(true, false);}

if (lat < 59.851) {

endDrive(false, true);}

if (movingDown) lat = lat - 0.0001;

if (movingUp) lat = lat + 0.0001;

trackMarker.setPosition(new google.maps.LatLng(lat, 30.321136));

}

function loop() {

setTimeout(function () {

if (isMoving) {

move();

loop();

}

}, 50)

}

function endDrive(down, up) {

movingDown = down;

movingUp = up;

isMoving = false;

document.getElementById("drive_btn").disabled = false;

}

function drive() {

isMoving = true;

document.getElementById("drive_btn").disabled = true;

loop();

}

</script>

</head>

<button id="drive_btn" onclick="drive()">Drive</button>

</body>

</html>

Сохраним и запустим. Грузовичок катается как надо :) Краткий обзор кода:

1. Метод initialize запускается как только страничка загружена инициализирует карту и размещает на ней маркер с картинкой.

2. Метод Drive запускает алгоритм движения, который реализован в методах loop, move и endDrive

3. Чтобы передвинуть маркер достаточно изменить его позицию через метод setPosition и передать ему объект класса LatLng с новыми координатами

Я живу во Фрунзенском районе Санкт-Петербурга, здесь очень много деревьев и практически не слышно вездесущего городского шума. Для демонстрации отображения полигонов я нарисую его на карте. И поможет мне в этом следующий код:

<!DOCTYPE html>

<html>

<head>

src="http://maps.googleapis.com/maps/api/js?key=AIzaSyBXQROV5YMCERGIIuwxrmaZbBl_Wm4Dy5U&sensor=false">

</script>

function initialize() {

var mapOptions = {

center: new google.maps.LatLng(59.858889, 30.370849),

zoom: 11,

mapTypeId: google.maps.MapTypeId.ROADMAP

};

var map = new google.maps.Map(document.getElementById("map_canvas"),

mapOptions);

var paths = [new google.maps.LatLng(59.913644, 30.334597),

new google.maps.LatLng(59.916139, 30.345411),

new google.maps.LatLng(59.91373, 30.363407),

new google.maps.LatLng(59.833775, 30.47533),

new google.maps.LatLng(59.818935, 30.381947),

new google.maps.LatLng(59.875672, 30.353451),

new google.maps.LatLng(59.883597, 30.346928),

new google.maps.LatLng(59.89152, 30.346098)];

var shape = new google.maps.Polygon({

paths: paths,

strokeColor: '#00FF00',

strokeOpacity: 0.8,

strokeWeight: 2,

fillColor: '#00FF00',

fillOpacity: 0.35

});

shape.setMap(map);

}

</script>

</head>

</body>

</html>

Все очень просто:

1. Инициализируем карту

2. Создаем массив координат

3. Создаем объект класса полигон и выставляем его свойства

4. Связываем полигон с картой.

Есть желание продолжить? Не проблема! Здесь вы найдете большое количество примеров - http://code.google.com/apis/ajax/playground/#map_simple_v3

Александр Кобелев.