Ваша задача на практике неразрешима — ни средствами СУБД, ни даже написанием программы, реализующей алгоритм.
Объясню почему. Давайте для простоты решим, что мы ищем только пути, не посещающие одну вершину более 1 раза — так называемые «простые» пути. Если не налагать это ограничение, то количество путей будет несравнимо больше, а при наличии в графе циклов — бесконечным.
Но даже перечисление простых путей невозможно при таком размере графа. Дело в том, что количество простых путей из вершины А в вершину В зависит экспоненциально от количества ребер в графе. Эксполненциальный рост сложности приводит к тому, что при количестве ребер свыше десятков перечисление путей занимает неприемлемо долгое время. В случае с миллионами ребер всё еще гораздо хуже.
Вы можете попробовать реализовать поиск в глубину и лично убедиться.
Замечу, что при наложении на структуру графа некоторых строгих ограничений (например, не более 2 ребер, выходящих из каждой вершины) время работы поиска в глубину становится приемлемым — полиномиальная асимптотика вместо экспоненты. Но на практике такими графами дело, конечно же, не ограничивается.
