Mysql:AutoIncrementIdを推測するワザ #PHP

概要

バイナリサーチでAIDを推測するだけ

ありがちな遅いクエリ

SELECT *
FROM `sugoi_table`
WHERE `create_time` >= '2019-10-01'
(48,126 合計, クエリの実行時間 28.3798 秒)

Explainの結果

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	sugoi_table	range	PRIMARY	PRIMARY	4	NULL	32715643	Using where

rows(走査範囲)が多すぎる!!

MySQLは「1番目のレコードから全てのレコードのcreate_timeが10/1より大きいか？」を判断するので大変遅い
本番write用のDBにこんなもん流した日にはしばらくサービスが反応しなくなる
せめて迂闊なselectを投げる前にindexが効いてるか確認しよう・・・

シンプルな解決方法

AIDで走査範囲を絞る

SELECT *
FROM `sugoi_table`
WHERE `user_id` >=50000000
AND `create_time` >= '2019-10-01'
(48,153 合計, クエリの実行時間 0.0621 秒)

早くなった

Explainの結果

id	select_type	table	type	possible_keys	key	key_len	ref	rows	Extra
1	SIMPLE	sugoi_table	range	PRIMARY	PRIMARY	4	NULL	500844	Using where

rowsが3200万→50万に減ったのが要因

適当に作った調査クエリを流して「結果が返ってこない・・・」とかなりそうな時は事前に使おう

だがしかし、それっぽいAIDを調べるのが面倒くさい！！

create_timeで二分探索(バイナリサーチ)すればいい

アルゴリズムを勉強するなら二分探索から始めよう！『なっとく！アルゴリズム』より

文字が読みたくない人向け

全体の中心のデータを見て「大きい」なら後ろ、「小さい」なら前を繰り返して検索する方法
計算量はO(log2 n)だそうな

実装してみる

/**
 * 指定テーブルの指定日付のAIDを推測する
 */
public static function guessAid( $tableName, $targetKey, $targetDateTime) {

    //まず最大のAIDを取得する
    $maxId = self::_getMaxAid($tableName, $targetKey);

    $low    = 1;
    $high   = $maxId;
    $loopCnt = 0;
    $guess  = 0;

    while ( $low <= $high ) {
        $loopCnt++;
        $mid = (int)(($high + $low) / 2); //中央値を作成 floatにならないように
        $sql = "SELECT create_time FROM {$tableName} WHERE {$targetKey} >= {$mid} LIMIT 1";
        $tmpData = Db::query($sql);
        if ( empty($tmpData)) {
            //データが無い時の処理(投げやり);
            break;
        }
        if (strtotime($tmpData['create_time']) < strtotime($targetDateTime)) {
            //時間が小さい時に推測候補を保持しておく
            //逆条件の時にループが終わると指定時間ちょい後のAIDになってしまう場合がある為
            $guess = $low; 
            $low = $mid + 1;
        } else {
            $high = $mid - 1;
        }
        //データが消されている可能性も考慮して一定ループで抜ける
        if ( $loopCnt >= 50 ) {
            break;
        }
    }
    //echo("だいたいこの辺じゃろ");
    $id = $guess;
    return $id;
}

/**
 * テーブルのMAX_AIDをとる
 */
private static function _getMaxAid( $tableName="", $targetKey="") {
    $sql = "SELECT MAX({$targetKey}) FROM {$tableName}";
    $data = Db::query($sql);
    return $data;
}