Сложный запрос к БД

Question

[vizgl]

Имеется 2 таблицы:
PlayersData:
uid int PK
score int
level int

MapsScores
map_id int PK
user_id int PK
score int

Таблица PlayersData хранит: лучший результат игрока за все игры(score), его id и уровень(level). В таблице MapsScores хранится: id карты(map_id), id пользователя(user_id) и счет полученный игроком на картe(score). Еще таблица MapsScores имеет составной ключ по id карты и id игрока.

Задача заключается в построении топа игроков по определенной карте, этот запрос получился таким(для примера, выведем для карты с id = 3):

SELECT 
   ms.user_id uid, ms.score, pd.level
FROM
    MapsScores ms
        LEFT JOIN PlayersData pd ON ms.user_id = pd.uid
WHERE
    ms.map_id = 3
ORDER BY ms.score DESC
LIMIT 20

Тут все просто, берутся 20 лучших результатов и выводятся:
user_id
score
level

Таких карт 50 штук, и для каждой нужно построить топ игроков. Получается в php скрипте я в цикле перебираю id карт и делаю 50 запросов к бд, с последующим сохранением данных.
Но тут есть 2 проблемы:
— id карт могут идти не по порядку
— Как-то не хочется делать цикл из 50 запросов к бд за один раз.

Теперь вопрос. Можно ли сделать такой запрос, который бы сразу вывел топы для всех карт хотя бы в таком виде:
1 1 999 1
1 2 998 1
1 3 997 1
…
25 4 999 1
25 5 990 1
…
50 6 999 1
50 7 995 1

Где, столбце 1 — id карты;
столбец 2 — id игрока
столбец 3 — очки
столбец 4 — уровень

Т.е. по сути в самом запросе перебрать все id карт и записать в вывод топ игроков. Дальше я уже в php смогу определить, какая строка результата, к какой таблице относится.

Answer 1

[karellen]

Если бы вы залили тестовые данные куда-то, было бы проще проверить, но так есть вот такой трюк с MySQL — не факт, что это будет работать быстрее, и выглядит это жутко, так что выбор использовать это или нет исключительно за вами :)

SELECT 
  t.map_id,
  t.score,
  pd.level 
FROM
  (SELECT 
    ms1.map_id,
    ms1.score,
    ms1.user_id 
  FROM
    MapsScores ms1 
    LEFT JOIN MapsScores ms2 
      ON ms1.map_id = ms2.map_id 
      AND ms1.score >= ms2.score 
  GROUP BY ms1.map_id,
    ms1.score 
  HAVING COUNT(*) <= 20) t 
  LEFT JOIN PlayersData pd 
    ON t.user_id = pd.uid 
ORDER BY 1,
  2 DESC

Comments

[vizgl]

Спасибо, заработало с первого толчка. Сейчас буду проводить спидтесты.

[karellen]

Если скорость важна — посмотрите на Redis, там есть предназначенные для leaderboards конструкции (Z...). Интересный линк: blog.agoragames.com/blog/2011/01/02/creating-high-score-tables-leaderboards-using-redis-2/ — только учтите, что все данные в памяти (и бэкап на диске).

Answer 2

[Сергей Протько]

SELECT p.uid, p.level, p.score, m.map_id FROM PlayersData p INNER JOIN MapsScores m ON m.map_id=p.map_id ORDER BY p.score DESC GROUP BY p.map_id HAVING COUNT(p.uid) <= 20

Что-то на подобии этого, быть может? Увы проверить не могу.

Answer 3

[Lev Lybin]

Не стоит делать громоздкий запрос.
> id карт могут идти не по порядку
это не проблема, получите список id ваших карт и foreach, либо disinct по MapsScoresи foreach

Answer 4

[nmike]

ну вот если хочется поизвращаться :)

SET @place := 0, @map_id := 0;

SELECT 
	IF(@map_id != map_id, @place := 1, @place := @place + 1) AS place, 
	IF(@map_id != map_id, @map_id:=map_id, map_id) AS map_id,  
	user_id, map_score , level, @place
FROM (
  SELECT m.map_id, m.user_id, m.score AS map_score, p.level
    FROM MapsScores AS m, PlayersData AS p 
   WHERE m.user_id = p.id
   GROUP BY m.map_id, m.user_id 
   ORDER BY m.map_id ASC, m.score DESC
) AS tops
GROUP BY map_id, user_id HAVING place <= СКОЛЬКО_НАРОДУ_ХОТИТЕ_В_ТОП
ORDER BY map_id ASC, map_score DESC

