Отправляет email-рассылки с помощью сервиса Sendsay
  Все выпуски  

Новости сайта "Упражнения по SQL" (http://www.sql-ex.ru) 104


Новости сайта "Упражнения по SQL (http://www.sql-ex.ru)" Выпуск 104 (9 сентября 2006 г.)

http://www.sql-ex.ru

Новым посетителям сайта

Сайт посвящен изучению языка, с помощью которого осуществляется взаимодействие с реляционными (и не только) СУБД. Суть обучения состоит в выполнении заданий на написание запросов к учебным базам данных; при этом система контролирует правильность выполнения заданий. В настоящее время реализованы все операторы подъязыка манипуляции данными (DML), которые включают в себя оператор извлечения данных SELECT, а также операторы модификации данных - INSERT, DELETE и UPDATE.

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

Демонстрация плана выполнения запроса и сравнительная оценка эффективности решений поможет вам освоить принципы оптимизации запросов.

Имеется возможность получить сертификат по SQL DML при выполнении определенного количества заданий.


Новости сайта

§ Как справедливо заметил PHOENIX2000, формулировка простой задачи 34 допускает трактовку в стиле задачи 41. Добавил примечание, что рассматриваются только корабли с известным годом спуска на воду.

§ Свершилось:-). С задачи Snowbear - 139 - начат третий этап. Он называется оптимизационным, т.к. теперь недостаточно просто решить задачу. Нужно еще, чтобы время выполнения запроса-решения не превышало более чем вдвое время выполнения авторского решения. Доступ к третьему этапу получает тот, кто решит 138 задачу.
Условия третьего этапа:
1. Время, потраченное на задачи второго этапа обнуляется, т.е. соревнование ведется только по результатам третьего этапа.
2. Участник, находящийся на третьем этапе (Маклауд :-)), всегда будет в рейтинге выше всех тех участников, кто еще находится на втором этапе, независимо от общего количества баллов.
3. Задачи можно решать в любом порядке и начинать решать сразу несколько задач. Естественно, для все начатых задач время будет тикать.
4. Участник третьего этапа не потеряет в рейтинге, даже если вообще не будет решать новые задачи предыдущих этапов.
Баллы предыдущих этапов будут учитываться только при равенстве показателей третьего этапа.

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

§ Новый человек в сотне - Goga_3040 (задач 115, время 31.130).

§ Сохранили шансы попасть в ТОР 10:
SolYUtor (137, 12.909)
MadVet (задач 137, время 25.778)
Johan (130, 7.773)
=Maxim= (125, 19.510)
PS_Sergey (120, 7.481)

§ Продолжили свое восхождение к вершине:
Ocean (123, 45.119)
imsh (123, 50.162)

§ На этой неделе сертифицированы:
Нормальный пацан (A06011082) [BK] (г.Новосибирск, Россия)
imsh (A06011082 [BK] и B06011387 [AR]) (Netanya, Israel)

§ Число подписчиков - 3290

Число участников рейтинга - 6704

Число участников второго этапа - 666

Сертифицировано на сайте - 91

Лучшие результаты (ТОР 20)

