EXPLAIN EXTENDED

Answering questions asked on the site.

Beren asks:

In my database, I store the information about the game matches.

A match can be played between two players (mostly) or, occasionally, between two teams of 2, 3 or 4 players.

I store the matches in a table like this:

Game

id	player1	player2	type

, where type is ENUM(player, team).

If type is player, the ids of players are stored in the record; if type is team, those of teams are stored.

Now, the tricky part. For a given game, I need to select two lists of players from both sides, comma separated, be they single players or members of a team.

Are two separate queries required for this?

This of course can be easily done using a single query.

Let's make a sample table and see:

Table creation details

CREATE TABLE filler (
id INT NOT NULL PRIMARY KEY AUTO_INCREMENT
) ENGINE=Memory;

CREATE TABLE game
(
id INT NOT NULL PRIMARY KEY,
name VARCHAR(30) NOT NULL,
player1 INT NOT NULL,
player2 INT NOT NULL,
type ENUM('player', 'team')
)
ENGINE=InnoDB;

CREATE TABLE player
(
id INT NOT NULL PRIMARY KEY,
name VARCHAR(30) NOT NULL
)
ENGINE=InnoDB;

CREATE TABLE team
(
id INT NOT NULL PRIMARY KEY,
name VARCHAR(30) NOT NULL
)
ENGINE=InnoDB;

CREATE TABLE player_team
(
team INT NOT NULL,
player INT NOT NULL,
PRIMARY KEY (team, player)
)
ENGINE=InnoDB;

DELIMITER $$

CREATE PROCEDURE prc_filler(cnt INT)
BEGIN
DECLARE _cnt INT;
SET _cnt = 1;
WHILE _cnt <= cnt DO
                INSERT
                INTO    filler
                SELECT  _cnt;
                SET _cnt = _cnt + 1;
        END WHILE;
END
$$

DELIMITER ;

START TRANSACTION;
CALL prc_filler(500000);
COMMIT;

INSERT
INTO    player
SELECT  id, CONCAT('Player ', id)
FROM    filler
ORDER BY
        id
LIMIT 100000;

INSERT
INTO    team
SELECT  id, CONCAT('Team ', id)
FROM    filler
ORDER BY
        id
LIMIT 3000;

INSERT
INTO    player_team
SELECT  t.id,
        FLOOR(RAND(20101020) * 25000) * 4 + num
FROM    team t
JOIN    (
        SELECT  1 AS num
        UNION ALL
        SELECT  2
        UNION ALL
        SELECT  3
        UNION ALL
        SELECT  4
        ) n
ON      n.num <= ((t.id - 1) % 3) + 2;

INSERT
INTO    game
SELECT  id, CONCAT('Game ', id),
        CASE n
        WHEN 1 THEN
                CEILING(RAND(20101020 << 2) * 100000)
        ELSE
                FLOOR(RAND(20101020 << 3) * 1000) * 3 + n - 1
        END,
        CASE n
        WHEN 1 THEN
                CEILING(RAND(20101020 << 4) * 100000)
        ELSE
                FLOOR(RAND(20101020 << 5) * 1000) * 3 + n - 1
        END,
        CASE n
        WHEN 1 THEN
                'player'
        ELSE
                'team'
        END
FROM    (
        SELECT  id, -FLOOR(LOG10(POWER(30, -4) + RAND(20100930) * (1 - POWER(30, -4))) / LOG10(30)) AS n
        FROM    filler
        ) q;

The tables contain 500,000 games, 100,000 players and 3,000 teams.

The participants in the games are distributed logarithmically: 95% of all games are single player, 95% of the remaining games are played by 2×2 teams, etc.:

The model above may seem quite weird, since the single players can be assigned to the fake teams so that the joins will be always performed through the player_team table. However, it's not required and in fact is less efficient. We don't really need that extra lookup if we can find a player right away, using its id, and since the majority of games are single player, majority of queries will be too.

Let's see how we can build a list of players' names. First, let's do it for the player1 part only:

SELECT  g.id, g.name, GROUP_CONCAT(p.name SEPARATOR ', ') AS players
FROM    game g
LEFT JOIN
player_team pt
ON      g.type = 'team'
AND pt.team = g.player1
JOIN    player p
ON      p.id = CASE g.type WHEN 'player' THEN g.player1 WHEN 'team' THEN pt.player END
GROUP BY
g.id
LIMIT 50

select `20101020_matches`.`g`.`id` AS `id`,`20101020_matches`.`g`.`name` AS `name`,group_concat(`20101020_matches`.`p`.`name` separator ', ') AS `players` from `20101020_matches`.`game` `g` left join `20101020_matches`.`player_team` `pt` on(((`20101020_matches`.`pt`.`team` = `20101020_matches`.`g`.`player1`) and (`20101020_matches`.`g`.`type` = 'team'))) join `20101020_matches`.`player` `p` where (`20101020_matches`.`p`.`id` = coalesce(`20101020_matches`.`pt`.`player`,`20101020_matches`.`g`.`player1`)) group by `20101020_matches`.`g`.`id` limit 50

