Blogs

Построение индексов – Часть 4.

  • Comments 11
  • Likes

Параллельное, автономное построение несекционированного индекса (Offline, Parallel, No Partitioning).

 

Существует 3 основных категории паралльных планов построения индекса:

 

1)      Интервальное секционирование (для машин малой мощности);

2)      Интервальное секционирование (для высокопроизводительных машин);

3)      План для индексирования представления без гистограм (No histogram Indexed view).

 

Интервальное секционирование* (для машин малой мощности).

 

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

 

             X

                     /                |                \

Построитель… Построитель …  Построитель …  

                   |                  |                 |

Сортировка… Сортировка …  Сортировка …

                    \                 |                /

       Сканирование (для каждого исполнителя (worker))

 

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

1)      Уровень параллелизма (DOPDegree of parallelism) – число процессоров, которые могут быть использованны для построения индекса < 8

или DOP > 8, но память требуемая для постоения индекса превышает определенный % общей доступной обработчику запросов памяти (см. в следущем посте - интервальное секционирование (для высокопроизводительных машин));

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

 

Используя имеющуюся статистику обработчик запросов распределяет данные на N сегментов, где N = DOP * 3. Зная оценочное число строк для каждого сегмента объем работ делится на DOP секций между исполнителями – по одной секции на исполнителя (это делается для выравнивания нагрузки). Используя секционное сканирование каждый исполнитель получает данные принадлежащие к его секции, хотя для этого и приходится сканировать все данные для каждого исполнителя, т.е., если, например, DOP = 4, вся таблица будет просканирована 4 раза.

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

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

 

* Не путайте, пожалуйста, «интервальное секционирование (Range partition)» - тип параллельного плана построения индекса и «секционированный индекс (Partitioned Index)» - тип индекса.

 

В следующих сообщениях:

- Интервальное секционирование (для высокопроизводительных машин);

- План для индексирования представления;

- Требования к памяти при парллельном построении индексов;

...