No Person Number of
Sel_ex
Last_Sel Number of
DML_ex
Scores Days Days_2 LastSolved LastVisit
1 Войнов П.Е. (pаparome) 138 47 20 323 348 2.680 07 Aug 2006 08 Sep 2006
2 Юлдашев М.Р. (Snowbear) 138 47 20 323 383 4.055 05 Aug 2006 08 Sep 2006
3 Slobodcicov A.N. (Testo) 138 92 20 323 337 7.180 25 Aug 2006 07 Sep 2006
4 Мурашкин И.В. (lepton) 138 47 20 323 136 10.134 06 Aug 2006 07 Sep 2006
5 Иванов А.Н. (Goapsy) 138 47 20 323 270 18.919 07 Aug 2006 07 Aug 2006
6 Голубин Р.С. (Roman S. Golubin) 138 47 20 323 353 21.138 06 Aug 2006 08 Sep 2006
7 Карасёва Н.В. (vlksm) 138 47 20 323 92 24.922 06 Aug 2006 02 Sep 2006
8 Валуев Д.И. (Fiolent) 138 47 20 323 1085 54.545 24 Aug 2006 08 Sep 2006
9 Кувалкин К.С. (Cyrilus) 137 47 20 321 623 9.768 09 Aug 2006 08 Sep 2006
10 Абашин П.И. (Dizil) 137 47 20 319 348 3.903 07 Aug 2006 31 Aug 2006
11 Самохвалов В. (ValdemarES) 137 47 20 319 273 7.850 17 Aug 2006 05 Sep 2006
12 Солдатенков Ю.С. (SolYUtor) 137 137 20 319 111 12.909 06 Sep 2006 08 Sep 2006
13 Держальцев В.А. (MadVet) 137 92 20 319 506 25.778 04 Sep 2006 06 Sep 2006
14 Тарасов Д.Б. (Gavrila) 136 47 20 318 346 19.382 07 Aug 2006 08 Sep 2006
15 Kamaev V.M. (Heromantor) 135 138 20 316 128 9.044 14 Mar 2006 25 Mar 2006
16 Бураков С.Г. (burakov58) 135 138 20 316 419 17.381 24 Mar 2006 07 Apr 2006
17 frenkental (a2010) 135 137 20 315 110 15.332 19 Jul 2006 26 Jul 2006
18 Крижевич С.А. (yaff) 135 47 20 314 407 14.792 11 Aug 2006 23 Aug 2006
19 Зырин В.Е. (Vezyr) 135 47 20 314 204 20.590 05 Aug 2006 12 Aug 2006
20 Страшников А.С. (EffEct) 135 47 20 314 452 59.948 10 Aug 2006 08 Sep 2006

Лучшие результаты за неделю

No surname n_sel sel_all sel_scores dml_scores scores rating last_visit
1 >Карасев А.В. (Lotar) 57 57 106 32 138 384 08 Sep 2006
2 Спирин А.В. (PHOENIX2000) 60 60 110 0 110 688 07 Sep 2006
3 >rrr (Nromik) 47 47 81 0 81 1199 08 Sep 2006
4 >Дзидзигури Д.Г. (Диана) 45 45 80 0 80 1216 08 Sep 2006
5 Гончаров Д.К. (Ockham) 38 44 73 0 73 1241 07 Sep 2006
6 >Натаров С.А. (Mr..Gray) 40 40 73 0 73 1408 08 Sep 2006
7 >Иванов (Wind7) 35 42 68 3 71 1285 08 Sep 2006
8 >Voronchev (keezaa) 43 43 69 0 69 1514 08 Sep 2006
9 >all2000 (all) 37 37 64 5 69 1515 08 Sep 2006
10 Шевченко А.Ю. (alexsvk) 32 56 67 0 67 394 07 Sep 2006
11 >Kriex (Крик) 29 29 49 17 66 1578 08 Sep 2006
12 >Крутов А.Ю. (kaiu) 36 36 65 0 65 1607 08 Sep 2006
13 >Кузнецов А. (Chupokabr) 35 35 64 0 64 1631 08 Sep 2006
14 >Кержнер И. (argnist) 26 41 50 9 59 1347 08 Sep 2006
15 >Надаев Э.А. (Nerd) 33 33 58 1 59 1809 08 Sep 2006
16 Shymko I.V. (MaverickWise) 32 32 57 0 57 1894 07 Sep 2006
17 >Shtenyovych V.I. (Volodya) 36 36 57 0 57 1896 08 Sep 2006
18 >Голованова (Oksana2006) 31 31 56 0 56 1936 08 Sep 2006
19 Иванов М.С. (mxi) 20 60 37 17 54 348 08 Sep 2006
20 Antipov (Antipych) 27 27 47 0 47 2285 07 Sep 2006
21 >Креславский И.М. (Kreslav) 10 60 22 23 45 347 08 Sep 2006
22 Корж (KSK) 23 59 44 0 44 355 08 Sep 2006
23 Волков О.В. (kutuzov) 30 30 40 3 43 2442 08 Sep 2006
24 >Овечкин М. (Gralph) 20 66 42 0 42 271 08 Sep 2006
25 Lyaskovsky V.L. (Oliver) 14 55 30 12 42 580 08 Sep 2006
26 >Филин К.А. (E@gle-owl) 20 29 42 0 42 1969 08 Sep 2006
27 Zhadovecs S. (DarkTower) 6 64 9 32 41 308 07 Sep 2006

Изучаем SQL

Настройка операторов SQL на Microsoft SQL Server 2000 (продолжение, начало в вып.99)

