Ускоряем работу с графами в 20000 раз

[kawena54]

просто скажите мне почему все рекомендуют использовать граф БД для соц сетей? в 99% задач , например найти пересечение друг друзей друга это пересечение SET'OV

[Spinifex]

Не знаю почему. :) Согласен, что к выбору нужно подходить вдумчиво и никому не подражать. У графовых БД часто очень выразительный и удобный синтаксис написания запросов. Вместо 8 строчек с джойнами вы можете получить 1 строчку как аналог. Но средства диагностики, администрирования по своему развитию уступают реляционным. Поэтому поступаем как всегда — анализируем требования, в том числе не функциональные. И выбираем то, что лучше всего подходит для нашего проекта.

[Hashbash]

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

WHERE g.node1 = sg.node2
AND not (g.node1 = ANY(sg.path)) -- тоже самое, но останавливаемся на первом вхождении
AND ((sg.depth = 1) 
     or (sg.depth > 2 and sg.node1 > g.node1)
    ) -- исключаем логические повторы
      -- актуально если 30 2 3 1003 и 30 3 2 1003 - одно и тоже
      -- оставляем только одну последовательность (30 2 3 1003)

[Spinifex]

Лайк! Полезное дополнение.

[grebenyukov]

Здравствуйте! Добавление виртуального графа создает аналог прямой связи между узлами одного и того же столбца. В оригинальном графе они связаны лишь через крайний узел и узлы соседнего столбца. Разве не так?

[RinNas]

Добрый день, а https://postgrespro.ru/docs/postgresql/14/datatype-bit пробовали?

[Spinifex]

Для матрицы смежности? Пробовали. Строго говоря подобного можно добиться оперируя битами в наборе числовых значений (если у вас не PostgreSQL). Вполне себе вариант. Но обвес кода нужно будет прилично так написать.

[mentin]

Для постгресса есть расширение pgRouting. Им конечно в основном географы пользуются, но работает на произвольных графах, и там есть алгоритм pgr_connectedComponents, вычисляющий связанность. Описанную в начале схему по-моему можно без изменений ему скормить. Интересно, насколько быстрее / медленнее.

[Spinifex]

Да, интересно… честно говоря как-то руки не дошли. Обязательно попробую.

[Parser104]

Вынос общего множителя всегда упрощает решение, главное правильно вынести!

© Конфуций

[Spinifex]

С выражением не поспоришь. Но вот Конфуций разве такое говорил? :)

[Parser104]

Нет)

[Caraul]

Для графовых БД есть такой https://tinkerpop.apache.org/gremlin.html - язык обхода графов. Для PostreSQL нету, а вот MS для новой CosmosDB реализовал. Про призводительность не знаю.

[Spinifex]

Да, Гремлин весьма распространен в графовых БД. Однако у лидера этого класса БД (Neo4j) есть свой язык — Cypher. Мне он показался еще более удобным…
Но с производительностью использование диалекта связывать смысла не имеет. Важно что у вас за движок выполняет запросы. Но вот читабельность кода будет ясно выше, поэтому такие диалекты и изобретают.

[Caraul]

Полюбопытствовал - Гремлин имеет вид FluentAPI, а вот Cypher больше похож на SQL. Есть даже старый транслятор от openCypher - https://github.com/opencypher/cypher-for-gremlin

[fransua]

Кажется что использование реляционной БД здесь дикий оверхед, притом что из всех возможностей используется только SQL и может быть транзакционность.

Для разряженных матриц связей можно использовать mkl, вроде бы если детерминант не 0, то граф связный.

[Spinifex]

Возможно. В случае с mkl как быть с транзакционностью?

[fransua]

А какие нужны транзакции, обновление графа? Читаем граф, обновляем, сохраняем. В БД или просто на диск. Если есть конкурирующие потоки, то в локе.

[mrbald]

Я бы попробовал на плюсах написать простой прототип (или на numpy, или на любом языке с массивами и векторизацией) и использовал как бенчмарк. Может оказаться, что никакой multi-tier и не понадобится. Человечество начинает забывать какими быстрыми могут быть программы без проводов и баз данных.

[charypopper]

Спасибо за статью.

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

На первом рисунке (я пронумеровал вершины), чтобы попасть в вершину 2 из 1 надо одно ребро пройти. А чтобы в 3 из 1 - надо пройти 2 ребра. На второй картинке у вас получается одинаковое расстояние - 2 ребра (через виртуальный узел).

P.S. Если ориентировать ребра ("от" виртуального и "к"), то можно свернуть так, как на рисунке и потом иметь возможность получить исходный граф (считать связью только "к"+"от" и "от"+"к")

[Spinifex]

Зависит от того направленный граф или нет. Я изначалько подразумевал направленный граф, но стрелочки загромождают схему. :) Поправлю схемы чуть позже... На суть это не сильно влияет.

[charypopper]

Только если все направления от чётных к нечётным или наоборот. Если смешанное, то не получится. В статье что Вы приводите как раз так на первом рисунке