こっぱみぢんこ

連続する範囲と欠落する範囲

寒かったり暖かかったりと気温は不安定だが、それでもやっぱり春なんだよな。外には、気配なんて小さなものではなく、もうはっきりと主張しているレベルのいかにもな春がそこここに。

家の前の桜。昨日見た時は3分咲ぐらいだったのに、今日見たらもうほぼ満開だった。

隣の家の庭（？）に土筆。いっぱい生えている。

樹液が染み出しているのだが、その色がちょっと凄い。ヌラヌラと濡れ光っていて、胃カメラで見た胃の入り口にも似ている。

連続する範囲

先日の順序に繋がるようなそうでもないような話なのだが、連番の順序とこれに対応付けられる値を登録して、その後にいくつか削除されて歯抜けになる場合がある。例えば社員マスター。社員番号は、単純な連番や、上位2桁が入社年度で下位5桁が連番なんてパターンが多いだろう。これに名前や所属がくっついて登録され、辞職や解雇で欠番となる。

そんな状況で、連続する範囲をSQLで抽出するにはどうすればいいのだろうか。連続する範囲の抽出とは、仮にデータが

		1, 2, 3, 6, 8, 9
	

であるなら

		1〜3, 6, 8〜9
	

と取り出すこと。

昨日、仕事中にふと疑問に思い、そのままずっと気になって、仕事の合間に気分転換を兼ねて考えても良い解答が思いつかず、結局帰りのバスの中で解答に辿り着いたのだった。その解答がこれ。


select min( user_no )
     , max( user_no )
from ( select user_no
            , user_no - row_number() over ( order by user_no ) usub
       from users )
group by usub
order by min( user_no )

ここで、対象テーブルを社員マスタ（users）とし、そこに数値形式で社員番号（user_no）が登録されているものとしている。

社員マスタの社員番号の登録値が上記の例なら、このSQLによって

が取得できる。

ポイントは、社員番号から社員番号昇順に振った連番を引くところ。上の例で実際にやってみると、

user_no	連番	引算
1	1	0
2	2	0
3	3	0
6	4	2
8	5	3
9	6	3

と、連続している間は引き算の結果（usub）が同じ値になるのだな。なので、これで group by して min と max を取り出すことで、求める結果が得られるのだ。

結果の書式まで求めるなら、若干複雑になるが


select case when min_no = max_no
            then min_no
            else min_no || '〜' || max_no
       end
from ( select to_char( min( user_no ) ) min_no
            , to_char( max( user_no ) ) max_no
       from ( select user_no
                   , user_no - row_number() over ( order by user_no ) usub
              from users )
       group by usub
       order by min( user_no ) )

とすれば、文字列として以下が得られる。

これ、バスの中で気付いた時に「俺って冴えてる！」と一人ニヤニヤしていたのだが、家に帰って検索してみたら、同じようなことを同じアイデアでやっている人が既にいたのだった。まあ、そんなもんだよな。

欠落する範囲

さて、連続する範囲が取り出せると、それを元に欠落した範囲も取り出せる。歯抜けの比喩を使うなら、抜けた歯の方だな。

具体的には、連番範囲として取得した各レコードに1からの連番を振った集合と、同じく連番を振るが開始値を2からとする集合とを、この連番で内部結合する。上の例をそのまま使うと、こんな風になる。

集合1			集合2
min	max	連番	min	max	連番
1	3	1
6	6	2	1	3	2
8	9	3	6	6	3
			8	9	4

内部結合すると黄色のレコードが返ってくるので、ここから欠番範囲を以下で得ることができる。

欠番範囲の開始値 = 集合2側のmaxの値 + 1
欠番範囲の終了値 = 集合1側のminの値 - 1

SQLは以下の通り。


with s0 as ( select min( user_no ) min_no
                  , max( user_no ) max_no
                  , row_number() over ( order by min( user_no ) ) ugrp
             from ( select user_no
                         , user_no - row_number() over ( order by user_no ) usub
                    from users )
             group by usub )
select s2.max_no + 1
     , s1.min_no - 1
from ( select min_no, max_no, ugrp          from s0 ) s1
     inner join
     ( select min_no, max_no, ugrp + 1 ugrp from s0 ) s2
     on s1.ugrp = s2.ugrp
order by s1.min_no

これを実行すると、以下が得られる。

		4, 5

		7, 7

一応できたから良いかと思ったのだが、最初の連続する範囲を取り出すのに比べて複雑なのが、ちょっとモヤモヤするんだよな。まあ、やってることが

連続する範囲を取り出す
その組み合わせで欠落する範囲を取り出す

という2段階なので、どうしたって複雑にはなるのだが。