но проще сделать 50 запросов на каждую карту в отдельности — мускул вам будет благодарен :)

Answer 5

[Stdit]

Этой проблеме много лет, и о ней много написано на разных ресурсах (search). Помимо предлагаемых вариантов запросов разной степени жуткости, можно использовать денормализацию (занесение данных во вспомогательную таблицу-топ на триггерах или по крону).

Answer 6

[nmike]

это выведет всех, но с сортировкой

SELECT m.map_id, m.user_id, m.score AS map_score, p.level
  FROM MapsScores AS m, PlayersData AS p
 WHERE m.user_id = p.id 
 GROUP BY m.map_id, m.user_id
 ORDER BY m.map_id ASC, m.score DESC

а вот как отрезать в момент выборки…

Comments

[vizgl]

Если бы записей было немного, то подошел бы и этот метод, можно было бы руками обрезать все ненужное.
Но я записей может быть больше 1 миллиона.

[Lev Lybin]

тем более не стоит делать сложный запрос, а оптимизировать этот + кэширование.
я бы для каждой карты выбрал бы 20 лучших сначала, потом запросил бы для каждого user_id его уровень вторым запросом where user_id IN (из первого) и в кэш со временем жизни, все будет быстро

[nmike]

Но тут есть 2 проблемы:
— id карт могут идти не по порядку
— Как-то не хочется делать цикл из 50 запросов к бд за один раз.

порядок можете сделать в пхп, а 50 простых запросов к бд лучше одно убойного :) с ужасной картой запроса.

[vizgl]

Спасибо за подсказку про кэширование.
Вообще я пишу flash игру и попутно серверную часть, вот приходится разбираться с тонкостями работы с БД.

Answer 7

[rechik]

Ответ к самому вопросу не относиться. Но саму задачу решил бы хорошо. Можно закешировать результат запроса и в фоне с помощью крона раз в минуту обновлять его. В результате фронтенд работает только с кешем, и к БД вообще не делает запросов.

Answer 8

[vizgl]

В общем сделал, как подсказывали.
1) Получаю id всех карт.
2) Для каждой карты строю список запросом, который приведен в вопросе.
3) Кэширую полученные данные.

Кэширование пришлось сделать извращенное, т.к. сервер у меня работает на виртуальном хостинге и Memcached не доступен.
Первое, что пришло в голову — это сделать memory таблицу и хранить закешированные данные в ней, данные будут хранится в формате json. После тестов, оказалось, что для хранения всех(текстовых) данных, недостаточно 65536 байт. В итоге, пришлось сделать обычную таблицу, и хранить в ней с типом данных blob.

Кому интересно, вот код:

function CacheGet($key)
{
	$query =  "SELECT ";
	$query .= "  data ";
	$query .= "FROM ";
	$query .= "  CacheTable ";
	$query .= "WHERE ";
	$query .= "  name = \"".$key."\" ";
	$query .= "  AND (expire > ".time()." OR locked = 1)";

	$result = mysql_query($query);

	if ($result == false)
	{
		return false;
	}
	else
	{
		$data = mysql_fetch_array($result, MYSQL_ASSOC);

		return $data[data];
	}
}

// lock cache while one process write new updated data
function CacheLock($key)
{
	$query =  "INSERT INTO CacheTable (name, locked) ";
	$query .= "  VALUES(\"".$key."\", 1) ";
	$query .= "ON DUPLICATE KEY UPDATE ";
	$query .= "  name = VALUES(name),";
	$query .= "  locked = VALUES(locked)";

	mysql_query($query);
}

function CacheSet($key, $data, $expire)
{
	$query =  "INSERT INTO CacheTable (name, data, expire, locked) ";
	$query .= "  VALUES(\"".$key."\", \"".mysql_real_escape_string($data)."\", ".(time() + $expire).", 0) ";
	$query .= "ON DUPLICATE KEY UPDATE ";
	$query .= "  name = VALUES(name), ";
	$query .= "  data = VALUES(data), ";
	$query .= "  expire = VALUES(expire), ";
	$query .= "  locked = VALUES(locked)";

	mysql_query($query);
}

Теперь при получении топа, если функция CacheGet возвращает false, то мы блокируем данные по этому ключу, чтобы другие пользователи тоже не начали записывать новые данные в кэш. А дальше, после записи обновленных данных, разблокируем данные по этому ключу.