EXPLAIN EXTENDED

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

CREATE TABLE t_set (
        ts INT NOT NULL,
        code CHAR(1) NOT NULL,
        PRIMARY KEY pk_set_ts_code (ts, code)
) ENGINE=InnoDB DEFAULT CHARSET=UTF8;

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(10000);
COMMIT;

INSERT
INTO    t_set
SELECT  ft.id * 29 + RAND(20090819) * 10, CHAR(64 + fs.id)
FROM    filler ft
JOIN    (
        SELECT  id
        FROM    filler
        ORDER BY
                id
        LIMIT 25
        ) fs
ON      fs.id <= 25 - ((ft.id - 1) div 400);
&#91;/sourcecode&#93;
</div>

This table contains <strong>130,000</strong> records: <strong>10,000</strong> sets having from <strong>26</strong> to <strong>1</strong> records in each.

The timestamps are deliberately made not consecutive.

To find out the list of timestamps, we issue the following query:


SELECT  DISTINCT ts
FROM    t_set

See the results and the plan

, which uses INDEX FOR GROUP-BY and completes in but 126 milliseconds.

However, it we try to select the previous value of timestamp along with each timestamp using a subquery with MAX:

SELECT  (
        SELECT  MAX(ts)
        FROM    t_set si
        WHERE   si.ts < so.ts
        ) AS pts,
        ts
FROM    (
        SELECT  DISTINCT ts
        FROM    t_set
        LIMIT 100
        ) so
&#91;/sourcecode&#93;

, we will get the following results:

<a href="#" onclick="xcollapse('X7849');return false;"><strong>See the results and the plan</strong></a>
<br />
<div id="X7849" style="display: none; ">
<div class="terminal">
<table class="terminal">
<tr>
<th>pts</th><th>ts</th></tr>
<tr><td class="integer"></td><td class="integer">36</td></tr>
<tr><td class="integer">36</td><td class="integer">64</td></tr>
<tr><td class="integer">64</td><td class="integer">88</td></tr>
<tr class="break"><td colspan="100"></td></tr>
<tr><td class="integer">289916</td><td class="integer">289950</td></tr>
<tr><td class="integer">289950</td><td class="integer">289974</td></tr>
<tr><td class="integer">289974</td><td class="integer">290008</td></tr>
<tr class="statusbar"><td colspan="100">10000 rows fetched in 0.0021s (796.8578s)</td></tr>
</table>
</div>

<div class="terminal">
<table class="terminal">
<tr>
<th>id</th><th>select_type</th><th>table</th><th>type</th><th>possible_keys</th><th>key</th><th>key_len</th><th>ref</th><th>rows</th><th>filtered</th><th>Extra</th></tr>
<tr><td class="bigint">1</td><td class="varchar">PRIMARY</td><td class="varchar">&lt;derived3&gt;</td><td class="varchar">ALL</td><td class="varchar"></td><td class="varchar"></td><td class="varchar"></td><td class="varchar"></td><td class="bigint">100</td><td class="double">100.00</td><td class="varchar"></td></tr>
<tr><td class="bigint">3</td><td class="varchar">DERIVED</td><td class="varchar">t_set</td><td class="varchar">index</td><td class="varchar"></td><td class="varchar">PRIMARY</td><td class="varchar">7</td><td class="varchar"></td><td class="bigint">133167</td><td class="double">16.67</td><td class="varchar">Using index; Using temporary</td></tr>
<tr><td class="bigint">2</td><td class="varchar">DEPENDENT SUBQUERY</td><td class="varchar">si</td><td class="varchar">index</td><td class="varchar">PRIMARY</td><td class="varchar">PRIMARY</td><td class="varchar">7</td><td class="varchar"></td><td class="bigint">133167</td><td class="double">100.00</td><td class="varchar">Using where; Using index</td></tr>
</table>
</div>
</div>

We see <code>USING WHERE</code> in the query plan for a subquery. This is because <strong>MySQL</strong> cannot use <strong>RANGE</strong> access method in subqueries.

This leads to rescanning the <em>whole</em> table for each distinct value of <code>ts</code>, which takes <strong>700 seconds</strong>.

To work around this, we just need to use a session variable to store the previous value of the <code>ts</code>:


SELECT  @r AS pts,
        @r := ts AS ts
FROM    (
        SELECT  ts
        FROM    (
                SELECT  @r := NULL
                ) vars,
                (
                SELECT  DISTINCT ts
                FROM    t_set
                ) soo
        ) so

See the results and the plan

This is very fast, just 140 milliseconds.

Fortunately, MySQL does use REF access (as opposed to RANGE access) in subqueries, that's why we can use the following query to obtain the result we're after:

SELECT  ts,
        (
        SELECT  GROUP_CONCAT(code)
        FROM    t_set si
        WHERE   si.ts =
                (
                SELECT  sp.ts
                FROM    t_set sp
                WHERE   sp.ts = so.pts
                ORDER BY
                        sp.ts DESC
                LIMIT 1
                )
                AND NOT EXISTS
                (
                SELECT  NULL
                FROM    t_set sn
                WHERE   sn.ts = so.ts
                        AND sn.code = si.code
                )
        ) AS diff
FROM    (
        SELECT  @r AS pts,
                @r := ts AS ts
        FROM    (
                SELECT  @r := NULL
                ) vars,
                (
                SELECT  DISTINCT ts
                FROM    t_set
                ) soo
        ) so
HAVING  diff IS NOT NULL

See the results and the plan

, which completed in only 3.75 seconds.