We see that the query returns the lists of players correctly both for single-player games and team ones (like the one you can see at Game 38). The query works in the following way:

• For each record from game, it determines whether the game is single player or a team match.
• If the game is multiplayer, it joins the player_team table. The query is written so that the game type is a part of a LEFT JOIN condition which can be short-circuited by the optimizer. This means that if a game is a single player game, no actual lookup is performed against player_team: the optimizer will just optimize away this step, knowing for sure that it just needs to return a NULL.
• Finally, the player table is joined, using CASE. The case will evaluate to either player_team.player or to game.player1 (depending on the game type).

Theoretically, it could be replaced with a mere COALESCE(player_team.player, game.player1); however, if the game type were team but the team itself were empty, this expression would incorrectly evaluate to game.player1, not regarding the game type. So it's better to leave it as is.

Now, we have an aggregate of the players' names from the one side. How do we make the same for two sides?

Since we need to calculate aggregates for two different columns, it's better to replace the JOINs with the correlated subqueries. However, there is a little problem.

Normally, a correlated subquery just replaces the ON condition with a WHERE condition. But this is with a plain JOIN, and we here have a LEFT JOIN. We cannot just replace it with WHERE: it won't match anything.

Unfortunately, MySQL has a very limited ability of correlating the subqueries. For instance, a correlated value cannot be nested more than one level deep, neither can is be used in an ON clause of a join. That's why we will need to make one extra join in our subqueries.

To rewrite the aggregate query as subqueries, we will need to join game to itselft in the subqueries and use the values of a joined table instead of the correlated values:

SELECT  g.id, g.name,
(
SELECT  GROUP_CONCAT(p.name SEPARATOR ', ') AS players
FROM    game gi
LEFT JOIN
player_team pt
ON      gi.type = 'team'
AND pt.team = gi.player1
JOIN    player p
ON      p.id = CASE gi.type WHEN 'player' THEN gi.player1 WHEN 'team' THEN pt.player END
WHERE   gi.id = g.id
),
(
SELECT  GROUP_CONCAT(p.name SEPARATOR ', ') AS players
FROM    game gi
LEFT JOIN
player_team pt
ON      gi.type = 'team'
AND pt.team = gi.player2
JOIN    player p
ON      p.id = CASE gi.type WHEN 'player' THEN gi.player2 WHEN 'team' THEN pt.player END
WHERE   gi.id = g.id
)
FROM    game g
ORDER BY
id
LIMIT 50

Field or reference '20101020_matches.g.id' of SELECT #2 was resolved in SELECT #1
Field or reference '20101020_matches.g.id' of SELECT #3 was resolved in SELECT #1
select `20101020_matches`.`g`.`id` AS `id`,`20101020_matches`.`g`.`name` AS `name`,(select group_concat(`20101020_matches`.`p`.`name` separator ', ') AS `players` from `20101020_matches`.`game` `gi` left join `20101020_matches`.`player_team` `pt` on(((`20101020_matches`.`pt`.`team` = `20101020_matches`.`gi`.`player1`) and (`20101020_matches`.`gi`.`type` = 'team'))) join `20101020_matches`.`player` `p` where ((`20101020_matches`.`gi`.`id` = `20101020_matches`.`g`.`id`) and (`20101020_matches`.`p`.`id` = (case `20101020_matches`.`gi`.`type` when 'player' then `20101020_matches`.`gi`.`player1` when 'team' then `20101020_matches`.`pt`.`player` end)))) AS `(
        SELECT  GROUP_CONCAT(p.name SEPARATOR ', ') AS players
        FROM    game gi
        LEFT JOIN  
                player_team pt
        ON      gi.type = 'team'
                AND pt.team = gi.player1
        JOIN    player p
        ON      `,(select group_concat(`20101020_matches`.`p`.`name` separator ', ') AS `players` from `20101020_matches`.`game` `gi` left join `20101020_matches`.`player_team` `pt` on(((`20101020_matches`.`pt`.`team` = `20101020_matches`.`gi`.`player2`) and (`20101020_matches`.`gi`.`type` = 'team'))) join `20101020_matches`.`player` `p` where ((`20101020_matches`.`gi`.`id` = `20101020_matches`.`g`.`id`) and (`20101020_matches`.`p`.`id` = (case `20101020_matches`.`gi`.`type` when 'player' then `20101020_matches`.`gi`.`player2` when 'team' then `20101020_matches`.`pt`.`player` end)))) AS `(
        SELECT  GROUP_CONCAT(p.name SEPARATOR ', ') AS players
        FROM    game gi
        LEFT JOIN
                player_team pt
        ON      gi.type = 'team'
                AND pt.team = gi.player2
        JOIN    player p
        ON      p.` from `20101020_matches`.`game` `g` order by `20101020_matches`.`g`.`id` limit 50

