Джино: хостинг и веб-сервисы

Система Orphus
Russian version
Добавить на Del.icio.us
English version
Добавить на Digg.com

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

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


2008-05-20

Скачать 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 объектов).







Дмитрий Котеров, Лаборатория dk. ©1999-2016
GZip
Добавить на Del.icio.us   Добавить на Digg.com   Добавить на reddit.com