で、2段階ではなくいきなり欠落範囲を求められないかと考えながら例の数を眺めていて、定義に立ち返ればうまくいきそうな気がしてきた。というのも、欠落とはつまり

自分の次に大きい値が自分+1ではない

ってことなんだよな。これは

自分よりも大きい値の集合の最小値が自分+1ではない

となって、なんだかもうSQLっぽいではないか。

例で実際にやってみると、

user_no	より大きい値の最小値
1	2
2	3
3	6
6	8
8	9
9	-

黄色の部分が欠落が発生しているところ。うん、いい感じ。

実際の欠落範囲は

自分+1 〜自分より大きい大きい値の最小値-1

となることに注意して、これをSQLにすると、


select s1.user_no + 1
     , min( s2.user_no ) - 1
from users s1
     inner join users s2
     on s1.user_no < s2.user_no
group by s1.user_no
having s1.user_no + 1 != min( s2.user_no )
order by s1.user_no

結構すっきりしたな。

とりあえず2つ考えてみたが、どっちも、現在登録されている最小値よりも小さい欠番と、現在登録されている最大値よりも大きい欠番が取れないのが欠点なんだよな。

それらも取得したい場合はどうすれば良いんだろう。最小の欠番と最大の欠番を含むように母集合の値の範囲を設定してやれば良いのか。取得する考え方から、具体的には、想定される最小値より1少ないダミーレコードと、想定する最大値より1多いダミーレコードをunionすればいいのだな。

後の例で適用するなら、


with s0 as ( select user_no from users
             union
             select 0 user_no from dual
             union
             select 1000 user_no from dual )
select s1.user_no + 1
     , min( s2.user_no ) - 1
from s0 s1
     inner join s0 s2
     on s1.user_no < s2.user_no
group by s1.user_no
having s1.user_no + 1 != min( s2.user_no )
order by s1.user_no

最小値と最大値は場合によって違うので、ダミーの値はサンプルとしてとりあえず0と1000を追加してみた。なんだか微妙にダサくなった気がするが、実行すると

と、大きい方の欠番範囲が追加で返ってくる。

もういいような気もするのだが、さらに未練たらしくコードを眺めていて、欠落する範囲を連続する範囲に置き換えればいいことに気がついた。

想定される連番範囲の連番と外部結合してnullを抜き出せば、欠落した番号だけの集合が得られる。これに対して、連続する範囲を取得する方法を適用してやれば良いのではないか。


select min( user_no )
     , max( user_no )
from ( select s1.user_no
            , s1.user_no - row_number() over ( order by s1.user_no ) usub
       from ( select level user_no from dual connect by level < 999 ) s1
            left outer join
            users s2
            on s1.user_no = s2.user_no
       where s2.user_no is null )
group by usub
order by min( seq )

うーん… 何か+1 なんて加工も無いし、最小値と最大値のためのダミーレコードも不要で、その点ではすっきりしている。しかし、値の範囲のための連番を作り出す部分や、レコードの連番を引く意味がぱっと見では判らないんじゃないだろうか。判りやすさなら前の方が良いような気がするな。

ついでなので実行計画を見てみたら、前のSQLはダミーレコードのためにwithを使い、これをまた結合しているので TABLE ACCESS FULL が3回発生していた。後のSQLは1回なので、性能的には後の方が良いのか。データが少なければどうでもいいけど、大量にある中から検索する場合、この差はきっと圧倒的だろう。

当然ながら、連番が単純な連番じゃなくて、何かしらの構造の中に連番が入っている場合は、それなりの工夫が必要になる。また、最大値を動的に取得する必要がある場合は、連番生成部分を工夫する必要があるだろう。

あとは使う機会があるかどうかだが、今更こんなことを考えているってことから察せられる通り、俺にはこれまで欠落した範囲を取得する必要が生じたことが無いんだよな。

+

ところで「歯抜け」って普通に使ってるけど、そのうち使えなくなったりするんだろうか。歯の治療中の人や入れ歯の人を傷つけるとかで。まあ、禿げが使われている間は大丈夫か。

そうそう、意外に知られていないけど、チビとハゲは漢字が同じなんだよな。禿びと禿げ。送り仮名が無いと文脈で判断するしか無いのだが、その判断を迫られる文脈って、ねえ。

いずれも「擦り減る」という現象の現れ方の違いで、擦り減って短くなるのが「禿びる」で、擦り減って表面が失われるのが「禿げる」なのだが、しかしこれが人に向けられる場合、禿げはともかく、禿びは擦り減る前にそもそも伸びて無いんだよな。

2015 03 28

連続する範囲と欠落する範囲

連続する範囲

欠落する範囲

+