Instead of using correlated values g.type and g.player*, we join another instance of game (aliased as gi) on g.id and use its fields in the join instead.

This of course adds some overhead to the query, however, the PRIMARY KEY join on an already cached record is quite fast.

Let's run two queries that select player lists for all games and compare the execution times.

First, the grouping query:

SELECT  SUM(LENGTH(players))
FROM    (
SELECT  g.id, g.name, GROUP_CONCAT(p.name SEPARATOR ', ') AS players
FROM    game g
LEFT JOIN
player_team pt
ON      g.type = 'team'
AND pt.team = g.player1
JOIN    player p
ON      p.id = CASE g.type WHEN 'player' THEN g.player1 WHEN 'team' THEN pt.player END
GROUP BY
g.id
ORDER BY
NULL
) q

Show query details

select sum(length(`q`.`players`)) AS `SUM(LENGTH(players))` from (select `20101020_matches`.`g`.`id` AS `id`,`20101020_matches`.`g`.`name` AS `name`,group_concat(`20101020_matches`.`p`.`name` separator ', ') AS `players` from `20101020_matches`.`game` `g` left join `20101020_matches`.`player_team` `pt` on(((`20101020_matches`.`pt`.`team` = `20101020_matches`.`g`.`player1`) and (`20101020_matches`.`g`.`type` = 'team'))) join `20101020_matches`.`player` `p` where (`20101020_matches`.`p`.`id` = (case `20101020_matches`.`g`.`type` when 'player' then `20101020_matches`.`g`.`player1` when 'team' then `20101020_matches`.`pt`.`player` end)) group by `20101020_matches`.`g`.`id` order by NULL) `q`

And the subqueries:

SELECT  g.id, g.name,
SUM(LENGTH(
(
SELECT  GROUP_CONCAT(p.name SEPARATOR ', ') AS players
FROM    game gi
LEFT JOIN
player_team pt
ON      gi.type = 'team'
AND pt.team = gi.player1
JOIN    player p
ON      p.id = CASE gi.type WHEN 'player' THEN gi.player1 WHEN 'team' THEN pt.player END
WHERE   gi.id = g.id
)
)) AS len1,
SUM(LENGTH(
(
SELECT  GROUP_CONCAT(p.name SEPARATOR ', ') AS players
FROM    game gi
LEFT JOIN
player_team pt
ON      gi.type = 'team'
AND pt.team = gi.player2
JOIN    player p
ON      p.id = CASE gi.type WHEN 'player' THEN gi.player2 WHEN 'team' THEN pt.player END
WHERE   gi.id = g.id
)
)) AS len2
FROM    game g

Show query details

Field or reference '20101020_matches.g.id' of SELECT #2 was resolved in SELECT #1
Field or reference '20101020_matches.g.id' of SELECT #3 was resolved in SELECT #1
select `20101020_matches`.`g`.`id` AS `id`,`20101020_matches`.`g`.`name` AS `name`,sum(length((select group_concat(`20101020_matches`.`p`.`name` separator ', ') AS `players` from `20101020_matches`.`game` `gi` left join `20101020_matches`.`player_team` `pt` on(((`20101020_matches`.`pt`.`team` = `20101020_matches`.`gi`.`player1`) and (`20101020_matches`.`gi`.`type` = 'team'))) join `20101020_matches`.`player` `p` where ((`20101020_matches`.`gi`.`id` = `20101020_matches`.`g`.`id`) and (`20101020_matches`.`p`.`id` = (case `20101020_matches`.`gi`.`type` when 'player' then `20101020_matches`.`gi`.`player1` when 'team' then `20101020_matches`.`pt`.`player` end)))))) AS `len1`,sum(length((select group_concat(`20101020_matches`.`p`.`name` separator ', ') AS `players` from `20101020_matches`.`game` `gi` left join `20101020_matches`.`player_team` `pt` on(((`20101020_matches`.`pt`.`team` = `20101020_matches`.`gi`.`player2`) and (`20101020_matches`.`gi`.`type` = 'team'))) join `20101020_matches`.`player` `p` where ((`20101020_matches`.`gi`.`id` = `20101020_matches`.`g`.`id`) and (`20101020_matches`.`p`.`id` = (case `20101020_matches`.`gi`.`type` when 'player' then `20101020_matches`.`gi`.`player2` when 'team' then `20101020_matches`.`pt`.`player` end)))))) AS `len2` from `20101020_matches`.`game` `g`

The second query is only 40% longer, but it parses and returns twice as much data.

That means that it's more efficient to run a single query to get both lists of players than to run a grouping query twice.

Hope that helps.

I'm always glad to answer the questions regarding database queries.

Ask me a question