СОДЕРЖАНИЕ

1.	СОВЕТЫ
1.1.	Счётчики производительности SQL Server и Windows (продолжение)
1.2.	Динамика иерархии при навигации во многомерных кубах
1.3.	Как быстро можно сортировать натуральные числа?
2.	ССЫЛКИ НА СТАТЬИ
2.1.	Статьи на русском языке
2.2.	Новые и обновлённые технические статьи Microsoft
2.3.	Англоязычные статьи
3.	ФОРУМ SQL.RU
3.1.	Самые популярные темы недели
3.2.	Вопросы остались без ответа
4.	ПОЛЕЗНОСТИ
4.1.	Как создать SQL-скрипт на содержимое таблицы?

СОВЕТЫ

Счётчики производительности SQL Server и Windows

1.    Введение
2.    Анализ узких мест
3.    Счётчики
4.    Типы счётчиков
5.    Память
5.1. Поиск узких мест использования памяти Windows 2000
5.2. Наборы счётчиков мониторинга памяти
5.3. Системная таблица sysperfinfo
5.4. Диагностика всплесков отложенной записи
6.    Процессор
6.1. Поиск узких мест использования процессора Windows 2000
6.2. Набор счётчиков мониторинга процессоров

7. Дисковая подсистема

7.1. Поиск узких мест использования дисковой подсистемы сервера Windows 2000

Во время исследования производительности дисковой подсистемы Вы должны попытаться локализовать причину возникновения узкого места в операциях дискового ввода/вывода, осуществляемых SQL Server, используя вначале собственные счётчики сервера баз данных, а для более детального контроля, счетчики PhysicalDisk и LogicalDisk. Счётчики логических дисков контролируют логические диски NT (т.е. имена дисков) в то время как счетчики физических дисков контролируют то, что в оснастке управления дисками видно, как отдельные физические устройства.
Чтобы определить объём ввода/вывода, порождаемый компонентами SQL Server, исследуйте следующие аспекты производительности: Запись страниц на диск и чтение страниц с диска. Количество считанных и записанных страниц, которые использует SQL Server, может быть проверено с помощью счётчиков SQL Server\Buffer Manager\Page Reads/sec и Page Writes/sec. Если эти значения начинают приближаться к пропускной способности аппаратных средств подсистемы ввода/вывода, попробуйте уменьшить их значения, настраивая ваши приложения или базу данных так, чтобы уменьшить операции ввода/вывода (например: охват индексами, улучшение индексов или выполнение нормализации), повысить производительность ввода/вывода имеющихся аппаратных средств, или добавить оперативную память.
Для того, что бы подключить, отключенный по умолчанию из соображений производительности, сбор информации по счётчикам логического диска, которые необходимы для поиска узких мест дисковой подсистемы, запустите из командной строки: diskperf -yv. Для того, что бы прекратить сбор данных этих счётчиков, выполните команду diskperf -nv.

Формат команды:

