PostgreSQL: как оптимизировать мою базу данных для хранения и запроса огромного графика

Question

Я использую PostgreSQL 8.3 на 1,83 ГГц Intel Core Duo Mac Mini с 1 ГБ оперативной памяти и Mac OS X 10.5.8. Я храню огромный граф в моей базе данных PostgreSQL. Он состоит из 1,6 миллиона узлов и 30 миллионов ребер. Моя схема базы данных выглядит так:

CREATE TABLE nodes (id INTEGER PRIMARY KEY,title VARCHAR(256));
CREATE TABLE edges (id INTEGER,link INTEGER,PRIMARY KEY (id,link));
CREATE INDEX id_idx ON edges (id);
CREATE INDEX link_idx ON edges (link);

Данные в краях таблицы выглядят как

id link 
1  234
1  88865
1  6
2  365
2  12
...

Таким образом, он сохраняет для каждого узла с идентификатором x исходящую ссылку на идентификатор y.

Время поиска всех исходящих ссылок в порядке:

=# explain analyze select link from edges where id=4620;
                           QUERY PLAN                                                        
    ---------------------------------------------------------------------------------
     Index Scan using id_idx on edges  (cost=0.00..101.61 rows=3067 width=4) (actual time=135.507..157.982 rows=1052 loops=1)
       Index Cond: (id = 4620)
     Total runtime: 158.348 ms
    (3 rows)

Однако, если я ищу входящие ссылки на узел, база данных будет более чем в 100 раз медленнее (хотя итоговое количество входящих ссылок только в 5-10 раз превышает количество исходящих ссылок):

=# explain analyze select id from edges where link=4620;
                         QUERY PLAN                                                           
----------------------------------------------------------------------------------
     Bitmap Heap Scan on edges  (cost=846.31..100697.48 rows=51016 width=4) (actual time=322.584..48983.478 rows=26887 loops=1)
       Recheck Cond: (link = 4620)
       ->  Bitmap Index Scan on link_idx  (cost=0.00..833.56 rows=51016 width=0) (actual time=298.132..298.132 rows=26887 loops=1)
             Index Cond: (link = 4620)
     Total runtime: 49001.936 ms
    (5 rows)

Я пытался заставить Postgres не использовать растровое сканирование через

=# set enable_bitmapscan = false;

но скорость запроса входящих ссылок не улучшилась:

=# explain analyze select id from edges where link=1588;
                      QUERY PLAN                                                           
-------------------------------------------------------------------------------------------
 Index Scan using link_idx on edges  (cost=0.00..4467.63 rows=1143 width=4) (actual time=110.302..51275.822 rows=43629 loops=1)
   Index Cond: (link = 1588)
 Total runtime: 51300.041 ms
(3 rows)

Я также увеличил свои общие буферы с 24 МБ до 512 МБ, но это не помогло. Поэтому мне интересно, почему мои запросы на исходящие и входящие ссылки демонстрируют такое асимметричное поведение? Что-то не так с моим выбором индексов? Или мне лучше создать третью таблицу, содержащую все входящие ссылки для узла с идентификатором x? Но это было бы довольно пустой тратой дискового пространства. Но так как я новичок в базах данных SQL, может быть, мне здесь чего-то не хватает?

Answer 1

Полагаю, это из-за «плотности» записей одного и того же ключа на диске. Я думаю, что записи с одинаковым идентификатором хранятся в плотном (то есть, несколько блоков), а записи с одинаковыми ссылками хранятся в разреженном (то есть, распределены на огромное количество блоков). Если вы вставили записи в порядке идентификатора, такая ситуация может возникнуть.

Предположим, что: 1. Есть 10000 записей, 2. они хранятся в следующем порядке: (id, link) = (1, 1), (1, 2), ..., (1, 100), (2, 1) ... и 3. В блоке может храниться 50 записей.

В приведенном выше предположении блок № 1 ~ № 3 состоит из записей (1, 1) ~ (1, 50), (1, 51) ~ (1, 100) и (2, 1) ~ (2 , 50) соответственно.

Когда вы SELECT * FROM edges WHERE id=1, только 2 блока (# 1, # 2) должны быть загружены и отсканированы. С другой стороны, SELECT * FROM edges WHERE link=1 требует 50 блоков (# 1, # 3, # 5, ...), хотя количество строк одинаково.

Answer 2

Если вам нужна хорошая производительность и вы можете обойтись без ограничений внешнего ключа (или использовать триггеры для их реализации вручную), попробуйте модули расширения intarray и intagg . Вместо таблицы ребер есть столбец outedges integer[] на таблице узлов. Это добавит около 140 МБ к таблице, так что все это, вероятно, все еще уместится в памяти. Для обратного поиска либо создайте индекс GIN в столбце outedges (для дополнительных 280 МБ), либо просто добавьте столбец inedges.

Postgresql имеет довольно высокие издержки на строки, поэтому таблица наивных ребер даст 1 ГБ места только для таблицы, + еще 1,5 для индексов. Учитывая размер вашего набора данных, у вас есть хорошие шансы иметь большую его часть в кеше, если вы используете целочисленные массивы для хранения отношений. Это сделает любые поиски невероятно быстрыми. Я вижу около 0,08 мс времени поиска, чтобы получить ребра в любом направлении для данного узла. Даже если вы не поместите все это в память, у вас все равно будет большая доля памяти и намного лучшая локальность кэша.

Answer 3

Я думаю habe правильно.

Вы можете проверить это с помощью cluster link_idx on edges; analyze edges после заполнения таблицы. Теперь второй запрос должен быть быстрым, а первый - медленным.

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

Если вы не будете запрашивать это все время и не хотите сохранять и резервировать эту вторую таблицу, то вы можете временно создать ее перед запросом:

create temporary table egdes_backwards
  as select link, id from edges order by link, id;
create index edges_backwards_link_idx on edges_backwards(link);

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

Answer 4

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

ВАКУУМНЫЙ АНАЛИЗ (или просто АНАЛИЗ) поможет, если у вас есть много удаленных строк и / или обновленных строк. Сначала запустите его и посмотрите, есть ли улучшения.

CLUSTER также может помочь. Основываясь на ваших примерах, я бы сказал, используя link_idx в качестве ключа кластера. Msgstr "КЛАСТЕРНЫЕ ребра ИСПОЛЬЗУЯ link_idx". Однако это может ухудшить производительность ваших запросов идентификаторов (ваши запросы идентификаторов могут быть быстрыми, поскольку они уже отсортированы на диске). Не забудьте запустить ANALYZE после CLUSTER.

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

Answer 5

Вы пытались сделать это на www.neo4j.org? Это почти тривиально в графической базе данных и должно дать вам производительность при использовании в мс-диапазоне.