MySQL · MySQL 8.4.6
Граф Facebook лежит в MySQL как объекты и ассоциации TAO: строка (id1, atype, id2, created) — связь типа atype от id1 к id2. Дружба хранится в обе стороны: если есть (5, friend, 9), есть и (9, friend, 5).
Для каждого пользователя предложите до двух возможных друзей: людей на расстоянии двух шагов по friend. Не предлагать самого себя, тех, кто уже в друзьях, и тех, кого пользователь заблокировал (atype = blocked, от пользователя к кандидату).
Порядок кандидатов — по mutual (число общих друзей) по убыванию, при равенстве — меньший suggested_id. Верните user_id, suggested_id, mutual; ровно две строки, если кандидатов два и больше.
В работе: Блок «Люди, которых вы можете знать» и офлайн-расчёт кандидатов на рекомендацию.
Источник: кейс Meta: граф Facebook в MySQL через TAO, USENIX ATC 2013. Условие пересказано своими словами.
Какие запросы вернут по два возможных друга на пользователя?
- Кандидаты в CTE, ROW_NUMBER() ≤ 2
- RANK() OVER (ORDER BY mutual DESC) ≤ 2
- Без окна: кандидатов выше текущего меньше двух
- Без исключения самого себя
- Без исключения уже добавленных друзей