Двойной JOIN из двух таблиц - Базы данных

В базе SQlite имеются таблицы (упрощенно): posts(to_id, from_id, text), users (id, name), groups (id, name).
Для того чтобы вывести posts в удобочитаемом виде, нужно заменить to_id и from_id на имена.
Оба идентификатора to_id и from_id могут указывать как на юзера, так и на группу, причем в posts у юзеров положительные id, а у групп отрицательные (так сделано к примеру в соцсети vk).

Провел эксперимент с таким запросом (LEFT JOIN потому что не все to_id, from_id существуют в таблицах users и groups, а записи все равно нужны):

SELECT
   CASE WHEN posts.to_id   > 0 THEN u_to.name   ELSE g_to.name   END AS to_name,
   CASE WHEN posts.from_id > 0 THEN u_from.name ELSE g_from.name END AS from_name,
   posts.to_id,
   posts.from_id,
   posts.text
FROM posts
LEFT JOIN users  AS u_to   ON posts.to_id   =  u_to.id
LEFT JOIN groups AS g_to   ON posts.to_id   = -g_to.id
LEFT JOIN users  AS u_from ON posts.from_id =  u_from.id
LEFT JOIN groups AS g_from ON posts.from_id = -g_from.id
WHERE ... ORDER BY ... LIMIT ... OFFSET ...

и оказалось, что на последних страницах пагинации все это достаточно заметно подтормаживает (хотя данных пока не много — 5000 постов, 300000 юзеров и 4000 групп).

Далее попытался выяснить что именно подтормаживает. Убрал условный JOIN, приняв для эксперимента что to_id всегда группа а from_id всегда юзер (т.е. осталось 2 джойна вместо 4). Не помогло, задержки остались. А вот если принять, что to_id и from_id всегда юзеры, и убрать группы из запроса вообще (опять же 2 джойна вместо 4), то скорость становится нормальной. Получается, что дополнительные джойны даже при небольшом размере таблицы существенно замедляет работу запроса.

Прав ли я в своих рассуждениях? Все ли я правильно делаю? Есть ли альтернативные решения этой задачи в целом?

Думаю о варианте вообще объединить юзеров и группы в одну таблицу — у них значительная часть полей общая, в 99% случаев только она и нужна, а отличающиеся поля оставить в добавочных таблицах, связанных "один к одному" с главной.

Здравствуйте, x-code, Вы писали:

XC>В базе SQlite имеются таблицы (упрощенно): posts(to_id, from_id, text), users (id, name), groups (id, name).

В первую очередь я бы проверил план запроса (EXPLAIN QUERY PLAN) на предмет использования индексов. Из приведеного вами запроса нет особой разницы между users и groups. И выглядит так, что где-то индексы есть, а где-то их нет. Для этого посмотрите план запроса.

Тем не менее, в запросе делается двойная работа (фактически вместо созданием агрегатов имен в таблице posts) вы делаете двойную работу по выборке этих имен из других таблиц.

...<< Dementor ^1.5.4 ✪ Lets Play a Game ⚁⚃⚄⚄⚄>>

Здравствуйте, x-code, Вы писали:
XC>В базе SQlite

XC>

XC>FROM posts
XC>LEFT JOIN users  AS u_to   ON posts.to_id   =  u_to.id
XC>LEFT JOIN groups AS g_to   ON posts.to_id   = -g_to.id
XC>LEFT JOIN users  AS u_from ON posts.from_id =  u_from.id
XC>LEFT JOIN groups AS g_from ON posts.from_id = -g_from.id
XC>WHERE ... ORDER BY ... LIMIT ... OFFSET ...
XC>

XC>5000 постов, 300000 юзеров и 4000 групп.

XC>Далее попытался выяснить что именно подтормаживает. Убрал условный JOIN, приняв для эксперимента что to_id всегда группа а from_id всегда юзер (т.е. осталось 2 джойна вместо 4). Не помогло, задержки остались. А вот если принять, что to_id и from_id всегда юзеры, и убрать группы из запроса вообще (опять же 2 джойна вместо 4), то скорость становится нормальной. Получается, что дополнительные джойны даже при небольшом размере таблицы существенно замедляет работу запроса.

XC>Прав ли я в своих рассуждениях? Все ли я правильно делаю? Есть ли альтернативные решения этой задачи в целом?