diskperf [-y[d|v]|-n[d|v] [\\компьютер]

Где:

Отсутствие параметров - выдаёт информацию о том, включены ли счетчики производительности диска на локальном или указанном компьютере и показывает включенные счетчики: для физических дисков, логических дисков или для дисков обоих типов.
-y - Задает запуск счетчика для логического и физического дисков после перезапуска системы.
-yd - После перезапуска системы включает счетчики производительности диска для измерения быстродействия физических дисков. Этот режим устанавливается по умолчанию.
-yv -После перезапуска системы включает счетчики производительности диска для измерения быстродействия логических дисков.
-n - Задает отключение счетчика после перезапуска системы.
-nd - Отключает счетчики производительности для физических дисков после перезапуска системы.
-nv - Отключает счетчики производительности для логических дисков после перезапуска системы.
Компьютер - Задает имя компьютера в сети, состояние счетчика дисковой производительности которого представляет интерес. Если имя компьютера не указано, предполагается компьютер, на котором выполняется команда.

Во время сбора данных по счётчикам производительности диска, журнал статистики счётчиков располагайте на другом диске или компьютере, чтобы процесс журналирования не мешал исследованию диска.
При наличии в системе динамического тома, содержащего несколько физических дисков, они будут выглядеть как "Диск 0 C:", "Диск 1 C:" и "Диск 2 D:", где диск C: состоит из физических дисков 0 и 1. При наличии на диске двух логических разделов, они будут обозначаться как "0 C: D:".
Обычно дисковое устройство содержит один шпиндель, а RAID - массив имеют несколько шпинделей. Аппаратные RAID - массивы представляются в системном мониторе в виде единого диска, а программно организованные дисковые массивы, в виде нескольких томов (экземпляров). Наблюдение за счетчиками физического диска может вестись как для каждого физического диска, так и для всех дисков компьютера (используя экземпляр "_Total").Статистика отдельных дисков RAID массива недоступна, её можно получить с помощью поставляемого к RAID-контроллеру программного обеспечения. Также, при использовании аппаратных дисковых массивов, значение счетчика LogicalDisk| PhysicalDisk\% Disk Time может превышать 100%. Для определения среднего числа системных запросов, ожидающих доступа к диску, используйте в таких случаях счетчик PhysicalDisk\Avg. Disk Queue Length.

Объект \ счетчик	Рекомендуемое пороговое значение	Комментарий	Тип
LogicalDisk|PhysicalDisk\% Disk Time (Логический|Физический диск\% активности диска)	90%	Процент времени, затраченного выбранным дисковым устройством на обработку запросов на чтение и запись данных. Для регулировки нагрузки на сетевые серверы необходимо знать, какова нагрузка на их жесткие диски. Для этого служит счетчик "% активности диска", показывающий время активности диска в процентах. Если значение счетчика высоко (более 90%), следует проверить значение счетчика "Текущая длина очереди диска" для определения числа системных запросов, ожидающих доступа к диску. Количество ожидающих запросов ввода/вывода в установившемся режиме не должно превышать более чем в 1,5-2 раза количество физических дисков в дисковом устройстве. Поскольку данные этого счетчика могут охватывать больше чем один физический диск, а следовательно преувеличивать значение дисковой активности, необходимо сравнивать это значение со счётчиком "Процент времени бездействия", что бы откорректировать погрешность. По умолчанию этот счетчик не может превышать 100%. Однако, Вы можете внести изменения в системный реестр, которые позволят в System Monitor увидеть значения превышающие 100%.	PERF_PRECISION_100NS_TIMER
LogicalDisk|PhysicalDisk\ Disk Reads/sec (Обращений чтения с диска/сек), LogicalDisk|PhysicalDisk\Disk Writes/sec (Обращений записи на диск/сек)	Зависит от спецификаций производителя диска.Обычно диски Ultra Wide SCSI могут выполнять от 50 до 70 операций ввода/вывода в секунду.	Обращений чтения с диска/сек - это частота выполнения операций чтения с этого диска. Обращений записи на диск/сек - это частота выполнения операций записи на этот диск. Проверьте указанную на диске скорость передачи, чтобы удостовериться, соответствует ли реально наблюдаемая скорость спецификациями.	PERF_COUNTER_COUNTER
LogicalDisk|PhysicalDisk\Current Disk Queue Length (Текущая длина очереди диска), LogicalDisk|PhysicalDisk\Avg. Disk Queue Length (Средняя длина очереди диска)	Количество шпинделей плюс 2	Количество невыполненных запросов к диску во время сбора сведений о загруженности. Сюда включаются запросы, обслуживаемые во время проведения замера. Этот показатель представляет собой конкретное текущее значение, и не является средним значением по некоторому интервалу времени. Многошпиндельные дисковые устройства могут обрабатывать одновременно несколько запросов, остальные имеющиеся запросы будут ожидать обслуживания. Этот счетчик может отражать постоянные изменения длины очереди, показывая то большую, то малую ее длину, но если имеется перегрузка дискового устройства, то, вероятно, что значение этого счетчика будет большим постоянно. Время задержки обработки запросов пропорционально длине этой очереди минус количество шпинделей дисковых устройств. Для хорошей производительности системы среднее значение этого счетчика не должно превышать 2. Current Disk Queue Length является моментальным счётчиком, поэтому используйте несколько значений, измеренные в разные моменты времени. Для получения среднего значения во времени воспользуйтесь счетчиком Avg. Disk Queue Length. Значения счетчиков "Текущая длина очереди диска" и "% активности диска" позволяют отыскать узкие места в дисковой подсистеме. Если значения счетчиков "Текущая длина очереди диска" и "% активности диска" высоки в течение длительного времени, следует рассмотреть возможность обновления дисков или перемещения некоторых файлов на другие диски.	PERF_COUNTER_RAWCOUNT
LogicalDisk\% Free Space (Логический диск\ % свободного места)	15%	Доля свободного места, имеющегося на логическом диске, по отношению к общему объему выбранного логического диска. При вычислении значения _Total, счетчики %Free Space пересчитываются, как сумма процентов каждого диска. Не существует счетчика % Free Space для физических дисков.	PERF_RAW_FR ACTION
LogicalDisk|PhysicalDisk\Avg. Disk Bytes/Transfer (Средний размер одного обмена с диском (байт))	>20 Кбайт	Среднее количество байт данных, переданных при выполнении операций чтения или записи. Показывает объём операций ввода - вывода. Диск является эффективным, если он передает большие количества данных относительно быстро. Следите за этим счетчиком при измерении максимальной производительности. Также следует проверить показания счетчика "Средний размер одного обмена с диском (байт)". Значение больше 20 Кбайт обычно говорит о хорошей производительности диска, меньшие значения будут в случае, если приложение использует диск неэффективно. Например, если приложения обращающиеся к данным на диске в произвольном порядке, увеличивается значение счетчика "Среднее время обращения к диску (сек)", так как передача данных случайным образом увеличивает время поиска данных на диске. Чтобы более детально анализировать передаваемые данные, используйте счётчик Avg. Disk Bytes/Read и Avg. Disk Bytes/Write	PERF_AVERAGE_BULK
LogicalDisk|PhysicalDisk\Avg. Disk sec/Transfer (Среднее время обращения к диску)	< 0,3 секунды	Время в секундах, затрачиваемое в среднем на один обмен данными с диском. Счетчик отражает время, затрачиваемое на выполнение запросов к диску. Большое значение говорит о том, что контроллер диска постоянно повторяет попытки обращения к диску из-за его неисправности. Эти повторные попытки увеличивают среднее время обращения к диску. Для большинства дисков наибольшее среднее время обращения составляет не более 0,3 секунды. Для дальнейшего анализа обмена данными используйте счётчики Avg. Disk sec/Read и Avg. Disk sec/Write.	PERF_AVERAGE_TIMER

[В начало]

7.2. Набор счётчиков мониторинга дисковой подсистемы

Для контроля производительности дисковой подсистемы сервера Windows 2000, используйте следующий набор, дополнительных к указанным выше, счётчиков:

Объект \ счетчик	Комментарий	Тип
LogicalDisk|PhysicalDisk\% Disk Read Time (% активности диска при чтении)	Процент времени, затраченного выбранным дисковым устройством на обработку запросов на чтение данных.	PERF_PRECISION_100NS_TIMER
LogicalDisk|PhysicalDisk\% Disk Write Time (% активность диска при записи)	Процент времени, затраченного выбранным дисковым устройством на обработку запросов на запись данных.	PERF_PRECISION_100NS_TIMER
PhysicalDisk\% Idle Time	Говорит о том, какую часть времени интервала измерения диск бездействовал. Как уже говорилось выше, если этот счетчик анализировать совместно с % Disk Time, помните, что % Disk Time может превышать 100 процентов, т.к. он может завышать значения использования дисков.	PERF_PRECISION_100NS_TIMER
LogicalDisk\Avg. Disk Bytes/Read (Средний размер одного чтения с диска (байт))	Среднее количество байт данных, полученных с диска при выполнении операций чтения.	PERF_AVERAGE_BULK
LogicalDisk\Avg. Disk Bytes/Write (Средний размер одной записи на диск (байт))	Среднее количество байт данных, переданных на диск при выполнении операций записи.	PERF_AVERAGE_BULK
LogicalDisk|PhysicalDisk\Avg. Disk Queue Length (Средняя длина очереди диска)	Среднее общее количество запросов на чтение и на запись, которые были поставлены в очередь для соответствующего диска в течение интервала измерения. Вычисляется число запросов, которые были поставлены в очередь и ожидают обращения к диску в течение базового интервала измерения, а также запросов на обслуживание. В итоге, может показывать завышенные значения. Если более двух запросов непрерывно ожидают обращения к одной дисковой подсистеме, диск может быть узким местом. Чтобы уточнить данные о длине очереди, используйте счётчики: Avg. Disk Read Queue Length и Avg. Disk Write Queue Length.	PERF_COUNTER_LARGE_QUEUELEN_TYPE
LogicalDisk\Avg. Disk Read Queue Length (Средняя длина очереди чтения диска)	Среднее количество запросов на чтение, которые были поставлены в очередь для соответствующего диска в течение интервала измерения.	PERF_COUNTER_LARGE_QUEUELEN_TYPE
LogicalDisk\Avg. Disk Write Queue Length (Средняя длина очереди записи на диск)	Среднее количество запросов на запись, которые были поставлены в очередь для соответствующего диска в течение интервала измерения.	PERF_COUNTER_LARGE_QUEUELEN_TYPE
LogicalDisk\Avg. Disk sec/Read (Среднее время чтения с диска)	Время в секундах, затрачиваемое в среднем на одну операцию чтения данных с диска.	PERF_AVERAGE_TIMER
LogicalDisk\Avg. Disk sec/Write (Среднее время записи на диск)	Время в секундах, затрачиваемое в среднем на одну операцию записи данных на диск.	PERF_AVERAGE_TIMER
LogicalDisk|PhysicalDisk\Disk Bytes/sec (Скорость обмена с диском (байт/сек))	Показывает пропускную способность дисковой системы.Это скорость, с которой происходит обмен данными с диском при выполнении операций чтения или записи.Для дальнейшего анализа данных об обмене, основанных на чтений и записи, используйте счётчики: Disk Read Bytes/sec и Disk Write Bytes/sec соответственно.	PERF_COUNTER_BULK_COUNT
LogicalDisk\Disk Read Bytes/sec (Скорость чтения с диска (байт/сек))	Скорость, с которой происходит передача данных с этого диска при выполнении операций чтения.	PERF_COUNTER_BULK_COUNT
LogicalDisk|PhysicalDisk\Disk Transfers/sec (Обращений к диску/сек)	Частота выполнения операций чтения и записи на этот диск. Вычисляется число операций чтения и записи в секунду, независимо от того, сколько данных они включают. Измеряет утилизацию дисков. Если значение превышает 50 (у физического диск, состоящего из набора страйпов), то вероятно возникновение узкого места. Продолжить анализ обмена данными при операциях чтения и записи можно с помощью счётчиков: Disk Read/sec и Disk Writes/sec соответственно.	PERF_COUNTER_COUNTER
LogicalDisk\Disk Write Bytes/sec (Скорость записи на диск (байт/сек))	Скорость, с которой происходит передача данных на этот диск при выполнении операций записи.	PERF_COUNTER_BULK_COUNT
LogicalDisk\Free Megabytes (Свободно мегабайт)	Показывает объем незанятого пространства на диске в мегабайтах. Один мегабайт равен 1048576 байтам. Не существует подобного Free Megabytes счетчика для физических дисков.	PERF_COUNTER_RAWCOUNT
LogicalDisk|PhysicalDisk\Split IO/sec (Расщепления ввода-вывода/сек)	Вычисляет частоту, с которой операции ввода-вывода диска оказываются расщепленными на несколько операций ввода-вывода. Расщепление операций ввода-вывода может происходить либо из-за того, что запрошен слишком большой блок данных, который не может быть передан за одну операцию, либо из-за фрагментации диска. На расщепление I/O запроса влияет дизайн прикладных программ, файловая система или драйверы. Высокая норма расщеплений I/O не может сам по себе представлять проблему. Однако, если речь идёт о единичном диске, высокая норма для этого счетчика может указывать на фрагментацию диска.	PERF_COUNTER_COUNTER

ПРОДОЛЖЕНИЕ СЛЕДУЕТ

[В начало]

Динамика иерархии при навигации во многомерных кубах

Автор: Александр Денисенко

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

Постановка задачи

Имеется иерархическая структура и набор элементов. Элементы отображены на узлы структуры.
Соответствие элемента узлу иерархии зависит от времени. На каждом элементе задана функция времени. Задачей навигации является изображение суммарных значений в узлах любого уровня иерархической структуры.

Пример 1 (Торговля)

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

Пример 2 (Производство)

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

Особенности навигационного подхода

Набор программ для каждого из приведенных примеров на любом распространенном языке программирования не очень сложен. Но почти всегда при перемещении элементов он должен меняться в некоторых местах кода, то есть программный код неустойчив. В таких системах как [1] суммарные (и другие аггрегирующие) значения получаются автоматически при навигации наблюдателя по соотвествующим координатам и узлам иерархии. Можно сказать, что типовые фрагменты программного кода автоматически запускаются в ответ на то или иное движение наблюдателя по экрану. Во многих случаях вообще не требуется программного кода либо он незначителен. Это достигается за счет проектирования координат куба в виде иерархической структуры элементов по каждой из координатных осей и встроенных способов получения суммирующих данных при восхождении по иерархии элементов. Однако при смене иерархии (перемещении элементов по узлам) вообще говоря требуется заново формировать куб, что приводит к потере информации об элементах в прошлые моменты времени (в соответствии с отображением элементов на узлы структуры в предшествующие моменты времени). В примере из торговли при перемещении кассового аппарата в другую торговую точку вся итоговая отчетность искажается так, как если бы аппарат все время находился в новом месте. В производственном примере при перестройке куба, необходимой после перемещения сотрудника в другой цех (так называемое обновление куба - термин "refresh" в [1]) рабочее время сотрудника будет зачтено в новом подразделении и утрачено в старом - как если бы он весь период работал на новом рабочем месте.

Нам потребуется один вспомогательный термин из смежных проблемных областей - понятие "морф" элемента, то есть его разновидность, зависимая от временного (ударение на предпоследнем слоге) контекста. При перемещении элемента по узлам иерархии создается его новый морф (или редакция). В морфе есть две части - бесконтекстная (постоянная, глобальная, универсальная - примером может служить GUID в [1]) и контекстная (переменная, локальная, динамическая). Отображение элементов на узлы иерархии подменим отображением их морфов на узлы в соответствии с интервалом существования морфа. Остается заменить в функции на каждом элементе (то есть в ленте кассового аппарата или табеле рабочего времени сотрудника) элемент на его текущий морф. Это несложное (однопроходное преобразование) так называемой фактовой таблицы.

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

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

Все описанные операцию могут быть выполнены стандартными средствами.

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

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

Приведем небольшой пример

Штатное расписание завода (иерархическая структура) включает отдел 2, в составе которого две Лаборатории, в которых предусмотрены должности инженеров, экономистов и операторов. В отделе кадров хранится список сотрудников (элементы), среди которых мы выделим Абрамова, Баранова и Васильева. Для удобства перенумеруем рабочие места и сотрудников (фамилии и названия подразделений могут изменяться).

Штатное расписание:

Отдел	Участок	Штатная единица	Код штатной единицы
Отдел 2	Лаб 21	Инженер	Ш2-21-1
Отдел 2	Лаб 21	Инженер	Ш2-21-2
Отдел 2	Лаб 21	Экономист	Ш2-21-3
Отдел 2	Лаб 21	Оператор	Ш2-21-4
Отдел 2	Лаб 22	Инженер	Ш2-22-1
Отдел 2	Лаб 22	Экономист	Ш2-22-2
Отдел 2	Лаб 22	Оператор	Ш2-22-3

Персоналии:

Сотрудник	Персональный Код
Абрамов	Е101
Борисов	Е203
Васильев	Е307

Динамика иерархии: 03 января Борисов переходит из Лаборатории 21 в Лабораторию 22

Фрагмент табеля учета рабочего времени (таблица фактов):

Дата	Сотрудник	Часы
2 янв	Е101	8
2 янв	Е203	8
2 янв	Е307	8
3 янв	Е101	8
3 янв	Е203	8
3 янв	Е307	8
4 янв	Е101	8
4 янв	Е203	8
4 янв	Е307	8

Для Борисова необходимы два морфа с периодами до 3 января и после:

Сотрудник	Морф	Период
Е101	М101-1	< 3 янв
Е203	М203-1	< 3 янв
Е203	М203-2	>= 3 янв

Используем соответствие морфов и штатных единиц:

Морф	Штатная единица
М101-1	Ш-2-21-1
М203-1	Ш-2-21-2
М203-2	Ш-2-22-2
М307-1	Ш-2-22-3

Теперь преобразуем фактовую таблицу с учетом морфов:

Дата	Код штатной единицы	Часы	Комментарий
2 янв	Ш-2-21-1	8	Абрамов
2 янв	Ш-2-21-2	8	Борисов (морф1)
2 янв	Ш-2-22-3	8	Васильев
3 янв	Ш-2-21-1	8	Абрамов
3 янв	Ш-2-22-2	8	Борисов (морф2)
3 янв	Ш-2-22-3	8	Васильев
4 янв	Ш-2-21-1	8	Абрамов
4 янв	Ш-2-22-2	8	Борисов (морф2)
4 янв	Ш-2-22-3	8	Васильев

Теперь стандартные функции аггрегирования будут отражать корректные значения функции. Рабочее время Абрамова до 3 января будет учитываться в составе Лаборатории 21, а с 3 января - в составе Лаборатории 22.

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

Морф	Родительский элемент
М101-1	Е101
М101-2	Е101
М203-1	Е203
М307-1	Е307

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

Источники:

[1]. Микрософт. SQL2000-OLAP. Электронная документация.

[В начало]

Как быстро можно сортировать натуральные числа?

Автор: Александр Денисенко

Сортировка Шелла является асимптотически оптимальной по сложности в смысле числа попарных сравнений элементов множества, предназначенного для сортировки. Если множество состоит из N элементов, то сложность такой сортировки - примерно N*LogN (логарифм двоичный).

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

Итак, имеется множество М={i1,…,ik} причем все i1,…,ik<N.
Требуется получить множество S, состоящее из элементов M в порядке возрастания (убывания).
Алгоритм состоит из не более чем трех шагов.
Шаг 1(подготовительный). Выделяем в памяти массив A[i] из N битов и обнуляем его.
Шаг 2 (основной). Считываем поочередно элементы массива M (одномерный проход) и для каждого элемента i устанавливаем в единицу бит A[i].
Шаг 3 (дополнительный). Проходим по массиву A[i] и для каждого единичного бита выдаем на выход - во множество S - номер соответствующего бита.

Нетрудно видеть, что алгоритм линеен, то есть его сложность - C*K.
Шаг 1 назван подготовительным, так как соответствующий массив может храниться в системе изначально (скажем, современная операционная система при выделении памяти сама заполняет его нулями по требованиям стандарта безопасности). Можно и заготовить такую константу.
Для множеств мощности до 1 миллиона - это всего 128 килобайт - две страницы сервера баз данных. Для множеств мощности до 100 миллионов потребуется обнуляемый вектор размера 12 мегабайт. Шаг 3 может и не требоваться - если результат носит промежуточный характер - мы просто перешли к другой кодировке множества.

Что касается теоретико-множественных операций над множествами рассматриваемой природы, то они сводятся очевидным образом к сортировке. В самом деле, для двух множеств M1 и M2 следует завести по вектору из нулей, затем выполнить Шаг 2 сортировки. Далее остается провести необходимую булевскую операцию (дизъюнкцию для объединения множеств, конъюнкцию - для пересечения и т.д.) и результат готов. Уместно заметить, что во многих системах разность множеств строится существенно сложнее суммы - что неестественно (сумма и разность чисел в процесссоре идет одинаково быстро, так как никакой разницы в алгоритмах нет).

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

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

[В начало]

ССЫЛКИ НА СТАТЬИ

Статьи на русском языке

Birdstep XML. Реализация стандартов SAX, DOM и XPATH
Interface Ltd
XML является универсальным форматом для структурированных документов и данных в интернет. Этот язык разметки, являющийся стандартом консорциума W3C (World Wide Web Consortium), используется для создания структурированного содержания и сопровождения метаданных о нем. На практике это означает, что XML позволяет организациям совместно использовать, обмениваться и публиковать данные универсальным и общепринятым образом. Более подробную информацию о XML можно получить по адресу www.w3.org/XML/.
Совместное использование учетных систем и технологии OLAP
CITFORUM.RU
В наше время без систем управления базами данных не обходится практически ни одна организация, особенно среди тех, которые традиционно ориентированы на взаимодействие с клиентами. Банки, страховые компании, авиа- и прочие транспортные компании, сети супермаркетов, телекоммуникационные и маркетинговые фирмы, организации, занятые в сфере услуг и другие - все они собирают и хранят в своих базах гигабайты данных о клиентах, продуктах и сервисах. Ценность подобных сведений несомненна. Они применяются для различных целей, например для управления материально-техническими запасами, управления отношениями с клиентами (CRM - customer relationship management), биллинга (формирования счетов) и т.п...
Применение OLAP технологий при извлечении данных
Арустамов Алексей
OLAP (Online Analyzing Processing) – это один из способов добычи и анализа данных. Суть заключается в том, что информация представляется в виде многомерного куба с возможностью произвольного манипулирования ею. По сухому описанию довольно трудно понять, зачем OLAP нужен и как он работает. Чтобы это лучше понять, я расскажу, как мы создавали свою OLAP систему – Cube. История очень показательна. Скорее всего, вы с аналогичными ситуациями встречались. Речь будет идти не о конкретной программе, а технологии...
Ядро OLAP системы
Алексей Стариков
Механизм OLAP является на сегодня одним из популярных методов анализа данных. Есть два основных подхода к решению этой задачи. Первый из них называется Multidimensional OLAP (MOLAP) – реализация механизма при помощи многомерной базы данных на стороне сервера, а второй Relational OLAP (ROLAP) – построение кубов 'на лету' на основе SQL запросов к реляционной СУБД. Каждый из этих подходов имеет свои плюсы и минусы. Их сравнительный анализ выходит за рамки этой статьи. Мы же опишем нашу реализацию ядра настольного ROLAP модуля...
Менеджмент качества и "электронная нервная система" Билла Гейтса
Валерий Матюшин, Александр Шадрин
"Электронная нервная система" современного предприятия, организованная в соответствии с принципами стандартов ИСО на базе современных технических средств, является основой, необходимым условием успеха предприятия. У информационных технологий и требований стандартов ИСО одна цель – эффективность предприятия, основанная на удовлетворении потребностей всех заинтересованных сторон, и один источник – кибернетика ...
OLAP-средства и Web-технологии
Intersoft Lab
Успешно развивающиеся технологии Хранилищ данных (ХД) и средств Business Intelligence (BI) – весьма полезные инструменты поддержки современного бизнеса. Однако большинству традиционных BI-приложений свойственны некоторые ограничения. Технология, на основе которой они реализуются, была разработана для анализа небольших выборок данных. Со временем круг пользователей расширялся, но ориентация на небольшие объемы данных при этом сохранялась. Наконец, появились технологии, предназначенные для обработки постоянно растущих огромных объемов данных, содержащихся в Хранилищах...
Создание приложения для карманных компьтеров с использованием БД
Александр Петров
Недавно мне поставили задачу по созданию приложения для карманного компьтера с использованием Microsoft Server CE 2.0. На создание приложения ушло гораздо блоше времени, чем предполагалось изначально (как обычно). На решение этой задачи мне отводилось 3 полных рабочих дня, однако пришлось много работать сверхурочно из-за весьма скудной документации по этой теме. Надеюсь мой опыт окажится полезным другим разаботчикам, работующим с Pocket PC. Ниже я приведу свой путь создания проекта. Для начала, думаю, стоит описать задание: «...Он представляет из себя программу для социологических опросов, тестов, изучения мнения покупателей. Приложение представляет из себя одно окно с несколькими элементами управленияю На форме присутствуют кнопки «следующий вопрос» и «результат сессии...
Обзор OLAP-продуктов для Web
Intersoft Lab
Как показал проведенный нами анализ, Web-архитектуры быстро вытесняют традиционные клиент/серверные приложения для целого ряда категорий программного обеспечения, и рынок корпоративных OLAP-решений здесь не исключение...

[В начало]

Новые и обновлённые технические статьи Microsoft

BUG: Error Message: "The colv1 parameter is shorter..." Occurs When Replicated Column is Updated
BUG: Error Message: "There is not enough space on drive" Occurs When You Extract SQL Server 2000 Downloads
BUG: Slow Performance with SQLOLEDB Inserting BLOB Data into SQL Server Using Stored Procedure
FIX: ADO Returns No Resultset for Prepared Parameterized Query Involving CHAR Data with SQLOLEDB
FIX: Bcp.exe with Long Query String Can Result in Assertion Failure
FIX: DTS Designer May Generate an Access Violation After You Install SQL Server 2000 SP3
FIX: Lock Monitor Exception in DeadlockMonitor::ResolveDeadlock
FIX: MS DTC Transaction Commit Operation Blocks Itself
FIX: Slow Execution of a Query that Contains a Correlated Subquery
FIX: Trace Flag -T8002 Treats an Affinity Mask Like a Process Affinity
FIX: Using xp_sendmail with a COMPUTE Clause Causes an Access Violation
FIX: Various Problems When You Call Transactional COM+ Components from ASP.NET
HOWTO: Perform Replication by Using SSCERelay and ActiveSync
HOWTO: Use Kerberos Authentication for Microsoft SQL Server 2000 Analysis Services
INF: Network Encryption Available Using the Multi-Protocol Net Library
INF: The Microsoft Support Policy for a SQL Server Failover Cluster
Post a Question to the Microsoft SQL Server Newsgroups
PRB: Connection to Analysis Services Fails After You Install Analysis Services SP3
PRB: Error 4928 Occurs When You Try to Rename a Non-Replicated Column
PRB: SQL Server 2000 Changes Name of RETURN_VALUE to @RETURN_VALUE
PRB: You Receive Error 7391 When You Run a Distributed Transaction Against a Linked Server
SQL Server 2000 Cluster Does Not Install on Windows Server 2003-Based Computers Where Terminal Services Is Installed in Application Mode
Support WebCast: Microsoft SQL Server 2000 SP 3a: What It Is, Why It Is, and Whether to Upgrade

[В начало]

Англоязычные статьи

DDL Archive Utility
Bill Wunder
If your shop is even close to the typical Microsoft SQL Server environment there are several people that can (and do!) make changes to the production environment, a change management system is in place, that change management system uses SourceSafe to store database scripts, and what's in SourceSafe does not match what's on the SQL Server. While most developers do a good job of keeping SourceSafe updated as production and other environments change, others just don't give a hoot, and some even consider the change management system a hindrance to job security. Bottom line for all the developers is "I just dropped my procedure/table/database/?, don't have a version in SourceSafe that is correct, and the DBA should fix this now. And while you're at it bring me another umpa-lumpa." So what can you do? What I do is generate a fresh copy of the scripts for each object in each user database every day. I manage the size of the history of the daily script files by storing the scripts in SourceSafe. This keeps me from having to keep track of versions or maintaining a cumbersome and ever growing collection of scripts on the file system. The latest version (and all the others) are there in SourceSafe and stored in a much more efficient and effective manner than I have time to create or support. I automate the script generation and SourceSafe Check In so that the scripts contain the same elements and thus avoid invalid differences from being recorded during the automated Check In processing. I used to run the automated pulls from the SQL Agent Job Scheduler of the Developer Edition SQL Server on my desktop as DTS packages that use ActiveX script steps to extract the scripts from the SQL Server via DMO and then move them to SourceSafe using the SourceSafe API. Using my desktop keeps me from having to install the SourceSafe client on one of my SQL Servers and also keeps most of the load from the pull and all of the load of the Check In off of any of the SQL Servers in the shop. The error handling and performance of the ActiveX scripts in DTS are less than ideal and there is little flexibility possible in what will be scripted and checked in. The Archive Utility puts a GUI on the ActiveX scripts and guides you through the easy configuration steps as you create your first copy of a DDL archive for a server. Then it lets you save the settings you provided for easy use the next time it runs. You'll always be ready for that next moment of human error...
Building Business Intelligence Data Warehouses
Tom Osoba
Business intelligence can improve corporate performance in any information-intensive industry. With applications like target marketing, customer profiling, and product or service usage analysis, businesses can finally use their customer information as a competitive asset. They can enhance their customer and supplier relationships, improve the profitability of products and services, create worthwhile new offerings, better manage risk, and reduce expenses dramatically. In order to capture the power of business intelligence, a proper data warehouse needs to be built. A data warehouse project needs to avoid common project pitfalls, be business driven, and deliver proper functionality
UDF as Computed Column Part 2
Dinesh Priyankara
If you have already read my previous article about UDF, hope now you know very well how to add UDF as computed column in table and why and when should use. In this article, I will show you more thing about UDF and let's see how useful it is.

[В начало]

ФОРУМ SQL.RU

Самые популярные темы недели

Start dll with extended store procedure
Testking vs Microsoft...
А кто нить юзает серваки с Itanium
Mеханизм слежения за изменениями в БД во всех ее обьектах. Sysobjects and text
Как большую базу ужать?
Книга Kalen Delaney "Inside Microsoft SQL Server 2000" в формате CHM
Доступ к системным таблицам
Тихие подляны upgrade 6.5->2000
Linked Servers - ODBC - dBase V - невидит содержимое таблиц
tree
Раздача прав юзверям
При инсерте серевер медленнее чем обычный комп?
MS VISIO 2002 в качестве CASE???? средства.
Подскажите как сделать sum(...)-sum(...)?
Про транзакции
Защита интелектуальной собственности :)
Открыть файл в хранимой процедуре
Люди объясните с триггером
!SOS!! DataEnvironment (VB6.0) видит только базы :master, model, msdb, tempdb ?
Зависание транзакции....
Запрос
Выбор сервера
совсем ламерский вопрос про транзакции
Взаимообратная репликация
Медленно грузятся большие recordset-ы
Merge replication
Нужен DB-Developer
Не могу найти описание ошибки №22029
Оптимизация ХП
Почему одним запросом работает медленнее чем в цикле ?
Убить подписку.
Скорость работы с функцией и без
Ситуация однако... Может кто чего знает ;-)
Отчет из процедуры
Как заставеть SQL Server Работать как Acess
Может ли Select блокировать таблицы
Помечтаем ?
SQL to Active Directory (ADSI)
работа с dbf
SOS!!! SOS!!! Excel !!!!
Остановка Distribution Agent при потере связи
database 'tempdb' is full
Как отключить identity?
Передача таблицы в качестве параметра
Динамическое создание таблицы в процедуре и возврат значений
SQLServer и 1C
есть ли на русском sql server 2000?
помогите совсем начинающему (ntext и прочее)
Чем пользоваться для архивирования больших баз данных
Указать родителя для разностного бэкапа
Microsoft SQL Server "Yukon" Beta1 released
Кoлбaсит не пo-детски! Выручaйте!
Differential backup trouble. Alert - need you help!
Вопрос по T-SQL
порядок возвращаемых UNION записей
А кто нибудь знает какой-нибудь буржуйский продукт, аналог 1C?
Winword from T-SQL
Зависание соединения
sp_password в триггере
Не получается освобождать библиотеки с extended stored procedures
PowerBuilder
При открытии списка серверов в EM или SM рубит екзешник.
Проблемы с отладкой процедур

[В начало]

Вопросы остались без ответа

pomogite s sql query
Материалы конференции Microsoft Tech-Ed 2003
Блокировка
set parseonly on
Какое железо нунжно...
Связанные серверы
sql 6.5 и Widows-2000
Размещение adittrace
Создание скрипта для переноса данных
Есть ли хорошие Sales менеджер по серверным платформам и комплектующим?
разбить интервалы на подинтервалы/corrected
Сервер остановился. ПОЧЕМУ?
помогите ламеру
И снова репликация...
Off - VSS
Книги по ADO.NET
HELP PLEASE
Ковертация Access в SQL Server
OpenQuery

[В начало]

ПОЛЕЗНОСТИ

Рассылка:  Вопросы и ответы по Microsoft SQL Server

Автор рассылки: Сергей Кошкин

Выпуск No. 22 от 2003-07-18
Вопрос : Как создать SQL-скрипт на содержимое таблицы?
Ответ

[В начало]