Russian version

Добавить на Del.icio.us

English version

Добавить на Digg.com

 dkLab | Конструктор | dkLab PostgreSQL patch: работа с очень большими int-массивами 

Карта сайта :: Форум «Лаборатории» :: Проект «Денвер»
Проект «Orphus» :: Куроводство: наблы :: Конструктор :: Копилка

Обсудить статью в форуме Скачать исходные коды На странице: intagg.int_array_append_aggregate(int[]): слияние нескольких массивов в один большой intarray._int_group_count_sort(int[], bool): сортировка по частоте intarray.bidx(int[], int): поиск методом деления пополам в отсортированном массиве Резюме

Скачать dkLab PostgreSQL intarray and intagg patch:
dklab_postgresql_patch_2008-05-20.tgz

dkLab PostgreSQL patch — это небольшой набор патчей для PostgreSQL 8.3, а именно, для расширений ("контрибов") intarray и intagg. Он добавляет 3 написанные на C (а потому быстрые) функции для работы с очень большими наборами предварительно отсортированных массивов.

Чтобы наложить эти патчи, запустите приведенные ниже команды, а затем пересоберите PostgreSQL из исходных кодов, как обычно:

скопировать код в буфер обмена Листинг 1: Наложение патчей

$ cd postgresql-8.3.* $ patch < /your/path/to/dklab_postgresql_patch_intagg.patch $ patch < /your/path/to/dklab_postgresql_patch_intarray.patch $ ./configure && make install

Посмотреть исходный код патчей:
dklab_postgresql_patch_intagg.patch
dklab_postgresql_patch_intarray.patch

intagg.int_array_append_aggregate(int[]): слияние нескольких массивов в один большой

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

скопировать код в буфер обмена Листинг 2: int_array_append_aggregate - пример использования

CREATE TABLE doc(doc_id INTEGER, doc_word_ids INTEGER[]); INSERT INTO doc(doc_id, doc_word_ids) VALUES(1, '{123, 456, 789, 111}'); ... SELECT int_array_append_aggregate(doc_word_ids) FROM doc; /* Возвращает ID всех слов, встречающихся во всех документах. */

Даже если таблица doc содержит 10000 строк, каждая из которых имеет по 1000 ID слов в поле doc_word_ids, выполнение запроса займет всего несколько миллисекунд.

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

intarray._int_group_count_sort(int[], bool): сортировка по частоте

INTEGER[][] _int_group_count_sort(list_sorted INTEGER[], sort_asc BOOLEAN)

Представьте, что у вас есть очень большой отсортированный массив целых чисел, значения в котором могут повторяться. Вам нужно определить, какие из значений в массиве встречаются наиболее часто, а какие — наименее. Функция _int_group_count_sort() поможет вам это сделать, затратив минимум ресурсов процессора даже при работе с очень большим массивом. В некоторых случаях функция дает более чем тысячекратный прирост производительности по сравнению со стандартным использованием запроса вида "GROUP BY ... ORDER BY COUNT(*)".

скопировать код в буфер обмена Листинг 3: _int_group_count_sort - пример использования

list_sorted := '{ 1, 1, 1, 6, 6, 7, 7, 7, 7 }'; groups := _int_group_count_sort(list_sorted); /* Результат: { { 4, 7 }, { 3, 1 }, { 2, 6 } } */

Как видите, функция возвращает двумерный массив. Первый элемент каждого подмассива равен частоте вхождения величины в исходный массив, а второй — самой этой величине. Результат отсортирован по убыванию (sort_asc = false) или возрастанию (sort_asc = true) частоты вхождения величин.

Обратите внимание на то, что входной массив ОБЯЗАТЕЛЬНО должен быть отсортирован (используйте функцию intarray.sort()), иначе _int_group_count_sort() будет возвращать неверный результат.

Имя _int_group_count_sort выглядит, возможно, странновато, однако таков уж принятый стандарт именования функций в модуле intarray...

intarray.bidx(int[], int): поиск методом деления пополам в отсортированном массиве

INTEGER bidx(INTEGER[] list_sorted, INTEGER value)

Данная функция реализует алгоритм поиска "методом деления пополам" в отсортированном массиве. Она возвращает позицию элемента value в отсортированном массиве list_sorted или 0, если элемент найти не удалось. Алгоритм поиска очень быстр и может обрабатывать тысячи массивов за единицы миллисекунд. Функция может быть использована, если вы хотите быстро отфильтровать значения в большом наболе целых чисел внутри хранимой процедуры или SQL-запроса. Вот иллюстрация использования функции:

скопировать код в буфер обмена Листинг 4: bidx - пример использования

list := ARRAY(SELECT * FROM generate_series(2,1000000,1)); SELECT bidx(list, 765432); /* возвращает 765431, позицию числа 765432 */ SELECT bidx(list, -100); /* возвращает 0, элемент не найден */

Обратите внимание на то, что входной массив ОБЯЗАТЕЛЬНО должен быть отсортирован (используйте функцию intarray.sort()), иначе bidx() будет возвращать неверный результат.

Резюме

Функции в составе dkLab PostgreSQL patch могут быть полезны при разработке высоконагруженных проектов, которым не хватает чисто реляционных возможностей SQL, а работа происходит с большими массивами целых чисел (например, ID объектов).