Ну смотри. Это SQLite, он может только nested loop join. То есть ты можешь считать, что у тебя условно всегда foreach вместо join. То есть без индексов у тебя будет на вышеприведенном запросе следующее количество операций:
5000*300000*4000*300000*4000 == 72*10²⁰ * **
В первом варианте с двумя джоинами
5000*300000*4000 == 75*10¹¹
во втором варианте с "двумя" джоинами на самом деле только один
5000*300000 = 15*10⁸

* на самом деле там нужно делить еще каждый join на два, так как среднее на нахождение записи будет x/2, да и черт с ним, на количество нулей не влияет
** при наличии индексов сам посчитаешь количество операций, это не влияет на оптимизацию

Идею понял?

То есть даже банальное

FROM posts
    LEFT JOIN users  AS u_to   ON posts.to_id   =  u_to.id
    LEFT JOIN users  AS u_from ON posts.from_id =  u_from.id
    LEFT JOIN groups AS g_to   ON posts.to_id   = -g_to.id
    LEFT JOIN groups AS g_from ON posts.from_id = -g_from.id

может помочь (если оптимизатор совсем тупой ***).

*** никогда не ведись на мысли вроде "ну они ж не совсем тупые, не могли же они такую тривиальщину пропустить", всегда проверяй — в реальности все плохо

XC>Думаю о варианте вообще объединить юзеров и группы в одну таблицу — у них значительная часть полей общая, в 99% случаев только она и нужна, а отличающиеся поля оставить в добавочных таблицах, связанных "один к одному" с главной.

Да нафиг, считывай только посты. Построй себе в памяти хештаблицы для users и groups (304000 должны влезть в память незаметно и спокойно) и присваивай уже "в приложении". Такой ручной hash join побыстрее будет в твоем случае.

Или нет, лучше просто тупо массивы, получится merge join.

Это ж SQLite, ты на сервер не спихнешь работу, все у тебя локально все равно будет вычисляться.

PS Я вообще боюсь, что выбор 20 постов и 40 запросов для вытягивания name у тебя быстрее отработают, чем любой запрос с join-ами или возня с массивами (словарями). У тебя нет network latency, пользуйся.

Здравствуйте, x-code, Вы писали:

XC>Далее попытался выяснить что именно подтормаживает. Убрал условный JOIN, приняв для эксперимента что to_id всегда группа а from_id всегда юзер (т.е. осталось 2 джойна вместо 4). Не помогло, задержки остались.
1. Попробуйте такого вида условия
LEFT JOIN groups AS g_to ON g_to.id=(-1)*posts.to_id
2. Сделать 4 select с Join (Юзер-Юзер, Группа-Юзер, Юзер-Группа, Группа-Группа) объединив через Union all

Здравствуйте, Ромашка, Вы писали:

Р>Ну смотри. Это SQLite, он может только nested loop join. То есть ты можешь считать, что у тебя условно всегда foreach вместо join. То есть без индексов у тебя будет на вышеприведенном запросе следующее количество операций:
Р>5000*300000*4000*300000*4000 == 72*10²⁰ * **
Р>В первом варианте с двумя джоинами
Р>5000*300000*4000 == 75*10¹¹
Р>во втором варианте с "двумя" джоинами на самом деле только один
Р>5000*300000 = 15*10⁸
Ну, это странно. Я предполагаю, что id в обеих таблицах объявлены как primary key, а SQLite вроде бы для них создаёт индексы. Так что можно рассчитвать на log(N).
Так что left join users — это 5000*log(300000).
Дальше, мы ж для каждой строчки находим не более одного пользователя, так что left join groups — это 5000*(log(300000)+log(4000)).
Дальше — то же самое, так что итого у нас операций будет 5000*(log(300000)+log(4000)+log(300000)+log(4000)).
Вроде бы немного.

Р>** при наличии индексов сам посчитаешь количество операций, это не влияет на оптимизацию[/i]

Р>Идею понял?

Р>То есть даже банальное
Р>

Р>FROM posts
Р>    LEFT JOIN users  AS u_to   ON posts.to_id   =  u_to.id
Р>    LEFT JOIN users  AS u_from ON posts.from_id =  u_from.id
Р>    LEFT JOIN groups AS g_to   ON posts.to_id   = -g_to.id
Р>    LEFT JOIN groups AS g_from ON posts.from_id = -g_from.id
Р>

