Эксперимент проверки применимости графовой СУБД JanusGraph для решения задачи поиска подходящих путей

[glorfindeil]

aimultiple.com/process-mining-software

[nitrosbase]

На Stack Overflow спросить не пробовали? Возможно, лучше писать что-нибудь типа out("hasNextVisit") вместо просто out().

[ivankudryavtsev]

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

К сожалению, на StackOverflow я не спрашивал, не приучен — читал доки. Когда я думаю, что инженеры при разработке должны будут ходить на SO и спрашивать о вопросах оптимизации, мне сразу не хочется с этим связываться.

[lnuynxa]

Кликхаус конечно не тормозит, но почему было решено сделать подобные запросы через INNER JOIN(N^2), вместо GROUP BY user и дальше через массивы и лямбдами(arrayMap,arrayFilter,arrayReduce), либо через то подмножество оконных функций в кликхаусе, что уже есть. Это было бы в тысячи раз быстрее на больших датасетах.

[ivankudryavtsev]

Решил быстрое сравнение провести:

SELECT COUNT(*)
FROM
(
SELECT
s3.person,
s1z,
s1w,
s2z,
s2w,
s3.zone,
s3.when
FROM
(
SELECT
s1.person AS person,
s1.zone AS s1z,
s1.when AS s1w,
s2.zone AS s2z,
s2.when AS s2w
FROM
(
SELECT *
FROM steps
WHERE (area = 0) AND (zone = 0)
) AS s1
ANY INNER JOIN
(
SELECT *
FROM steps AS s2
WHERE (area = 0) AND (zone = 3)
) AS s2 USING (person)
WHERE s1.when <= s2.when
) AS p
ANY INNER JOIN
(
SELECT *
FROM steps
WHERE (area = 0) AND (zone = 19)
) AS s3 USING (person)
WHERE p.s2w <= s3.when
)

┌─COUNT()─┐
│ 11689 │
└─────────┘

1 rows in set. Elapsed: 0.062 sec. Processed 232.55 thousand rows, 7.42 MB (3.78 million rows/s., 120.43 MB/s.)



Оконная функция (результаты различаются из-за приведения DateTime64 к DateTime, как я полагаю, запрос должен быть верным, проверьте, если не так):

SELECT count(*)
FROM
(
SELECT
person,
sequenceCount('(?1).*(?2).*(?3)')(toDateTime(when), zone = 0, zone = 3, zone = 19) AS c
FROM steps
WHERE area = 0
GROUP BY person
)
WHERE c > 0

┌─count()─┐
│ 4893 │
└─────────┘

1 rows in set. Elapsed: 0.099 sec. Processed 435.85 thousand rows, 13.95 MB (4.39 million rows/s., 140.44 MB/s.)


Сколько ни запускаю, JOIN работает быстрее.

[lnuynxa]

SELECT count(*)
FROM
(
SELECT
person,
sequenceCount('(?1).*(?2).*(?3)')(toDateTime(when), zone = 0, zone = 3, zone = 19) AS c
FROM steps
WHERE area = 0 and zone IN (0,3,19) --ну если мы отсекаем ненужные зоны в запросе с join то можем и тут их не сканировать.
GROUP BY person
)
WHERE c > 0

В чем проблема клика с JOIN?
В том, что тк в клихаусе индекс разряженный, кликхаус использует merge джоин и ему приходится поднимать правую таблицу в оперативную память и сортировать ее, что обязательно выстрелит в ногу, когда у тебя в правой таблице окажется сотни миллионов — миллиарды записей. Поэтому в кликхаусе желательно избегать JOIN, на небольших правых таблицах можно обходится словарями.

[ivankudryavtsev]

Спасибо, ценно)

[ivankudryavtsev]

Спасибо за совет. Я этот инструментарий еще не использовал на практике — так что это просто за областью моих знаний. Коллегам обязательно посоветую посмотреть, возможно, что они про это не знают тоже.

[Kubera2017]

Я думаю это ошибочная модель графа, переходы между зонами должны быть представлены гранями т.к. это действия, а не объекты. На грани я бы предложил хранить trackId цепочки и построить vertex-centric индекс (zoneId, trackId)

[Kubera2017]

Я думаю это ошибочная модель графа, переходы между зонами должны быть представлены гранями т.к. это действия, а не объекты. На грани я бы предложил хранить trackId цепочки и построить vertex-centric индекс (zoneId, trackId)

[nkretov]

https://nebula-graph.io/posts/performance-comparison-neo4j-janusgraph-nebula-graph/ — кстати нашел перформанс компарисон между основными движками графовых бд. как по мне хьюдж граф ведет себя очень достойно.