Comments
  • Что понимается под "для машин малой мощности"?

    Насколько малой мощности?

  • Скажите, пожалуйста о каких объемах данных идет речь. Так как промежуточные результаты надо хранить на диске, то, вероятно это десятки мегабайт и более. Но могут ли это быть гигабайты?

  • Выше я имел в виду объем данных, идущих в индекс.

    Второй вопрос: какой примерно размер кеша в ОП используется при построении дерева индекса?

  • Еще один вопрос касается упомянутой ранее  предварительной сортировки. Это "полноценная" сортировка в классическом понимании, или грубая сортировка, т.е. разбиение элементов на группы (сегменты, кластеры и т.п.)

  • В предыдущем посте я забыл поставить знак вопроса :)

    Обсуждаемая тема интересует меня потому, что мне приходиться заниматься решением аналогичных задач для словарной базы данных в своем shareware-проекте ( http://www.jardicpro.com ). Пытаюсь достичь скорости построения полнотекстового индекса равной 1,000,000 строк в минуту на 1.6 Мгц процессоре (индекс с ключам переменой длины, Unicode collation, сжатие страниц индекса, суммарный объем индексов - 1-15 млн элементов).

  • По ряду причин время предварительной сортировки соизмеримо со временем построения дерева индекса, а иногда и может значительно превышать его. Таким образом, сократив время сортировки или избавившись от нее, можно увеличить скорость построения индекса в два и более раз. В каких случаях сортировка не приносит ощутимого эффекта? Ну, например, когда затрагиваемая часть дерева индекса целиком умещается в кеше. Еонечно, при этом увеличивается фрагментация индекса, но 100%-заполнение имеет смысл только для необновляемых баз данных, а случайное обновление индекса уже дает 75% заполнения. На практике размер дерева индекса значительно превышает размер кеша, но и здесь остаются пути для повышения эффективности за счет упрощения сортировки. Предположим, в индексе хранятся текстовые строки в алфавитном порядке, и в кеше помещается не все дерево индекса, а только его часть, которая содержит строки, начинающиеся на букву "А" ("Б", "В", и т.д.). Кстати, что значит "...если она не существует на момент создания индекса, она будет сгенерирована"? На основе каких данных выполняется генерация?

  • Давно не заходила в свой журнал - не было времени. А тут уже столько вопросов 

    По порядку...

    [Что понимается под "для машин малой мощности"?]

    В данном случае - < 8 процессоров либо - >= 8 процессоров, но недостаточно памяти (построение индекса может потребовать >3% достпной обработчику запросов памяти).

    [Скажите, пожалуйста о каких объемах данных идет речь. Так как промежуточные результаты надо хранить на диске, то, вероятно это десятки мегабайт и более. Но могут ли это быть гигабайты?]

    Могут быть и гигабайты. Зависит от Вашего конкретного индекса. Размер индекс можно очень грубо представить как размер ключа*число строк. Более подробно можно почитать здесь (на английском):  ms-help://MS.SQLCC.v9/MS.SQLSVR.v9.en/udb9/html/c183b0e4-ef4c-4bfc-8575-5ac219c25b0a.htm

    и здесь:

    ms-help://MS.SQLCC.v9/MS.SQLSVR.v9.en/udb9/html/2b5137f8-98ad-46b5-9aae-4c980259bf8d.htm

    По-русски эти статьи имеются в online документации к русскому SQL Server -у 2005.

    [какой примерно размер кеша в ОП используется при построении дерева индекса?]

    Зависит от того, сколько может выделить внутренний (SQL Server-ный) распределитель памяти. Исполнитель запросов всегда постарается запросить памяти достаточно для проведения сортировки в памяти целиком, но это, на самом деле скорее редкий случай, когда индекс действительно маленький. Распределитель памяти будет учитывать остальные исполняющиеся в это время процессы и общий размер памяти. Здесь только стоит помнить, что если распределитель памяти не сможет выделить для процесса построения индекс 40 страниц (3200Kb), то Create Index вернет ошибку - 40 страниц это абсолютный минимум, который необходим даже для построения индекса меньшего размера.

    [Это "полноценная" сортировка в классическом понимании]

    Да, полноценная сортировка.

    По поводу предварительной сортировки против построения дерева из неотсортированных данных… Добавление случайных (неотсортированных) данных в btree требует поиска по дереву при каждом добавлении – это, в общем, далеко не оптимальное решение.

    [Предположим, в индексе хранятся текстовые строки в алфавитном порядке, и в кеше помещается не все дерево индекса, а только его часть, которая содержит строки, начинающиеся на букву "А" ("Б", "В", и т.д.)]

    Вы здесь говорите о уже существующем индексе? Я не совсем поняла. Как эти строки попали в индекс в алфавитном порядке?

    [Кстати, что значит "...если она не существует на момент создания индекса, она будет сгенерирована"? На основе каких данных выполняется генерация?]

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

  • >> Добавление случайных (неотсортированных) данных в btree требует поиска по дереву при каждом добавлении – это, в общем, далеко не оптимальное решение.

    Поиск в дереве выполняется быстрее чем, соответствующая сортировка, т.к. дерево уже построено и потребуется даже не N*LogN, а просто LogN операций. Неоптимальным этот процесс окажется в случае вынужденных обращений к диску.

    ==========

    Итак, предположим, что в кеше помещается (поместится) часть дерева индекса, которая содержит строки, начинающиеся на букву "А" ("Б", "В" и т.д.). Тогда достаточно сортировать исходные строки только по первой букве, т.к. если мы подадим на вход сразу все строки, начинающиеся с буквы "А", то кеш будет использоваться эффективно (без обращений к диску) и вставка соответствующего блока строк в индекс может занять даже меньшее количество времени, чем полная сортировка этого блока строк (опять же, потому, что дерево уже частично построено в явном виде).

    Собственно, я хотел в общих чертах упомянуть о возможных способах оптимизации. Описанны�� выше метод можно переформулировать, заменив фразу "на букву А" фразой "1000 ключей" и т.п. Хотел узнать, используется ли у вас что-то подобное и применить это у себя ;) Спасибо.

  • Интересно узнать ответы еще на такие вопросы:

    * Всегда ли число исполнителей равно числу просессоРов?

    * Запускаются ли несколько исполнителей в однопроцессорной системе?

    * Приведите, пожалуйста грубую оценку: во сколько раз сокращается время построения индекса если вместо одного исполнителя работают два (три) исполнителя?

    * Сколько процентов от общего времени уходит на каждый из этапов: сканирование / сортировка / построение / слияние?

    Заранее спасибо.

  • >>Неоптимальным этот процесс окажется в случае вынужденных обращений к диску.

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

    >>Всегда ли число исполнителей равно числу просессоРов

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

    >>Приведите, пожалуйста грубую оценку: во сколько раз сокращается время построения индекса если вместо одного исполнителя работают два (три) исполнителя?

    Не готова так сходу ответить. Определенно меньше, чем в два (для двух исполнителей).

    >>Сколько процентов от общего времени уходит на каждый из этапов: сканирование / сортировка / построение / слияние?

    Очень зависит от типа построения индекса (я еще буду об этом писать в дальнейшем).

  • >> Определенно меньше, чем в два (для двух исполнителей).

    Дык...

Your comment has been posted.   Close
Thank you, your comment requires moderation so it may take a while to appear.   Close
Leave a Comment