Р>может помочь (если оптимизатор совсем тупой ***).
Не, не помогает (и не должно).
https://www.db-fiddle.com/f/cwvYp2P2SB2a2HzVRK3ZWm/4

Но оптимизатор там действительно совсем тупой. Правильный ответ:

SELECT
   CASE WHEN p.to_id   > 0 THEN u_to.name   ELSE g_to.name   END AS to_name,
   CASE WHEN p.from_id > 0 THEN u_from.name ELSE g_from.name END AS from_name,
   p.to_id,
   p.from_id,
   p.text
FROM (select * from posts 
-- where ...
-- order by ...
 limit 10 offset 8000) p
LEFT JOIN users  AS u_to   ON p.to_id   =  u_to.id
LEFT JOIN groups AS g_to   ON p.to_id   = -g_to.id
LEFT JOIN users  AS u_from ON p.from_id =  u_from.id
LEFT JOIN groups AS g_from ON p.from_id = -g_from.id

См. тайминги в https://www.db-fiddle.com/f/cwvYp2P2SB2a2HzVRK3ZWm/5

Здравствуйте, x-code, Вы писали:
XC>Прав ли я в своих рассуждениях? Все ли я правильно делаю? Есть ли альтернативные решения этой задачи в целом?
Нужно отбор и пагинацию делать до join.

S>Нужно отбор и пагинацию делать до join.

Кстати на MS SQL (разных версий от 2008 до 2019) наблюдал аналогичное:
в запросе INNER JOIN и TOP N. Основное время запроса тратилось на Clustered Index Scan по одной таблиц (большой как по количеству рядов, так и по размеру данных в ряду).
По второй таблице был относитльно быстрый Index Seek.
Так вот, время выполнения от N не зависело, хотя при небольших N достаточное количество рядов должно было набираться уже в начале большой таблицы.
В execution плане был merge join, и если через опции форсировать nested loop join, то TOP отрабатывал на этапе JOIN, как ожидалось.
Время выполнения соответственно уменьшалось фактически в (размер большой таблицы)/N раз.
Вот такие чудеса.

Здравствуйте, Sinclair, Вы писали:

S>Ну, это странно. Я предполагаю, что id в обеих таблицах объявлены как primary key, а SQLite вроде бы для них создаёт индексы. Так что можно рассчитвать на log(N).
А индексы на
-g_to.id и -g_from.id
есть?
в запросе именно по таким значениям идет соединение.
соединение ON -posts.to_id = g_to.id должно использовать индекс

Здравствуйте, IZM, Вы писали:
S>>Ну, это странно. Я предполагаю, что id в обеих таблицах объявлены как primary key, а SQLite вроде бы для них создаёт индексы. Так что можно рассчитвать на log(N).
IZM>А индексы на
IZM> -g_to.id и -g_from.id
IZM>есть?
Я про них и говорю. g_to и g_from — это алиасы для таблицы groups. В ней поле id должно быть объявлено как primary key. Если нет — это надо починить; если да — то sqlite сам создаст для них индексы.
IZM>в запросе именно по таким значениям идет соединение.
IZM>соединение ON -posts.to_id = g_to.id должно использовать индекс
Всё легко увидеть, написав перед запросом explain query plan.
Можете сходить по ссылке и поиграть: https://www.db-fiddle.com/f/cwvYp2P2SB2a2HzVRK3ZWm/5

Здравствуйте, Sinclair, Вы писали:

S>Я про них и говорю. g_to и g_from — это алиасы для таблицы groups. В ней поле id должно быть объявлено как primary key. Если нет — это надо починить; если да — то sqlite сам создаст для них индексы.
Я спрашивал про Индекс не на ID, а на "-ID", именно это и используется при соединении для таблиц Groups.
S>Можете сходить по ссылке и поиграть: https://www.db-fiddle.com/f/cwvYp2P2SB2a2HzVRK3ZWm/5
не игрался с Sqlite, но Oracle и PostGreSql дают следующий пример:
Есть:
таблица tb1 (id number ,name varchar2(200)), есть 2 индекса по полю id и name
таблица tb2 (id_tb1 number ,name varchar2(200)), есть индекс по полю id_tb1
эмулируем отрицательное ко-во в 1-й таблице, и делаем соединение со 2-й таблицей:

