Mysql:AutoIncrementIdを推測するワザ

概要

バイナリサーチで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;
}