Хранение и быстрый доступ к элементам Materialized path в базе.

Здравствуйте! У нас в базе существует таблица, хранящая иерархию ( Parent_id -child_id). Тип id узлов иерархии- bigint. Тип выбран давно и его уже нельзя менять (во многих местах используется). Недавно понадобилось дополнительно произвести расчет данной иерархии ( с большим количеством данным). Кроме того, нужно было хранить цепочку (Materialized path), на основе которой получена связь parent_id-child_id. Пример :

parent_id-15926816
child_id - 15706021

Цепочка элементов

lpath- 15926816.15762121.15917825.16109332.15706021

В качестве типа поля lpath я стал использовать ltree.

CREATE TABLE test_gelt
(
parent_id bigint,
child_id bigint,
  lpath ltree
)
WITH (
  OIDS=FALSE
);


CREATE INDEX path_gist_idx
  ON test_gelt
  USING gist
  (lpath);


CREATE INDEX path_idx
  ON test_gelt
  USING btree
  (lpath);

В функциях часто нужно находить записи , где lpath содержит определенный участок:

select *
from public.test_gelt  gelt
where 
gelt.lpath ~ ('*.15697419.15891540.*') 

План выполнения:

Bitmap Heap Scan on test_gelt gelt  (cost=9677.33..334505.18 rows=100146 width=64)
  Recheck Cond: (lpath ~ '*.15697419.15891540.*'::lquery)
  ->  Bitmap Index Scan on path_gist_idx  (cost=0.00..9652.29 rows=100146 width=0)
        Index Cond: (lpath ~ '*.15697419.15891540.*'::lquery)

Выяснилось, что если таблица public.test_gelt содержит 1 млн записей, то выборка достаточно быстрая, однако на реальных данных в 100 млн записей, даже при использовании индекса path_gist_idx работа запроса увеличивается до 2 минут. Подозреваю,что я плохо оценил скорость ltree на больших данных. Не хочется переделывать plpg-функции, ориентированные на работу с ltree.

Что можете посоветовать для увеличения выборки данных ltree по индексу?
Какие могут быть альтернативные типы данных для хранения и быстрого поиска в materialized path с учетом 100 миллионной таблицы?

Rickkk,
интересно, каков размер индекса по ltree?

ну и вот rows=100146, холодные, при произвольном доступе [даже без сети] уже не менее 10 секунд. нет ? или у вас вся БД в памяти ?

лопата, проверил, размер индекса path_gist_idx - 15 ГБ . Размер test_gelt - 3 ГБ. Получается индекс в любом случае будет хранится на HDD, а не в памяти, ибо у нас не так много ОЗУ. Как оптимизировать скорость выборки?

Rickkk
лопата, проверил, размер индекса path_gist_idx - 15 ГБ . Размер test_gelt - 3 ГБ. Получается индекс в любом случае будет хранится на HDD, а не в памяти, ибо у нас не так много ОЗУ. Как оптимизировать скорость выборки?

ssd поставить или памяти больше чтобы все в RAM было... других вариантов нет, чудес не бывает... да и 15GB памяти не такой большой обьем (1.5TB RAM был бы вопрос другой но тоже решаемый при желании).
Доступ к данным на диске в 10.000-100.000 раз медленее чем доступ к данным в памяти.

--Maxim Boguk
www.postgresql-consulting.ru

В 9.5 обещают BRIN indexes
При нехватке памяти под индекс - самое то. Но это будет не раньше осени 2015.
http://michael.otacoo.com/postgresql-2/postgres-9-5-feature-highlight-brin-indexes/

tadmin
В 9.5 обещают BRIN indexes При нехватке памяти под индекс - самое то. Но это будет не раньше осени 2015. http://michael.otacoo.com/postgresql-2/postgres-9-5-feature-highlight-brin-indexes/

BRIN индексы они для ltree ну никак не помогут... они для скалярных типов только.

--Maxim Boguk
www.postgresql-consulting.ru

Rickkk,
из старых рецептов -- распараллелить чтение (позиционирование при произвольном доступе)
индексы -- на один физический диск[массив] , данные -- на другие
но это -- паллеатив

ну и подумать о докупке памяти [это пожалуй единственное], и о мерах, позволяющих там висеть нужным данным не вытесняясь.


А вообще-то приведите реальные запросы, а не выборку 100500 никому необозримых узлов. И полные explain analyze.

Rickkk
Какие могут быть альтернативные типы данных для хранения и быстрого поиска в materialized path с учетом 100 миллионной таблицы?

классический вариант с 3НФ, если у вас не стоит задач обработки действительно больших объёмов данных и/или экономии дискового пространства.

иначе - выносите данные за пределы SQL и индексируйте специально заточенными под это движками. sphinx'ом, например.

Уважаемые коллеги, спасибо за советы! Совет buddy_ekb мне показался особо ценным. Т.к. особо не хотелось менять функции по работе с полями ltree, я подумал про смену формата поля lpath на int[] из модуля intarray от тех же Бартунова и Сигаева. Поначалу были сомнения, поскольку тип id связи - bigint. Однако таких связей все 100 млн и вряд ли они будут серьезно прибавляться. Поэтому конвертирую parent_id и child_id в int и помещаю в массив int[] вместо lpath.

Далее, создаю индекс на новом поле-пути:

create index ipath_gelt_idx on public.test_gelt   using gin(ipath  gin__int_ops);

Соответственно поиск цепочек в поле int[], содержащих известные одиночные связи стал следующим:

select *
from public.test_gelt  gelt
where 
('15691032&15826865')::query_int ~~ ipath
and abs(idx(ipath, 15691032) -idx(ipath, 15826865))=1

В результате такого преобразования:

-с наименьшими изменениями я модифицировал функции для работы с цепочками
-приблизительно раз в 10 ускорил выборку цепочек, где присутствуют те или иные одиночные связи.
-размер индекса ipath_gelt_idx оказался 1.5 Гб.


Вывод:
-видимо ltree хранит данные в формате text, поэтому индекс по этому полю был столь большим (15 Гб)
-если в цепочке присутствуют только числа, то лучше использовать intarray вместо ltree. при больших объемах таблицы цепочек замедление поиска особенно ощутимо.