Многие не знают, что некоторые сложные для написания и неэффективные для выполнения SQL-запросы можно легко выразить и эффективно выполнить в графовой базе данных. Это справедливо даже для тех, кто уже знает, что графовые алгоритмы являются наиболее эффективным, а иногда и единственным решением для сложных бизнес-задач, таких как кластеризация пользователей (с использованием Лувенского алгоритма), поиск инфлюенсеров - людей или компаний (алгоритмом PageRank) или прогнозирование поведения пользователей для персональных рекомендаций (алгоритмом label propagation).
В этой статье мы опишем SQL запрос с 24 JOIN в корпоративный knowledge graph и покажем, что задачу можно решить в графовой базе данных - и это будет понятней, более легко поддерживаться и эффективно выполняться. Пример взят из проблемы, описанной в сообществе: https://community.tigergraph.com/
Высокоуровневое описание бизнес-вопроса звучит следующим образом: найти Сущности, которые имеют по крайней мере три определенных Отношения с другими Сущностями, а связанные Сущности, в свою очередь, также должны иметь по крайней мере 3 других указанных Отношения. Более конкретно, проблема состоит в том, чтобы найти каждую отдельную сущность X такую, чтобы:
X имеет отношение типа R1 с сущностью A, которая имеет
отношение типа R1 к любому объекту, И
отношение типа R2 к любому объекту И
отношение типа R3 к любому объекту
И X имеет отношение типа R2 к сущности B, которая имеет
отношение типа R2 к любому объекту И
отношение типа R3 к любому объекту , И
отношение типа R4 к любому объекту
И X имеет отношение типа R3 к сущности C, которая имеет
отношение типа R3 к любому объекту , И
отношение типа R4 к любому объекту, И
отношение типа R5 к любому объекту
Каждое из 12 условий связывает одну сущность с другой. Все сущности хранятся в одной таблице, поэтому мы неоднократно возвращаемся к этой таблице. Кроме того, полная проблема имеет условия для значений атрибутов сущностей. Если мы предложим конкретный запрос, показывающий отдельные сущности, а не таблицы, то он может выглядеть следующим образом:
Этот запрос не настолько искусственен, как может показаться. Предположим, что сущности являются банковскими счетами, а отношения - это переводы с одного счета на другой. Такого рода древовидная схема может быть примером наслоения, метода, используемого при отмывании денег для сокрытия своей деятельности. Или это может быть отслеживанием Trickle-Down эффекта просачивания платежей, поступающих от сущности X - работодателя, фонда или государственного учреждения.
Этот контекст полезен для разработки и понимания SQL запроса, показаного ниже:
SELECT DISTINCT Entity.id
FROM Entity AS X
JOIN R1 AS R1_X ON Entity.id = R1_X.source
JOIN Entity AS A ON A.id = R1_X.target
JOIN R1 AS R1_A ON A.id = R1_A.source
JOIN R2 AS R2_A ON A.id = R2_A.source
JOIN R3 AS R3_A ON A.id = R3_A.source
JOIN Entity AS A1 ON R1_A.target = A1.id
JOIN Entity AS A2 ON R2_A.target = A2.id
JOIN Entity AS A3 ON R3_A.target = A3.id
JOIN R2 AS R2_X ON Entity.id = R2_X.source
JOIN Entity AS B ON B.id = R2_X.target
JOIN R2 AS R2_B ON B.id = R2_B.source
JOIN R3 AS R3_B ON B.id = R3_B.source
JOIN R4 AS R4_B ON B.id = R4_B.source
JOIN Entity AS B2 ON R2_B.target = B2.id
JOIN Entity AS B3 ON R3_B.target = B3.id
JOIN Entity AS B4 ON R4_B.target = B4.id
JOIN R3 AS R3_X ON Entity.id = R3_X.source
JOIN Entity AS C ON C.id = R3_X.target
JOIN R3 AS R3_C ON C.id = R3_C.source
JOIN R4 AS R4_C ON C.id = R4_C.source
JOIN R5 AS R5_C ON C.id = R5_C.source
JOIN Entity AS C3 ON R3_C.target = C3.id
JOIN Entity AS C4 ON R4_C.target = C4.id
JOIN Entity AS C5 ON R5_C.target = C5.id
WHERE
Entity.attr1 = val1 AND
Entity.attr2 = val2 AND
Entity.attr3 = val3 AND
A.attr1 = val4 AND
A.attr2 = val5 AND
A.attr3 = val6 AND
A1.attr1 = valA AND
A2.attr2 = valB AND
A3.attr3 = valC AND
B.attr1 = val7 AND
B.attr2 = val8 AND
B.attr3 = val9 AND
B2.attr1 = valA AND
B3.attr2 = valB AND
B4.attr3 = valC AND
C.attr1 = val10 AND
C.attr2 = val11 AND
C.attr3 = val12 AND
C3.attr1 = valA AND
C4.attr2 = valB AND
C5.attr3 = valCОбратите внимание, что в приведенном выше SQL-запросе к таблицам отношений содержится 12 JOIN'ов и еще 12 JOIN'ов (копий предыдущих) обратно к таблице Entity, а затем длинный набор условий для атрибутов различных сущностей.
Проблемы решения задачи с использованием SQL
Решение с 24 JOIN'нами в SQL сложно написать, понять и поддерживать. Фактически, у нас были значительные трудности с пониманием того, какая копия таблицы является какой, пока мы не сделали рисунок 2 с алиасами для каждой показанной таблицы. Также хорошо известно, что реляционным базам данных очень сложно выполнить несколько JOIN'ов в одном запросе. Такой запрос просто невозможен на больших таблицах.
Графовое решение со встроенным параллелизмом
Теперь мы покажем использование графовой базы данных со встроенным параллелизмом и графовым языком запросов, на примере TigerGraph и языком запросов GSQL, для простого и эффективного решения подобных проблем.
Сначала мы перерисуем схему и представим её в виде графа. На графе каждая Сущность становится вершиной, нарисованной кругом, а каждое Отношение становится ребром, нарисованным линией, соединяющей две Сущности. Ребра также могут иметь свойства, такие как время, местоположение или вес, но в данном примере рёбра не имеют свойств. Хотя схема выглядит по-другому, предлагаемое графовое решение - это просто другое представление реляционного решения.
Диаграмма схемы графа может выглядеть необычно, если вы не знакомы с графами. Схема говорит о том, что существует один тип Сущности, который имеет 3 атрибута (attr1, attr2 и attr3). Кроме того, существует пять типов Отношений — от R1 до R5 — каждое из которых соединяет Сущность с другой Сущностью с явным направлением.
Благодаря мощности и гибкости GSQL, существуют различные подходы к решению этой задачи. Ниже показан один из таких способов.
/* Начинаем со всех элементов */
Entities = {Entity.*};
/* Вычисляем сущности A, подходящие по условиям атрибутов и нисходящим отношениям.
Сначала отношения R1, потом сужаем выборку до тех, где есть отношения R2 и R3 */
A = select m from Entities:m-(R1)-:t
where m.attr1 == val4 and m.attr2 == val5 and m.attr3 == val6
and t.attr1 == valA;
A = select m from A:m-(R2)-:t where t.attr2 == valB;
A = select m from A:m-(R3)-:t where t.attr3 == valC;
/* Вычисляем сущности B, подходящие по условиям атрибутов и нисходящим отношениям.
Сначала отношения R1, потом сужаем выборку до тех, где есть отношения R2 и R3 */
B = select m from Entities:m-(R2)-:t
where m.attr1 == val7 and m.attr2 == val8 and m.attr3 == val9
and t.attr1 == valA;
B = select m from B:m-(R3)-:t where t.attr2 == valB;
B = select m from B:m-(R4)-:t where t.attr3 == valC;
/* Вычисляем сущности C, подходящие по условиям атрибутов и нисходящим отношениям.
Сначала отношения R1, потом сужаем выборку до тех, где есть отношения R2 и R3 */
C = select m from Entities:m-(R3)-:t
where m.attr1 == val10 and m.attr2 == val11 and m.attr3 == val12
and t.attr1 == valA;
C = select m from C:m-(R4)-:t where t.attr2 == valB;
C = select m from C:m-(R5)-:t where t.attr3 == valC;
/* Вычисляем сущности X, подходящие по условиям атрибутов и нисходящим отношениям с A, B и C.
Сначала делаем выборку по атрибутам и связям R1, потом делаем выборки X где есть отношения R2 и R3 */
X1 = select t from A:s-(R1)-:t
where t.attr1 == val1 and t.attr2 == val2 and t.attr3 == val3;
X2 = select t from B:s-(R2)-:t;
X3 = select t from C:s-(R3)-:t;
/* Для конечного результата - делаем пересечение выборок X */
Result = X1 intersect X2 intersect X3;
print Result;Преимущества графового решения
Очевидно, что графовое решение намного проще в написании, чтении, понимании и сопровождении, чем один огромный SQL-запрос с 24 JOIN'нами. Графовое решение легко расширяется: позволяет выйти за рамки текущей "двухуровневой" проверки отношений без потери производительности и удобочитаемости.
Дальнейшее изучение
Один из лучших способов начать работу с графовой аналитикой - использовать TigerGraph Cloud. Это бесплатно, и можно создать учетную запись за несколько минут. Регистрируйтесь здесь.
Можно скачать сравнение производительности различных графовых баз данных: TigerGraph и Neo4j или TigerGraph и Amazon Neptune.
Вы также можете узнать больше о TigerGraph, присоединившись к нашему сообществу: https://community.tigergraph.com/.
Если хочется пообщаться на русском - пишите на TigerGraph@fgts.ru.
Мы с нетерпением ждем ваших экспериментов.
Комментарии (29)
derikn_mike
24.08.2021 14:05-3в 2021 всё на клиенте джойнится , проблем нету.
Тоесть GetVideos
Сразу показываем видео
Сразу ПОДгружаем GetLikesCount допустим
tempick
24.08.2021 14:48Не понял. То есть, вместо джойна отправляется ещё один запрос на сервер и ещё один запрос на сервере к бд для получения количества лайков?
popov-as Автор
24.08.2021 15:07+1Для небольших данных - согласен.
Но когда у вас 100M+ вершин и 10B+ связей - тут клиент боюсь не справится...
PrinceKorwin
24.08.2021 14:24Слишком маркетинговая статья. Перешел на сайт. Там там чтобы добраться до документации (не how to, не hello world) - это нужно изрядно постараться. Всё, что попадается - это только "купите нас полностью".
Жаль. Мне симпотичны графовые БД (neo4j, OrientDB, Titan, и т.д.). Но вот сходу понять какие ключевые фичи есть у TigerGraph - сложно. Как я понял ключевое - это набор готовых функций анализа графа + возможность писать свои.
Не очень понятно что с ACID транзакциями (как я понял они ACID только локально / in-memory).
Как именно реализован распределенный граф (partitioning, sharding, ...) и какие имеются ограничения - так же не нашел.
popov-as Автор
24.08.2021 15:44+1Статья скорее для замученного
нарзаномАналитика, а не Администратора...Документация: https://docs.tigergraph.com/ (в разделе Resourses на сайте)
До 50 GB (~150GB сырых данных) - free edition
Основные Advantages перечислены на этой странице:
написана на С++ с нуля (в продакшене с 2012, публична с 2017),
DeepLink аналитика (10+ хопов) - особеннно важен,
MPP распределённая база,
быстрая загрузка больших датасетов, они сжаты и занимают меньше места в ОП,
ACID(OLTP)+OLAP = HTAP,
In-Database аналитика, тьюринг полный язык GSQL, который наиболее близок к грядущему GQL стандарту
GUI для моделирования и No-Code
Не только Batch, но и Real-Time аналитика на больших датасетах
Про ACID:
The TigerGraph system also provides distributed system Sequential Consistency: every replica of the data performs the same operations in the same order. This is one of the strongest forms of consistency available, stronger than causal consistency, for example.
GSQL - есть готове к работе графовые алгоритмы, а также решения конкретных бизнес-задач. Алгоритмы открыты, их можно модифицировать и использовать как примеря для своих задач = например захочется чуть поправить PageRank.
Анализ связей на распределённом графе - одно из ключевых преимуществ. В отличие от Neo4j тут не надо сводить связанные данные в одну ноду: они могут быть реально распределены.
Как это сделано - тут лучшее посмотреть про архитектуру - коротко тут и видео "TigerGraph Architecture overview" - Why TigerGraph is 100x faster than the competition and provides the lowest cost of ownership
PrinceKorwin
24.08.2021 16:32Спасибо за такой развернутый ответ. Он полезнее чем сама статья :)
К сожалению ограничение по транзакциям достаточно существенные:
Transactions are defined as follows:
Each GSQL query is a transaction. Each query may have multiple read or write operations.
Если я правильно понимаю. То не получится сделать: BEGIN -> GSQL -> business logic -> GSQL -> COMMIT
И это существенно ограничивает область применения подобных транзакций.
Внутренний механизм согласованности строится поверх Zookeeper + Kafka.
Сама БД заточена под massive-read операции. Т.к. запись во все реплики синхронная. Само по себе это не плохо и не хорошо.
Просто такие вещи по хорошему должны быть где-то на первых страницах. Чтобы понимать область применимости этой БД :)
popov-as Автор
24.08.2021 17:34Тут скорее идея в том, что бизнес-логику можно реализовать с помощью GSQL. Поскольку это полноценный язык программирования, мы можем сделать циклы, ветвления и т.д.:
REST Request --> GSQL + business logic --> JSON Result
Massive-write - это тоже случай для этой БД. Например кейсы с CyberSec аналитикой, когда у нас большой стрим данных.
PrinceKorwin
24.08.2021 17:52Тут скорее идея в том, что бизнес-логику можно реализовать с помощью GSQL.
Это красиво только на бумаге. В реальности в этой бизнес-логике нужно обращаться к данным и функциям которые локальны с точки зрения клиента этой БД. И это не говоря про различные интеграции.
Представьте, что в Oracle/PostgreSQL есть только их pl/[pg]sql и транзакция только на их единичный вызов. Многое можете сделать? Что-то можно, но это ограничение очень сильное и с ним нужно считаться.
Massive-write - это тоже случай для этой БД.
Да, только вот физику никто не отменял. И для этих целей они вынужденно отключают синхронную репликацию и их преимущество master-less нивелируется.
Это не говорит против БД. Всё таки это принципиальные ограничения. Но вот об этом они нигде не говорят явно.
Вопрос: а о чём они ещё умалчивают? :)
popov-as Автор
24.08.2021 18:31По бизнес логике - конечно если несколько БД, тут некуда деваться и транзакцию нужно делать уровнем выше, на уровне приложения.
По запросам - тут сложнее, мастер есть в рамках GSQL запроса. Реплика фактор 2 или другой позволяет обеспечить сохранность данных.
Эти вопросы хорошо будет осветить в отдельной статье, спасибо!
Kubera2017
22.09.2021 00:00In-Database аналитика, тьюринг полный язык GSQL, который наиболее близок к грядущему GQL стандарту
вот это реально сомнительно
popov-as Автор
25.11.2021 15:37А что именно сомнительно? мы успешно пишем алгоритмы, которые работают внутри БД, без внешних библиотек и костылей.
Kubera2017
25.11.2021 15:52Я не уверен насчет этой фразы "язык, который наиболее близок к грядущему GQL стандарту" Уж скорее он будет ближе к Cypher, все таки 95% community это юзеры Neo4j и 5% это Gremlin. Хотя это не точно, Tigergraph'у больше всех надо.
Kubera2017
25.11.2021 15:54Про алгоритмы, да нормально, в некоторых вещах даже больше чем на гремлине можно сделать
Kubera2017
21.09.2021 23:53Ключевое отличие TigerGraph от остальных графовых бд это MPP и ACID одновременно, т.е. она HTAP бд (новое поколение). Шардинг реализован как node-based (есть два основных вида - predicate-based когда мы шардируем грани, и node-based когда мы шардируем вершины с исходящими гранями). Проблема node-based шардинга в supernode problem (когда очень много граней у вершины). Документация, да у них та еще, очень тяжело разобраться, видимо какой то особый образ мышления у китайцев. Это притом что я отлично знаю cypher и gremlin и знаю примерно каким должен быть запрос. Клиентам они говорят, купите лицензию, потом мы вам дадим наших инженеров и они все настроят и объяснят.
popov-as Автор
25.11.2021 15:55Ключевое отличие TigerGraph от остальных графовых бд это MPP и ACID одновременно, т.е. она HTAP бд (новое поколение).
Согласен
Шардинг реализован как node-based (есть два основных вида - predicate-based когда мы шардируем грани, и node-based когда мы шардируем вершины с исходящими гранями). Проблема node-based шардинга в supernode problem (когда очень много граней у вершины).
На видео ниже можно посмотреть детали архитектуры и Native Graph Storage - вершины и рёбра распределяются по сегментам и хранятся на одной партиции:
Документация, да у них та еще, очень тяжело разобраться, видимо какой то особый образ мышления у китайцев. Это притом что я отлично знаю cypher и gremlin и знаю примерно каким должен быть запрос. Клиентам они говорят, купите лицензию, потом мы вам дадим наших инженеров и они все настроят и объяснят.
Видел много документаций, у TG вполне подробная и понятная документация, от сохи https://docs.tigergraph.com/. Можно найти довольно подбробную информацию - по Языку, алгоритмам и администрированию самой БД.
PavelVelikhov
24.08.2021 16:47А что побудило переводить статью о TigerGraph? Вы пользуетесь этой СУБД, или собираетесь ее ставить?
popov-as Автор
24.08.2021 17:43+1Если коротко - пользуемся сами, ставим и поддерживаем.
Изначально были задачи на графой аналитике, посмотрели что есть с точки зрения масштабирования/скорости, удобства и текущих заказчиков (=продакшен), остановились на этой БД.
Также подкупило наличие ready-to-go решений - с набором данных и готовыми алгоритмами = просто добавь свои данные.
PrinceKorwin
24.08.2021 17:59Вам хватает ограничений бесплатной версии (50Gb данных в скомпрессированном виде ) или вы перешли на платную версию?
Если на платную, то что можете сказать об их уровне поддержки и скорости реагирования? Какие были к ним запросы?
Также подкупило наличие ready-to-go решений
Да. Это очень хорошее подспорье. Тут без вариантов.
Можете рассказать про:
Вы данные храните вместе со связями в этой БД?
Или данные отдельно, а эту БД только под граф-связи? (например именно так рекомендуют использовать neo4j)
Каков объем данных в Gb и какая топология деплоймента (партиции, реплики и т.д.)?
Сколько Vertex и сколько Edge?
Это реально интересно. Т.к. мои попытки залезть со своими сценариями на Neo4j и OrientDB привели к тому, что нео отпал, а OritentDB хоть и интересен с точки зрения архитектуры решения, но по производительности совершенно не устраивает. Да и наличие достаточно большого кол-ва багов которые годами не фиксятся удручает.
popov-as Автор
25.08.2021 10:51Наш кейс умещается в 50GB сжатых данных. В нашем случае - данные и связи - это одно и то же, поэтому храним всё в одной БД. Тут наверно индивидуально всё, в целом подход: если данные нужны для анализа, подпадают под определеения вершины или ребра, тогда их используем.
С вендором общались и общаемся, в т.ч. по другим кейсам. Общаемся как по линии community, так и с инженерми напрямую. Уровнем и скоростью довольны, в TigerGraph пришли люди с большим опытом работы в других коммерческих БД, а таже практики из прикладных доменов.
Если Вы пробовали Neo4j или другие, тогда Вам точно стоит попробовать эту БД. С точки зрения производительности на графах - они как раз лидеры, остальные фоловеры (раз и два). С точки зрения стбильности - в продакшенах разных не первый год, у нас тоже стабильно.
Из примеров масштабирования - недавно был пример задачи AML для Blockchain от Merkle Science:
Merkle Science’s cryptocurrency network graph, which currently contains over 2.5 TB of data and consists of 5 billion vertices and 36 billion edges, supports a complete extract, transfer and load (ETL) each day that takes under an hour, with near-instant streaming updates. “We reached out to TigerGraph as we’ve been trying to find an elegant way to visualize our investigative data over the last two years. Other incumbents in the graph database space weren’t able to process our vast amounts of data fast enough in order to generate graphs in real time. TigerGraph helped solve that issue for us
Видео работы - особенно интересно с 6 минуты https://www.youtube.com/watch?v=_5Z6c8G-AFk
asmm
25.08.2021 12:56Проблема тут не в SQL, а в EAV, т.е. неверно подобранном паттерне при проектировании схемы БД.
popov-as Автор
25.08.2021 14:49Тут как раз графовая схема является альтернативой EAV (Рисунок 3), что может быть проще.
asmm
25.08.2021 15:35не надо сравнивать с EAV, спроектируйте нормальную структуру и сравните с ней, читаемость кода, быстродействие, консистентность
popov-as Автор
25.08.2021 17:10Тут конечно нужно исходить от задачи, можно и генератор JOIN'ов написать. В целом - не очень удобно запускать класс графовых алгоритмов поверх таблиц.
uaggster
18.09.2021 20:14Очевидно, что графовое решение намного проще в написании, чтении, понимании и сопровождении, чем один огромный SQL-запрос с 24 JOIN'нами. Графовое решение легко расширяется: позволяет выйти за рамки текущей "двухуровневой" проверки отношений без потери производительности и удобочитаемости.
Вот, кстати, совершенно неочевидно.
SQL запрос, хоть он и с 24 джойнами - абсолютно линеен, предсказуем, прекрасно читается и понимается. Вариант с графом - какая то мешанина из слабосвязанных кусков, чтобы понять которую нужно держать в мозгу одновременно кучу кусков кода.
Про энтити-атрибут-вэлью, как антипаттерн создания реляционных БД уже сказали.
Кстати, тем кто хочет попробовать графы в привычной среде советую установить MSSQLSERVER 2019, можно даже express. Их там есть.
popov-as Автор
21.09.2021 13:17У каждого свои задачи, если начинаешь запускать графовые алгоритмы или нужно проанализировать связи с глубиной 6 или 10 - можно выбрать любой инструмент, но на каком-то этапе упереться в стену: по производительности, по масштабированию, по удобству работы и т.д.
Помимо синтаксического сахара в запросах, важно чтобы хранение данных было изначально графовое. Насколько могу судить по статье https://habr.com/ru/company/otus/blog/518586/ про MSSQLSERVER - получается монструозный "графовый" запрос и скорость работы на больших данных ожидаемо просядет (ибо JSON в таблицах).
Nnnnoooo
Обычная бесполезная маркетинговая статья.
Нет ничего ни о производительности и удобстве работы с реальными данными в реальных условиях (миграция текущего приложения на эту базу, задержки и скорость под нагрузкой и т.д.)
popov-as Автор
Статья является переводом и немного про другое - про аналитику. Что мне понравилось - наглядно показана разница между схемами реляционной БД и Графовой. Попробуйте сравнить Рисунок 1 и Рисунок 3, когда планируем схему - тут многие мыслят "традиционно" таблично.
В конце ссылки на сравнения по производительности. Более свежие сравнения:
https://www.tigergraph.com/benchmark/
https://www.tigergraph.com/blog/truth-behind-neo4js-trillion-relationship-graph/
Что касается миграции - есть готовые для MySQL и PG. Но если мы говорим про BigData - то TigerGraph часто используется поверх существующих хранилок (aka Spark) и реализует графовую аналитику на скоростях.
Nnnnoooo
Ну по статье это как раз и не понятно.
Просто обычная рекламная статья без каких-либо деталей