L10. Граф проти рекурсивного CTE

середнійспирається на модуль 18

Мета

Розв’язати одну й ту саму графову задачу двома способами і побачити, де різниця справжня, а де її робить відсутній індекс чи невдале формулювання. Після роботи ви вмієте писати на customer_friends запити, що не зациклюються в графі з циклами, відрізняєте друзів друзів від друзів і себе самого, рахуєте різних людей, а не шляхи, і знаєте, що у Cypher одне ребро не проходять двічі в межах шаблону.

Завдання

Результат: чотири файли в labs/l10-graph/solution/. Заготовки з повним описом результату лежать у starter/.

Файл	Параметри	Що повертає
`recommend.cypher`	`$customer_id`	друзі друзів покупця: до 10 рядків `candidate_id`, `mutual_friends`, `shared_categories`
`recommend.sql`	`:customer_id`	те саме в PostgreSQL
`chain.cypher`	`$src`, `$dst`	найкоротший ланцюжок знайомств до 6 ребер: один рядок, колонка `path` зі списком `customer_id`
`chain.sql`	`:src`, `:dst`	те саме, `path` типу `bigint[]`; рекурсивний CTE

Рекомендації. Кандидат: покупець, який рівно на двох кроках дружби від $customer_id: не сам покупець і не його прямий друг. Він купував товари з категорії, в якій купував і $customer_id. Купівля: позиція замовлення, статус якого не cancelled. mutual_friends рахує різних спільних друзів, shared_categories різні категорії, в яких купували обоє. Порядок: shared_categories за спаданням, mutual_friends за спаданням, candidate_id за зростанням, не більше 10 рядків. Якщо рекомендувати нікого, запит повертає 0 рядків.

Ланцюжок. Дружба неорієнтована. Довжина ланцюжка не більша за 6 ребер. Найкоротших ланцюжків може бути кілька, підійде будь-який. Якщо в межах 6 ребер ланцюжка немає, запит повертає 0 рядків, а не висить. Граф має цикли.

Готово, коли ./labs/l10-graph/check.sh виводить «усе гаразд: 12 перевірок». Чого робити не треба: змінювати дані чи схему (перевірка відкриває обидві бази лише для читання), підключати плагіни Neo4j. Індекс по customer_friends ви створюєте вручну в базі shop за своїм бажанням, у файлах розв’язку DDL не буде.

Перед початком

Прочитайте модуль 18, принаймні розділи про Cypher, рекурсивний CTE і CYCLE. Підніміть два профілі й завантажте граф:

docker compose --profile postgres --profile neo4j up -d --wait
./dataset/loaders/neo4j/load.sh small
mkdir -p labs/l10-graph/solution && cp labs/l10-graph/starter/* labs/l10-graph/solution/

Усе виконується на розмірі small (Датасет).

Якщо compose запущено під власною назвою проєкту, передайте її: COMPOSE_PROJECT_NAME=моя-назва ./labs/l10-graph/check.sh. Два клієнти для експериментів:

docker compose exec postgres psql -U shop -d shop
docker compose exec neo4j sh -c 'cypher-shell -u neo4j -p "${NEO4J_AUTH#neo4j/}"'

Драйвер перевірки працює на bash усередині контейнерів, тож Node.js і Python на хості не потрібні.

Етапи

Огляньте граф у двох системах. Порахуйте друзів покупця 152 у customer_friends і в Neo4j (MATCH (:Customer {customer_id: 152})-[:FRIEND]-(f) RETURN count(f)). Числа мають збігтися. Спробуйте -[:FRIEND]-> замість -[:FRIEND]-: скільки друзів лишилося і чому.
Рекомендації в Cypher. Допишіть solution/recommend.cypher. Запускайте його в cypher-shell з параметром (:param customer_id => 4279). Перевірте на собі, а не на чекері: покупець, його прямі друзі й кандидати не мають перетинатись; mutual_friends для кожного кандидата не більший за кількість друзів покупця.
Рекомендації в SQL. Допишіть solution/recommend.sql. У psql параметр задають командою \set customer_id 4279. Порівняйте вивід із Cypher для двох-трьох покупців: рядок у рядок, включно з порядком. Якщо числа різняться, шукайте розмноження рядків у JOIN.
Ланцюжок у Cypher. Допишіть solution/chain.cypher. Спробуйте дві пари: 152 і 8, а потім 152 і 73. Що повертає запит для другої пари і чи правильна ця відповідь за умовою про шість ребер?
Ланцюжок у SQL. Допишіть solution/chain.sql. Спершу напишіть рекурсію без захисту від циклів і межі глибини, запустіть її на парі 152 і 102 з SET statement_timeout = '10s' і прочитайте помилку. Потім додайте захист: масив відвіданих або CYCLE, і межу глибини 6. Подивіться, як змінюється час з \timing.
Індекс і час. Заміряйте chain.sql для пари 152 і 8 у psql з \timing. Потім створіть індекс і повторіть:
```
CREATE INDEX customer_friends_friend_idx ON customer_friends (friend_id);
```
Запишіть обидва числа та поясніть різницю: який з двох напрямків ребра раніше читав усю таблицю на кожному кроці. DROP INDEX поверне базу в початковий стан, чекеру індекс не потрібен.
Здача. Запустіть ./labs/l10-graph/check.sh. Кожне «НІ» називає покупця або пару, якої стосується, і що саме не так: очікували рядків, зайвий кандидат, шлях не з друзів, потрібна довжина.

Перевірка

./labs/l10-graph/check.sh                 # ваш розв'язок з labs/l10-graph/solution/
./labs/l10-graph/check.sh інший/каталог
L10_TIMEOUT=60 ./labs/l10-graph/check.sh  # якщо машина повільна

Чекер запускає кожен ваш запит окремим викликом з параметрами: psql для SQL, cypher-shell для Cypher. Обидві бази відкриті лише на читання. Перевіряється чотири групи по кількох випадках.

Рекомендації, Cypher і SQL. Десять покупців: шестеро з рекомендаціями, четверо без. Порожній результат у тих чотирьох має різні причини: немає друзів, немає покупок, усі замовлення скасовані, у друзів друзів немає спільних категорій. Рядки порівнюються з еталоном, порядок важливий.
Ланцюжок, Cypher і SQL. Сімнадцять пар. В одинадцяти ланцюжок довжиною від 1 до 6 ребер, і чекер перевіряє сам шлях: починається з $src, закінчується на $dst, кожна пара сусідів справді друзі, вузли не повторюються і довжина дорівнює найкоротшій. Будь-який із кількох найкоротших підходить. Ще три пари мають шлях довший за 6 ребер (очікується порожній результат), і ще три не мають жодного (покупець без друзів або з окремого кола з чотирьох покупців).

Ліміт часу одного запиту: 20 секунд. Він узятий із запасом: еталонний SQL на small з найдружнішого покупця виконується за 1.8 с без індексу по friend_id і за 70 мс з ним. Запит, що не вкладається, чекер зупиняє, пише «перевищено ліміт часу» і не перевіряє решту пар цієї групи. Якщо контейнер зупинено або з’єднання втрачено, чекер повідомляє про збій середовища й завершується з кодом 3 замість «усе гаразд». Весь прогін триває 1.5–2 хвилини.

Часті помилки

Друзі друзів без виключень. Шлях «друг, і назад» повертає самого покупця, а багато хто з друзів друзів є й прямим другом. Виключіть обох.

Лічильники шляхів замість людей. До кандидата й до категорії ведуть різні шляхи, і count(*) після JOIN їх розмножує. mutual_friends і shared_categories рахують різні значення. У SQL зручно спершу звести кожну частину до одного рядка на кандидата, а тоді приєднати JOINом.

Один MATCH для всього шляху. Одне ребро в шаблоні не береться двічі, тож категорія товару, який купили обидва, випадає. Розбийте шлях на два MATCH.

-[:FRIEND]-> або customer_id = :id без другого напрямку. Пара збережена один раз, і половина друзів губиться.

Скасовані замовлення. Статус лежить на ребрі BOUGHT і в orders.status.

Рекурсія без межі в SQL. UNION ALL без обмеження глибини й без перевірки відвіданих у графі з циклами не завершується. Чекер повідомить про перевищення часу на парі без шляху. Межа лише на глибину теж не гарантує швидкості, але на small з цим можна жити.

shortestPath без межі в Cypher. [:FRIEND*] знайде ланцюжок з 7 чи 8 ребер, а за умовою їх немає: чекер скаже, що очікував порожній результат.

ORDER BY у SQL проти LIMIT 1. Сортування змушує перебрати всі шляхи до глибини 6, і на найдружнішому покупцеві це секунди без індексу. Обидві форми допустимі, тож вибирайте свідомо.

Docker дивиться на віддалену машину. Якщо docker context ls показує зірочку біля SSH-адреси, docker compose працює там. docker context use desktop-linux (Docker Desktop) або default (Linux).

Далі, якщо цікаво

Напишіть пошук у ширину (BFS) з відновленням шляху через UNION і порівняйте з масивом на парі 152 і 8: рядків у CTE, час, EXPLAIN (ANALYZE, BUFFERS). Підніміть medium (./setup/generate-dataset.sh medium, ./setup/load-dataset.sh medium --reset, ./dataset/loaders/neo4j/load.sh medium) і повторіть заміри з кроку 6: де зазор між PostgreSQL з індексом і Neo4j збільшується, а де ні. Спробуйте SHORTEST 3 у Cypher і придумайте, як це записати в SQL.