次のようなテーブルがあったとします。1 レコードが a～b の範囲を示しています。終端の端点は含みません。例えば 3～6 なら 3,4,5 を含む範囲です。
create table t ( id int not null primary key auto_increment, a int not null, b int not null ); insert into t values (null, 3, 6); insert into t values (null, 10, 14); insert into t values (null, 13, 17); insert into t values (null, 16, 20); insert into t values (null, 25, 28); insert into t values (null, 28, 31); insert into t values (null, 31, 34); insert into t values (null, 34, 36); insert into t values (null, 40, 60); insert into t values (null, 44, 56);
このテーブルから、指定した任意の範囲 @a～@b の区間に隙間があるかを調べます。例えば↑のデータの場合、10～20 の区間は全部埋まっています、20～30 の区間には隙間があります。
案：ビットフィールド
範囲内の各ポイントに1ビットを割り当てます。次のようにです。
0 1 1 10 2 100 3 1000 4 10000 5 100000 6 1000000 7 10000000 8 100000000
範囲はその中のすべてのポイントを論理和したものになります。例えば 3～6 の範囲は 111000 = 56 です。
テーブルのすべてのレコードの範囲を論理和すれば埋まっている範囲のビットフィールドが得られます。そのビットを反転し、目的の範囲と論理積して、非ゼロとなるビットが隙間です。ので、結果が非ゼロかどうかで隙間があるかどうか判断できます。
3～6 のような範囲の値からビットフィールドへは次の式で変換できます。
set @a=3, @b=6; select (-1 << @a) & ~(-1 << @b) as x; /* +------+ | x | +------+ | 56 | +------+ */
レコードごとにビットフィールドを計算します。
select *, lpad(bin( (-1 << a) & ~(-1 << b) ), 64, '0') as x from t; /* +----+----+----+------------------------------------------------------------------+ | id | a | b | x | +----+----+----+------------------------------------------------------------------+ | 1 | 3 | 6 | 0000000000000000000000000000000000000000000000000000000000111000 | | 2 | 10 | 14 | 0000000000000000000000000000000000000000000000000011110000000000 | | 3 | 13 | 17 | 0000000000000000000000000000000000000000000000011110000000000000 | | 4 | 16 | 20 | 0000000000000000000000000000000000000000000011110000000000000000 | | 5 | 25 | 28 | 0000000000000000000000000000000000001110000000000000000000000000 | | 6 | 28 | 31 | 0000000000000000000000000000000001110000000000000000000000000000 | | 7 | 31 | 34 | 0000000000000000000000000000001110000000000000000000000000000000 | | 8 | 34 | 36 | 0000000000000000000000000000110000000000000000000000000000000000 | | 9 | 40 | 60 | 0000111111111111111111110000000000000000000000000000000000000000 | | 10 | 44 | 56 | 0000000011111111111100000000000000000000000000000000000000000000 | +----+----+----+------------------------------------------------------------------+ */
集計関数 BIT_OR ですべてのレコードの論理和を求めます。
select lpad(bin(bit_or( (-1 << a) & ~(-1 << b) )), 64, '0') as x from t; /* +------------------------------------------------------------------+ | x | +------------------------------------------------------------------+ | 0000111111111111111111110000111111111110000011111111110000111000 | +------------------------------------------------------------------+ */
↑の結果の補数と目的の範囲とを論理積します。
set @a=10, @b=30; select lpad(bin( ~bit_or( (-1 << a) & ~(-1 << b) ) & ( (-1 << @a) & ~(-1 << @b) ) ), 64, '0') as x from t; /* +------------------------------------------------------------------+ | x | +------------------------------------------------------------------+ | 0000000000000000000000000000000000000001111100000000000000000000 | +------------------------------------------------------------------+ */
最後の結果は、20～25 が隙間、ということを意味しています。
この方法は後述の他の方法と比べるとテーブルを 1 回しか走査しないため実行計画もシンプルでパフォーマンスも良いです。ただし値の範囲が 0～63 までしか扱えません。それを超える値だと複数に分割するなどが必要となるため、値の取りうる範囲が大きくなると現実的ではなくなります。例えば1日の中で10分単位で指定できる予約サイト（ありがち）とかだと 24*60/10 = 144 なのでオーバーします。30分単位なら 24*60/30 = 48 なのでカバーできます。この種のシステムの要件はなるべく30分単位にしたいところです（違
案：連続する範囲の左端と右端を計算
隣接する範囲や重なる範囲を結合し、隣接や重なりの無い範囲の組に変換することを考えてみます。
次の条件で他の範囲と隣接や重なっていない左端が得られます。
select t.a from t inner join t as s group by t.a having sum(t.a > s.a and t.a <= s.b) = 0 order by t.a; /* +----+ | a | +----+ | 3 | | 10 | | 25 | | 40 | +----+ */
同様に右端も次のように得られます。
select t.b from t inner join t as s group by t.b having sum(t.b < s.b and t.b >= s.a) = 0 order by t.b; /* +----+ | b | +----+ | 6 | | 20 | | 36 | | 60 | +----+ */
この2つの結果を横につなげれば、隣接や重なりの無い範囲の組が得られます。
select a, min(b) as b from ( select t.a from t inner join t as s group by t.a having sum(t.a > s.a and t.a <= s.b) = 0 ) aa join ( select t.b from t inner join t as s group by t.b having sum(t.b < s.b and t.b >= s.a) = 0 ) bb where a <= b group by a; /* +----+------+ | a | b | +----+------+ | 3 | 6 | | 10 | 20 | | 25 | 36 | | 40 | 60 | +----+------+ */
これらの範囲の組の中に目的の範囲 @a～@b を完全に含むものがあるなら、隙間はないと判断できます。
set @a=10,@b=20; select a, min(b) as b from ( select t.a from t inner join t as s group by t.a having sum(t.a > s.a and t.a <= s.b) = 0 ) aa join ( select t.b from t inner join t as s group by t.b having sum(t.b < s.b and t.b >= s.a) = 0 ) bb where a <= b group by a having a <= @a and b >= @b; /* +----+------+ | a | b | +----+------+ | 10 | 20 | +----+------+ */
LEFT JOIN でも似たようなことができます。
select a, min(b) as b from ( select t.a from t left join t as s on t.a > s.a and t.a <= s.b where s.a is null ) aa join ( select t.b from t left join t as s on t.b < s.b and t.b >= s.a where s.b is null ) bb where a <= b group by a; /* +----+------+ | a | b | +----+------+ | 3 | 6 | | 10 | 20 | | 25 | 36 | | 40 | 60 | +----+------+ */
案：すべての範囲が隣接または重なるか計算
目的の範囲 @a～@b と重なるすべてのレコードについて、下記が成り立つならその範囲に隙間はありません。
- 左端 a が他のレコードと隣接または含まれる、または、@a より左
- 右端 b が他のレコードと隣接または含まれる、または、@b より右
テーブルを自己結合し、すべての組み合わせから条件を判定します。aa や bb が 1 となる組み合わせが条件を満たしています。
set @a=10,@b=20; select *, (t.a > s.a and t.a <= s.b or t.a <= @a) as aa, (t.b < s.b and t.b >= s.a or t.b >= @b) as bb from t join t as s where t.a < @b and t.b > @a and s.a < @b and s.b > @a order by t.a, t.b, s.a, s.b; /* +----+----+----+----+----+----+------+------+ | id | a | b | id | a | b | aa | bb | +----+----+----+----+----+----+------+------+ | 2 | 10 | 14 | 2 | 10 | 14 | 1 | 0 | | 2 | 10 | 14 | 3 | 13 | 17 | 1 | 1 | | 2 | 10 | 14 | 4 | 16 | 20 | 1 | 0 | | 3 | 13 | 17 | 2 | 10 | 14 | 1 | 0 | | 3 | 13 | 17 | 3 | 13 | 17 | 0 | 0 | | 3 | 13 | 17 | 4 | 16 | 20 | 0 | 1 | | 4 | 16 | 20 | 2 | 10 | 14 | 0 | 1 | | 4 | 16 | 20 | 3 | 13 | 17 | 1 | 1 | | 4 | 16 | 20 | 4 | 16 | 20 | 0 | 1 | +----+----+----+----+----+----+------+------+ */
すべての t.id について aa が 1 である組み合わせと bb が 1 である組み合わせがそれぞれ 1 つ以上存在するかを判定します。count(distinct) ですべての id の数と、左端と右端がそれぞれ条件を満たす id の数が一致するかどうかで判定します。
set @a=10,@b=20; select count(distinct t.id) as cnt_id, count(distinct if (t.a > s.a and t.a <= s.b or t.a <= @a, t.id, null)) as cnt_aa, count(distinct if (t.b < s.b and t.b >= s.a or t.b >= @b, t.id, null)) as cnt_bb from t join t as s where t.a < @b and t.b > @a and s.a < @b and s.b > @a having cnt_id = cnt_aa and cnt_id = cnt_bb and cnt_id > 0; /* +--------+--------+--------+ | cnt_id | cnt_aa | cnt_bb | +--------+--------+--------+ | 3 | 3 | 3 | +--------+--------+--------+ */
テストします。1 1 1 のような結果が表示されている行が隙間の無い範囲です。
cat <<'EOS'>z.sql select count(distinct t.id) as cnt_id, count(distinct if (t.a > s.a and t.a <= s.b or t.a <= @a, t.id, null)) as cnt_aa, count(distinct if (t.b < s.b and t.b >= s.a or t.b >= @b, t.id, null)) as cnt_bb from t join t as s where t.a < @b and t.b > @a and s.a < @b and s.b > @a having cnt_id = cnt_aa and cnt_id = cnt_bb and cnt_id > 0 EOS while read -r x; do echo -n "$x " echo $({ echo "$x"; cat z.sql; } | mysql test -N) done <<'EOS' set @a = 3, @b = 6; set @a = 2, @b = 6; set @a = 3, @b = 7; set @a = 10, @b = 20; set @a = 9, @b = 20; set @a = 10, @b = 21; set @a = 25, @b = 36; set @a = 24, @b = 36; set @a = 25, @b = 37; set @a = 40, @b = 60; set @a = 39, @b = 60; set @a = 40, @b = 61; EOS #=> set @a = 3, @b = 6; 1 1 1 #=> set @a = 2, @b = 6; #=> set @a = 3, @b = 7; #=> set @a = 10, @b = 20; 3 3 3 #=> set @a = 9, @b = 20; #=> set @a = 10, @b = 21; #=> set @a = 25, @b = 36; 4 4 4 #=> set @a = 24, @b = 36; #=> set @a = 25, @b = 37; #=> set @a = 40, @b = 60; 2 2 2 #=> set @a = 39, @b = 60; #=> set @a = 40, @b = 61;
さいごに
なるべくぱっと見でなにやってるかわからない SQL は書きたくないものです。