Kevin Kline, Claudia Fernandez, Quest Software, Inc. (оригинал: Tuning SQL Statements on Microsoft SQL Server 2000)
Перевод Живенко Н.

SQL Server применяет три стратегии соединения. Они перечислены ниже по степени возрастания сложности.

Nested Loop (Вложенный Цикл)

Является наилучшей стратегией для маленьких таблиц с простыми внутренними соединениями. Лучше всего она работает в случае, когда одна таблица имеет сравнительно меньшее число записей по сравнению с другой таблицей, И обе они проиндексированы по соединяемым столбцам. Соединения с помощью вложенного цикла (Nested loop) требуют наименьшего числа операций ввода-вывода и наименьшего количества сравнений.

Цикл Nested loop проходит один раз все записи во внешней таблице (желательно, в меньшей таблице), на каждом шаге которого выполняется поиск совпадений во внутренней таблице и формируется выходной набор. Существует много названий для конкретных стратегий вложенных циклов. Например, соединение с помощью примитивного вложенного цикла (naive nested loop join) относится к случаю, когда происходит поиск по всей таблице или индексу. Соединением с помощью индексного вложенного цикла (index nested loop join) или соединением с помощью временного индексного вложенного цикла (temporary index nested loop join) называется соединение, когда используется постоянный или временный индекс.

Merge (Слияние)

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

Соединения Merge имеют преимущества для предварительно отсортированных наборов, выбирая по строке из каждого входного набора и выполняя прямое сравнение. Например, внутренние соединения возвращают записи, когда предикаты соединения есть равенство. Если они не равны, то запись с меньшим значением отбрасывается, и для сравнения выбирается следующая запись. Этот процесс продолжается до тех пор, пока не будут проверены все записи. Иногда соединения слиянием используются для сравнения таблиц в отношениях "многие-ко-многим". В этом случае SQL Server использует временную таблицу для хранения строк. Если в запросе с соединением merge также существует предложение WHERE, то предикат join merge оценивается первым. Затем записи, полученные после выполнения предиката merge join, проверяются на удовлетворение другим предикатам в предложении WHERE. Microsoft называется такие предикаты остаточными.

Хэш (Hash)

Hash join является лучшей стратегией для больших таблиц разного размера или для сложных условий соединения, когда соединяемые столбцы не индексированы или отсортированы. Хэширование используется для операций UNION, INTERSECT, INNER, LEFT, RIGHT и FULL OUTER JOIN, а также для множественных операций соответствия и расхождения. Хэширование также используется для соединений таблиц, когда не существует полезных индексов. Операции хэширования создают временную хэш-таблицу и затем циклически обходит все данные, формируя выходной поток.

Hash использует входной поток создания хэш-таблицы (build input) (всегда меньшая таблица) и входной поток зондирования (probe input). Для формирования соединения запрос использует хэш-ключ (т.е. столбцы, указанные в предикате соединения (join) или иногда перечисленные в списке GROUP BY). Остаточными предикатами в этом случае являются любые критерии, указанные в предложении WHERE, которые не используются в самом предикате соединения. Остаточные предикаты проверяются после предикатов соединения. Существует несколько различных опций, которые SQL Server выбирает при формировании hash join. Они указаны в порядке старшинства:

In-memory Hash: Соединения in-memmory hash создают в оперативной памяти временную хэш-таблицу при первом сканировании входного потока создания в память. Каждая запись вставляется в хэш-сегмент (hash bucket), определяемый хэш-значением, вычисленном для хэш-ключа. Далее входной поток зондирования сканируется запись за записью. Каждое значение входного потока зондирования сравнивается с соответствующим хэш-сегментом, и при совпадении заносится в результирующий набор.

Hybrid Hash (гибридное хэширование): Если размер хэш-таблицы незначительно превышает объем доступной памяти, SQL Server может использовать комбинацию методов in-memory hash join и grace hash join, это и будет называется соединением hybrid hash join.

Grace Hash: Способ grace hash используется, когда соединение хэшированием дает очень большой входной поток создания, который не может быть обработан в оперативной памяти. В этом случае полностью считываются входные потоки создания и зондирования. Затем они помещаются во множественные временные рабочие таблицы. Этот шаг называется секционированием (partitioning fan-out). Хэш-функция для хэш-ключей гарантирует, что все соединяемые записи находятся в одной и той же паре секционированных рабочих таблиц. Секционирование разбивает два больших шага на множество мелких шагов, которые могут обрабатываться параллельно. Хэш-соединение теперь применяется для каждой пары рабочих таблиц, и любые совпадения попадают в результирующий набор.

Recursive Hash (рекурсивное хэширование): Иногда секционированные таблицы, применяемые в Grace hash, остаются все еще достаточно большими и требуют дальнейшего секционирования. Это явление носит название recursive hash. Необходимо заметить что hash- и merge-соединения проходят каждую таблицу один раз. Поэтому они могут дать обманчиво невысокие показатели по числу операций ввода-вывода, если вы будете использовать команду SET STATISTICS IO ON с запросами этого типа. Тем не менее, низкий показатель операций ввода-вывода не означает, что эти стратегии соединения по определению быстрее, чем соединения с вложенными циклами, из-за их огромных вычислительных затрат.

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

В следующем примере показаны как стандартный вложенный цикл (nested loop) (использующий план выполнения запроса по умолчанию), так и hash- и merge-соединения (принудительное использование которых обеспечивается указаниями оптимизатору (hint)).

SELECT a.au_fname, a.au_lname, t.title
FROM authors AS a
INNER JOIN titleauthor ta
ON a.au_id = ta.au_id
INNER JOIN titles t

ON t.title_id = ta.title_id
ORDER BY au_lname ASC, au_fname ASC
StmtText
-----------------------------------------------------------------------------
|--Nested Loops(Inner Join, OUTER REFERENCES:([ta].[title_id]))
|--Nested Loops(Inner Join, OUTER REFERENCES:([a].[au_id]))
| |--Index Scan(OBJECT:([pubs].[dbo].[authors].[aunmind] AS [a]), ORDERED
FORWARD)
| |--Index Seek(OBJECT:([pubs].[dbo].[titleauthor].[auidind] AS [ta]),
SEEK:([ta].[au_id]=[a].[au_id]) ORDERED FORWARD)
|--Clustered Index Seek(OBJECT:([pubs].[dbo].[titles].[UPKCL_titleidind]
AS [t]), SEEK:([t].[title_id]=[ta].[title_id]) ORDERED FORWARD)

План, показанный выше, является стандартным планом выполнения запроса, который создает SQL Server. Можно потребовать с помощью указаний, чтобы SQL Serever показал, как бы он обрабатывал merge- и hash-соединения.

SELECT a.au_fname, a.au_lname, t.title
FROM authors AS a
INNER MERGE JOIN titleauthor ta
ON a.au_id = ta.au_id
INNER HASH JOIN titles t
ON t.title_id = ta.title_id
ORDER BY au_lname ASC, au_fname ASC
Warning: The join order has been enforced because a local join hint is used.
StmtText
-----------------------------------------------------------------------------
|--Sort(ORDER BY:([a].[au_lname] ASC, [a].[au_fname] ASC))
|--Hash Match(Inner Join, HASH:([ta].[title_id])=([t].[title_id]),
RESIDUAL:([ta].[title_id]=[t].[title_id]))
|--Merge Join(Inner Join, MERGE:([a].[au_id])=([ta].[au_id]),
RESIDUAL:([ta].[au_id]=[a].[au_id]))
| |--Clustered Index
Scan(OBJECT:([pubs].[dbo].[authors].[UPKCL_auidind]
AS [a]), ORDERED FORWARD)
| |--Index Scan(OBJECT:([pubs].[dbo].[titleauthor].[auidind] AS [ta]),
ORDERED FORWARD)
|--Index Scan(OBJECT:([pubs].[dbo].[titles].[titleind] AS [t]))

В данном примере ясно видно, что каждое из соединений рассматривает предикат другого соединения как остаточный предикат. (Также можно заметить, что при использовании указаний (hint) SQL Server выдает предупреждение.) Этот запрос также вынужден использовать оператор SORT, чтобы могли быть использованы hash- и merge-соединения.

(Продолжение следует...)

Полезная информация

§ Все статьи, публикуемые в рассылке, затем выкладываются на сайте Книги и статьи по SQL.

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

Контакты

По всем вопросам, связанным с функционированием сайта, проблемами при решении упражнений, идеями вы можете обращаться к Сергею И.Моисеенко msi77@yandex.ru. Вы также можете предложить свои задачи для публикации на сайте.

Подписка Subscribe.Ru
Новости сайта "Упражнения по SQL"

В избранное