--1-й вариант (соединение аналогично соединению как у автора)
select *
from 
  (select -id as id, name from tb1 where name like 'тру-ля-ля%') q
              join tb2 qq on (q.id=-qq.id_tb1);
--Индекс по name используется, по id_tb1 не используется (и не должен),должен использоваться по "-id_tb1", а его нет
select *
from 
  (select -id as id, name from tb1 where name like 'тру-ля-ля%') q
              join tb2 qq on (-q.id=qq.id_tb1);
--Индекс по name используется, по id_tb1 Индекс используется

Здравствуйте, IZM, Вы писали:

IZM>Здравствуйте, Sinclair, Вы писали:

S>>Я про них и говорю. g_to и g_from — это алиасы для таблицы groups. В ней поле id должно быть объявлено как primary key. Если нет — это надо починить; если да — то sqlite сам создаст для них индексы.
IZM>Я спрашивал про Индекс не на ID, а на "-ID", именно это и используется при соединении для таблиц Groups.
Бинго! Слона-то я и не приметил.
Вы совершенно правы; и, более того, проблема — именно в этом.
Индекс по -ID не нужен — нужно просто перенести negation на другую сторону сравнения.

https://www.db-fiddle.com/f/cwvYp2P2SB2a2HzVRK3ZWm/6

Здравствуйте, x-code, Вы писали:
XC>Далее попытался выяснить что именно подтормаживает.
Подтормаживают здесь вот эти сравнения: posts.from_id = -g_from.id. (Спасибо коллеге IZM за внимательность).
С точки зрения оптимизатора, это не "sargeable query" — в таблице групп ищутся строки по некоторому выражению, поэтому выполняется прямой перебор.
Увидеть это можно при помощи explain query plan (https://www.db-fiddle.com/f/cwvYp2P2SB2a2HzVRK3ZWm/7).
Вот смотрите, какой план у вашего исходного запроса:

id	detail
12	SCAN posts
14	SEARCH u_to USING INDEX sqlite_autoindex_users_1 (id=?) LEFT-JOIN
23	SCAN g_to LEFT-JOIN
31	SEARCH u_from USING INDEX sqlite_autoindex_users_1 (id=?) LEFT-JOIN
40	SCAN g_from LEFT-JOIN

А вот план

запроса, в котором negation перенесён на сторону таблицы posts

SELECT
   CASE WHEN posts.to_id   > 0 THEN u_to.name   ELSE g_to.name   END AS to_name,
   CASE WHEN posts.from_id > 0 THEN u_from.name ELSE g_from.name END AS from_name,
   posts.to_id,
   posts.from_id,
   posts.text
FROM posts
LEFT JOIN users  AS u_to   ON posts.to_id   =  u_to.id
LEFT JOIN groups AS g_to   ON -posts.to_id   = g_to.id
LEFT JOIN users  AS u_from ON posts.from_id =  u_from.id
LEFT JOIN groups AS g_from ON -posts.from_id = g_from.id
LIMIT 10 OFFSET 8000;

id	detail
14	SCAN posts
16	SEARCH u_to USING INDEX sqlite_autoindex_users_1 (id=?) LEFT-JOIN
25	SEARCH g_to USING INDEX sqlite_autoindex_groups_1 (id=?) LEFT-JOIN
35	SEARCH u_from USING INDEX sqlite_autoindex_users_1 (id=?) LEFT-JOIN
44	SEARCH g_from USING INDEX sqlite_autoindex_groups_1 (id=?) LEFT-JOIN

Видите? Третья и пятая строчки теперь вместо SCAN (линейный поиск) выполняют SEARCH USING INDEX — то есть O(log(N)) запросы.

	От:	x-code
	Дата:	20.01.24 22:47
	Оценка:

	От:	r0nd
	Дата:	21.01.24 17:45
	Оценка:

	От:	Ромашка
	Дата:	21.01.24 22:25
	Оценка:	3 (1)

	От:	IZM
	Дата:	22.01.24 10:50
	Оценка:

От:	Sinclair	https://github.com/evilguest/
Дата:	25.01.24 12:38
Оценка: