В первой части я собрал данные из социальной сети вконтакте по друзьям друзей друзей 9 пользователей из разных возрастных категорий, с которыми мне довелось пересечься в жизни. Я организовал хранение самих пользователей, а также их связей с другими пользователями в реляционной БД. Для этого я использовал postgres.

Схема БД:

Поля в таблице friends ссылаются на vk_id поле таблицы users.

Изначально я хотел проверить теорию 6-ти рукопожатий для этих девяти человек, а также расширить свой навык использования рекурсивных запросов.

Собирая данные для базы, и друзей 3-го уровня, у меня получилось порядка полумилиона пользователей. В результате мне удалось показать, что для моей выборке достаточно даже пяти рукопожатий. В этой статье я хочу доработать полученный результат и попробовать реализовать построение кратчайших цепочек-связей между двумя пользователями.

Ищу кратчайшие пути

В прошлой статье я показал запрос, который позволял построить все возможные цепочки между двумя пользователями. Главная его проблема заключалась в том, что с ростом уровня, дерево отношений сильно разрасталось и для 5 уровней составляло порядка 56 млн записей. А время на выполнение запроса составляло порядка 5 минут на запрос.

Так что, в этой статье я продумал альтернативный способ построения цепочек, чтобы минимизировать количество неподходящих вариантов.

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

Ключевым запросом у меня выступил следующий скрипт, который осуществлял поиск пересечения друзей (до 3-го уровня) пользователей 123 и 567:

WITH RECURSIVE levels(d1, d2) AS (
  -- список комбинаций соединения уровней
  VALUES (1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)
), level_from(id, depth) AS (
  -- первые 3 уровня друзей первого пользователя
  SELECT 123, 123 as id, 0 as depth
  UNION ALL
  SELECT DISTINCT
    start_id,
    CASE WHEN  l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
    l.depth + 1 as depth
  FROM level_from l
    JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < 3
), level_to(id, depth) AS (
  -- первые 3 уровня друзей второго пользователя
  SELECT 567, 567 as id, 0 as depth
  UNION ALL
  SELECT DISTINCT
    end_id,
    CASE WHEN  l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
    l.depth + 1 as depth
  FROM level_to l
    JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < 3
)
-- выбираем первого пользователя, являющегося центром в цепочке
SELECT start_id,  d1, l1.id, d2, end_id
FROM levels l
    JOIN level_from l1 ON l1.depth = l.d1
    JOIN level_to l2 ON l2.depth = l.d2 and l1.id = l2.id
ORDER BY d1 + d2
LIMIT 1

В результате получился такой ответ:

id 1-го пользователя Расстояние до центра id центрального пользователя в цепи Расстояние до 2-го пользователя id 2-го пользователя
123 1 999 2 567

Расстояние 1 - означает, что пользователь является непосредственным другом 1-го пользователя.

Расстояние 2 - означает, что центральный пользователь является другом друга 2-го пользователя.

Так как максимально возможное расстояние у меня в 3 уровня, то можно перебрать все цепочки. А из них уже выбрать любую.

Для этого я доработал скрипт из предыдущей статьи, который выдавал все цепочки для заданного пользователя:

WITH RECURSIVE chains(id, chain, depth) AS (
  -- строим левые цепочки
  SELECT
    123,
    123 :: TEXT AS chain,
    0 AS depth

  UNION

  SELECT
    CASE WHEN l.id = f.user2_id
      THEN user1_id
    ELSE user2_id END                      AS id,
    l.chain || ' -> ' || CASE WHEN l.id = f.user2_id
      THEN user1_id ELSE user2_id END AS chain,
    l.depth + 1                            AS depth
  FROM friends f
    JOIN left_chains l ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < 3
)
SELECT *
FROM chains

Порождаем чудовище

Немного доработаем его, чтоб он хватал цепочки, и получим такого монстра:

WITH RECURSIVE
users (from_user, to_user) AS (
   SELECT 123, 567
),

levels(d1, d2) AS (
  VALUES (1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)
),

level_from(id, depth) AS (
  SELECT
    (SELECT from_user FROM users) as id,
    0 as depth

  UNION ALL

  SELECT DISTINCT
    CASE WHEN  l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
    l.depth + 1 as depth
  FROM level_from l
    JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < 3
),

level_to(id, depth) AS (
  SELECT
    (SELECT to_user FROM users) as id,
    0 as depth

  UNION ALL

  SELECT DISTINCT
    CASE WHEN  l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
    l.depth + 1 as depth
  FROM level_to l
    JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < 3
),

center_info AS (
  SELECT
    (SELECT from_user FROM users) as start_id,
    d1,
    l1.id as center_id,
    d2,
    (SELECT to_user FROM users) as end_id
  FROM levels l
    JOIN level_from l1 ON l1.depth = l.d1
    JOIN level_to l2 ON l2.depth = l.d2 and l1.id = l2.id
  ORDER BY d1 + d2
  LIMIT 1
),

left_chains(id, chain, depth, max_depth, center_id) AS (
  -- строим левые цепочки
  SELECT
    ci.start_id,
    ci.start_id::text as chain,
    0 as depth, -- уровень дерева
    ci.d1 as max_depth,
    ci.center_id as center_id
  FROM center_info ci

  UNION

  SELECT
    CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END  AS id,
    l.chain ||  ' -> ' ||  CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END as chain,
    l.depth + 1 as depth, -- изменение уровня дерева
    l.max_depth,
    l.center_id
  FROM friends f
  JOIN left_chains l ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < l.max_depth - 1 or (l.depth = l.max_depth - 1 and
      CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END = l.center_id
  )
),

right_chains(id, chain, depth, max_depth, end_id) AS (
  -- строим правые цепочки
    SELECT
      ci.center_id,
      '' as chain,
      0 as depth, -- уровень дерева
      ci.d2 as max_depth,
      ci.end_id as end_id
    FROM center_info ci

  UNION

  SELECT
    CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END  AS id,
    l.chain ||  CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END ||
    CASE WHEN l.depth < l.max_depth - 1 THEN ' -> ' ELSE '' END  as chain,
    l.depth + 1 as depth, -- изменение уровня дерева
    l.max_depth,
    l.end_id
  FROM friends f
    JOIN right_chains l ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < l.max_depth - 1 or (l.depth = l.max_depth - 1 and
      CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END = l.end_id
  )
)
SELECT l.chain || ' -> ' || r.chain
FROM left_chains l, right_chains r
WHERE l.depth = l.max_depth and r.depth = r.max_depth

Разъяснение

Хоть скрипт внешне и выглядит страшно, на самом деле не так ужасен. Давайте разберем его по частям. Всего у нас 7 CTE подзапросов и один основной, который объединяет последние два CTE запроса. Что же тут происходит? Поехали:

1. Первый нужен, чтоб не вводить список пользователей по несколько раз, просто фиксируем во временную таблицу с одной записью и двумя столбцами:

users (from_user, to_user) AS (
   SELECT 123, 567
)

2. Это список возможных комбинаций расстояний (в уровнях) между крайними элементами цепочек (то есть пользователями, которых мы хотим соединить) и центральным связывающим пользователем. Это не значит, что все комбинации понадобятся, но значит, что мы рассматриваем только такие:

levels(d1, d2) AS (
  VALUES (1,1), (1,2), (2,1), (2,2), (2,3), (3,2), (3,3)
)

3. Формирует три уровня друзей (то есть друзья, друзья-друзей, друзья-друзей-друзей) для пользователя, от которого мы начинаем строить цепочку:

level_from(id, depth) AS (
  SELECT -- начальная итерация
    (SELECT from_user FROM users) as id,
    0 as depth

  UNION ALL

  SELECT DISTINCT -- наращиваем уровни
    CASE WHEN  l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
    l.depth + 1 as depth
  FROM level_from l
    JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < 3
)

Графически это выглядит так:

4. По аналогии с запросом выше, формируем три уровня друзей для пользователя, до которого мы пытаемся построить цепочку:

level_to(id, depth) AS (
  SELECT
    (SELECT to_user FROM users) as id,
    0 as depth

  UNION ALL

  SELECT DISTINCT
    CASE WHEN  l.id = f.user2_id THEN user1_id ELSE user2_id END AS id,
    l.depth + 1 as depth
  FROM level_to l
    JOIN friends f ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < 3
)

Выглядит вот так (но тут, для разннобразия, показываю только два уровня):

5. Находим самую короткую комбинацию уровней, на которой происходит пересечение друзей левого и правого пользователя соответственно:

center_info AS (
  SELECT
    (SELECT from_user FROM users) as start_id, -- левый пользователь
    d1, -- растояние до точки наложения
    l1.id as center_id, -- центральный пользователь
    d2, -- прстояние до правого пользователя
    (SELECT to_user FROM users) as end_id -- правый пользователь
  FROM levels l -- выбираем из комбинаций расстояний
    JOIN level_from l1 ON l1.depth = l.d1 -- подклеиваем с комбинациями существующие уровни левого пользователя
    JOIN level_to l2 ON l2.depth = l.d2 and l1.id = l2.id -- подклеиваем существующие уровни второго пользователя, в местах, где идет наложение на уровни левого пользователя
  ORDER BY d1 + d2 -- упорядочиваем по кратчайшему пути
  LIMIT 1 -- берем только первый (самый короткий) путь
)

Грубо говоря, тут рассчитываются различные комбинации пересечения множеств друзей. И выбирается та, которая позволит построить кратчайший путь от пользователя до пользователя.

На схеме цветом выделены общие друзья. Для первого пользователя они впервые встречаются на третьем уровне. Для второго - на втором уровне. В целях оптимизации, я выбирают только одного пользователя из списка (помечен красным):

6. Строим все возможные цепочки от левого пользователя до центрального, с длиной равной той, что была указана в center_info:

left_chains(id, chain, depth, max_depth, center_id) AS (
  SELECT
    ci.start_id,
    ci.start_id::text as chain,
    0 as depth, -- уровень дерева
    ci.d1 as max_depth, -- ограничение на размер дерева
    ci.center_id as center_id -- правый пользователь в подцепи
  FROM center_info ci

  UNION

  SELECT
    CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END  AS id,
    l.chain ||  ' -> ' ||  CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END as chain,
    l.depth + 1 as depth, -- изменение уровня дерева
    l.max_depth,
    l.center_id
  FROM friends f
  JOIN left_chains l ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < l.max_depth - 1 or (l.depth = l.max_depth - 1 and
      CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END = l.center_id
  )
)

Тут, думаю, все и без комментариев ясно:

7. Строим все возможные цепочки от центрального пользователя до правого, с длиной равной той, что была указана в center_info:

right_chains(id, chain, depth, max_depth, end_id) AS (
    SELECT
      ci.center_id,
      '' as chain,
      0 as depth, -- уровень дерева
      ci.d2 as max_depth,
      ci.end_id as end_id
    FROM center_info ci

  UNION

 -- тут небольшое отличие в формировании строки цепи, чтобы не появлялся двойной знак ->
  SELECT
    CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END  AS id,
    l.chain ||  CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END ||
    CASE WHEN l.depth < l.max_depth - 1 THEN ' -> ' ELSE '' END  as chain,
    l.depth + 1 as depth, -- изменение уровня дерева
    l.max_depth,
    l.end_id
  FROM friends f
    JOIN right_chains l ON l.id = f.user1_id OR l.id = f.user2_id
  WHERE l.depth < l.max_depth - 1 or (l.depth = l.max_depth - 1 and
      CASE WHEN l.id = f.user2_id THEN user1_id ELSE user2_id END = l.end_id
  )
)

Аналогично предыдущему пункту:

8. Основной запрос, просто склеивает две таблицы, выдающие цепочки, чтобы получить все возможные комбинации цепочек:

SELECT l.chain || ' -> ' || r.chain
FROM left_chains l, right_chains r
-- тут фильтруем по максимальной указанной длине цепи, потому что промежуточные цепочки нас не интересуют
WHERE l.depth = l.max_depth and r.depth = r.max_depth

Заключение

Как видно, рекурсивные запросы дают достаточно мощный инструмент для работы с графами. Для моего примера скорость нахождения цепочки составила порядка 4 секунд для полумиллиона ползователей на моем четырехядерном ноутбуке с SSD. Хороший ли это результат? Ну для работы в райнтайме, наверное, нет. Для разового запуска или для работы в бэкграунде - вполне приличный. Можно ли его улучшить? Полагаю, что можно.

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

Более того, я собрал достаточно внушительный набор данных для дальнейшего анализа. Который в ближайшее время, я планирую более глубоко проанализировать. Возможно, попробовать найти "ключевых" пользователей, за счет которых и обеспечивается покрытие рукопожатиями. Но пока на этом все.