Доброго всем дня!

Есть у меня большой социальный граф - 1.6 млн пользователей (вершины графа) и 22 млн связей между ними (ребра)
Так же есть около 1 млн пар (юзер, юзер), для которых нужно посчитать некоторые значение - все это будет использоваться для link prediction. 

Имеются следующие таблицы (DDL):

• users(user): ключ на user
• edges(to, from): две таблицы с одинаковыми данными, ключ в первой  (to, from), а во второй (from, to)
• membership(user, community): ид групп в которых состоят пользователи
• target edges - 1.1 млн пар, для которых нужно выполнить запрос ниже

Вот, собственно, запрос:

Вот Explain Plan этого запроса

Запрос будет выполнятся пачками по 1000 шт, т.к. вычисляется долго, чтобы соединение не отваливалось.

Как можно оптимизировать этот запрос, чтобы он выполнялся хотя бы минуту для 1 тыс строк? Сейчас вычисление отваливаются по таймауту после 10 мин

Добавлено через 1 минуту и 15 секунд
Немного подробнее про запрос

Граф этот направленный, поэтому правильнее сказать, что в графе не друзья, а "подписчики"



Кол-во людей на которых подписаны и а и б



Кол-во людей подписавшихся на а и б




кол-во людей в пересечении прошлых двух запросов 




кол-во подписчиков на а умножить на кол-во подписчиков на б



Кол-во групп, в которых состоят оба пользователя




кол-во подписчиков на а и на б



кол-во людей на которых подписаны и а и б



кол-во людей из пересечения прошлых двух запросов

0) LIMIT без ORDER -- безсмысленнен и вреден. Если Вам кажэтся, что он делает что-то полезное -- то Вы ошыбаетесь.
0.5) Да и вообще лучшэ его не использовать. Кривая конструкцыя.
Надо вам тут такой шардинг? Ну, вставьте номер в эту табличку pairs или ещё как-то её виртаульно поделите на кусочки.
1) Оптимизируйте по одному запросу. Сейчас я совершэнно не могу понять в plan, кто там от кого стоял. В смысле -- какой dependenet subquery относится к какому запросу. Ну, не совершэнно -- часто, конечно, имена проскакивают, но сложно это всё.
Кроме того, так Вы сможэт понять, какой из запросов выполняется быстро, а какой -- нет, и требует доводки или промежуточных таблиц.
2) Оставьте одну таблицу edges, с двумя индэксами. См. CREATE INDEX.
3) Постарайтесь выполнить этот запрос на компьютэре, в котором всё содержымое базы влезает в память. Кажэтся, 8GB должно хватить.

Спасибо за ответ


А как еще можно выполнять этот запрос кусочками по 1000? Добавить id и добавлять в where фильтр по этому id? 



Сейчас я понял, что именно последние три запроса вызывают проблему - если их убрать, то 1000 строк считаются за 40 секунд. 


Что еще интересно



Эти два запроса вычисляют одно и то же значение, только первый это делает за доли секунды (мускль пишет 0.000 сек), а второй - 12.808. 

Первый 


Второй


Если убрать or, то второй запрос так же выполняется мгновенно 





Какая принципиальная разница между этими двумя запросами? Он во втором full scan делает? Судя по кол-ву строк в dependent subquery   

В этом случае один из индексов будет unclustered, т.е. по одной дополнительной I/O операции на каждый index lookup - что на таких объемах будет заметно. Или я не прав? 



Т.е. для всех таблиц из запроса сделать engine=MEMORY и запустить? У меня как раз 8 гб, но когда я попробовал сунуть таблицу edges целиком в память (выделил под heap таблицы 2 гб - влезло) - получилось даже медленнее. При этом для таблицы в памяти я сделал два индекса. Видимо я что-то не так сделал?

Очевидно не так. По умолчанию в MEMORY в качестве индекса используется HASH а не BTree, поэтому запрос выполнялся совсем не так, как я предполагал. В итоге добавил в табличку два BTree индекса на (source, target) и (target, source) и все заработало. 5 тыс строк за 20 сек считаются. Возможно еще есть куда дальше оптимизировать, но такой прирост производительности сейчас более чем устраивает. 

Спасибо большое за помощь.

Например. Это был первый мой вариант. Второй -- ну, поделите в уме pairs.a на отрезки, и указывайте BETWEEN в WHERE.



Да нет, этого вобще говоря не требуется. Вот пройти их каким-нибудь index range scanом, чтобы соответствующие индэксы цэликом закачались в память -- вот это было бы полезно.

А что это значит? И как это можно сделать? 

Проблема уже решена, но все равно интересно  

<quote>&gt;А что это значит? И как это можно сделать? </quote>

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