旅人算メソッドの解説

昔、US-OTNに投稿した
Tabibitosan method tutorial by Aketi Jyuuzou
https://community.oracle.com/thread/1007478
を日本語に翻訳しつつ、全面リニューアルしてみました。

01 旅人算とは？

受験算数で有名な問題の1つです。

英進館CM：「歩く男」YouTube
https://www.youtube.com/watch?v=6I58kZybVUU

旅人算 - 算数の教え上手 | 学びの場.com
https://www.manabinoba.com/math/757.html

Hello School 算数 旅人算
https://www.hello-school.net/sansub1801.html

旅人算―中学入試問題をわかりやすくマンガで攻略
https://www.amazon.co.jp/dp/4895243702

02 旅人算メソッドとは？

SQLで、何らかの条件で連続した行を、集約したいときに使う、SQLおよび考え方です。
受験算数の旅人算での脳内の旅人のイメージがベースになってます。

03 数値の連続した行を集約

create table Ex1 (NumVal primary key) as
select  1 from dual union
select  2 from dual union
select  3 from dual union
select  5 from dual union
select  6 from dual union
select  7 from dual union
select 10 from dual union
select 11 from dual union
select 12 from dual union
select 20 from dual union
select 21 from dual;

数値の連続した行を集約します。

select min(NumVal),max(NumVal),count(*)
from (select NumVal,
      NumVal - Row_Number() over(order by NumVal)
      as DisTance
      from Ex1)
group by DisTance
order by min(NumVal);

Min(NumVal)  Max(NumVal)  count(*)
-----------  -----------  --------
          1            3         3
          5            7         3
         10           12         3
         20           21         2

上記のSQLでは、2人の旅人(XとA)をイメージしてます。
旅人Xは、必ず1進みます。 Row_Number() over(order by NumVal)
旅人Aは、必ず1以上進みます。 NumVal

そして、旅人Xと旅人Aとの距離でグループ化してます。group by DisTance

04 日付の連続した行を集約

create table Ex2 (DateVal primary key) as
select date '2009-12-10' from dual union
select date '2009-12-11' from dual union
select date '2009-12-12' from dual union
select date '2009-12-16' from dual union
select date '2009-12-17' from dual union
select date '2009-12-20' from dual;

select min(DateVal),max(DateVal),count(*)
from (select DateVal,
      DateVal - Row_Number() over(order by DateVal)
      as DisTance
      from Ex2)
group by DisTance
order by min(DateVal);

Min(DateVal)  Max(DateVal)  count(*)
------------  ------------  --------
2009-12-10    2009-12-12           3
2009-12-16    2009-12-17           2
2009-12-20    2009-12-20           1

05 年月の連続した行を集約

create table Ex3 (DateVal primary key) as
select date '2009-09-01' from dual union
select date '2009-10-01' from dual union
select date '2009-12-01' from dual union
select date '2010-01-01' from dual union
select date '2010-02-01' from dual union
select date '2010-04-01' from dual;

select min(DateVal),max(DateVal),count(*)
from (select DateVal,
       extract(year  from DateVal)*12
      +extract(month from DateVal)
      -Row_Number() over(order by DateVal)
      as DisTance
      from Ex3)
group by DisTance
order by min(DateVal);

min(DateVal)  max(DateVal)  count(*)
------------  ------------  --------
2009-09-01    2009-10-01           2
2009-12-01    2010-02-01           3
2010-04-01    2010-04-01           1

06 列の値が一致し続ける行を集約

前述した旅人算メソッドは、列の値が、1づつ増える行を集約しました。

旅人算メソッドは、ソートキーの順序で、列の値が一致し続ける行を集約する
という用途もあります。

create table Ex4 (ID,Val,SortKey) as
select 1, 5, 1 from dual union all
select 1,10, 2 from dual union all
select 2, 2, 3 from dual union all
select 2, 5, 4 from dual union all
select 1,15, 5 from dual union all
select 3,25, 6 from dual union all
select 3,10, 7 from dual union all
select 3, 5, 8 from dual union all
select 3,15, 9 from dual union all
select 4, 5,10 from dual;

SortKeyの昇順でIDが一致する行を集約します。

select ID,min(Val),max(Val),count(*)
from (select ID,Val,SortKey,
       Row_Number() over(order by SortKey)
      -Row_Number() over(partition by ID order by SortKey)
      as DisTance
      from Ex4)
group by ID,DisTance
order by min(SortKey);

ID  Min(Val)  Max(Val)  COUNT(*)
--  --------  --------  --------
 1         5        10         2
 2         2         5         2
 1        15        15         1
 3         5        25         4
 4         5         5         1

上記のSQLでは、5人の旅人(XとAとBとCとD)をイメージしてます。
旅人Xは、必ず1進みます。 Row_Number() over(order by NumVal)
旅人Aは、ID = 1 の時のみ、1進みます。Row_Number() over(partition by ID order by SortKey)
旅人Bは、ID = 2 の時のみ、1進みます。Row_Number() over(partition by ID order by SortKey)
旅人Cは、ID = 3 の時のみ、1進みます。Row_Number() over(partition by ID order by SortKey)
旅人Dは、ID = 4 の時のみ、1進みます。Row_Number() over(partition by ID order by SortKey)

そして、
旅人Xと旅人Aとの距離。旅人Xと旅人Bとの距離。
旅人Xと旅人Cとの距離。旅人Xと旅人Dとの距離。
を求めます

そして、旅人の種類(A,B,C,Dのいずれか)と、旅人Xとの距離
でグループ化してます。group by ID,DisTance

07 複数列の値が一致し続ける行を集約

元ネタ US-OTN analytic sql question
https://community.oracle.com/thread/941878

create table mytable (sortKey,Val1,Val2) as
select 1,'A','X' from dual union all
select 2,'A','X' from dual union all
select 3,'B','Y' from dual union all
select 4,'B','Y' from dual union all
select 5,'A','X' from dual union all
select 5,'B','X' from dual union all
select 6,'A','Y' from dual union all
select 7,'B','Y' from dual union all
select 7,'A','Y' from dual union all
select 8,'A','Y' from dual;

SortKeyの昇順でVal1とVal2が一致する行を集約します。

select Val1,Val2,min(sortKey) as sta,max(sortKey) as end
from (select sortKey,Val1,Val2,
       dense_rank() over(order by sortKey)
      -Row_Number() over(partition by Val1,Val2
                         order by sortKey)
      as DisTance
       from mytable)
group by Val1,Val2,DisTance
order by min(sortKey);

Val1  Val2  sta  end
----  ----  ---  ---
A     X       1    2
B     Y       3    4
B     X       5    5
A     X       5    5
A     Y       6    8
B     Y       7    7

上記のSQLでは、5人の旅人(XとAとBとCとD)をイメージしてます。
旅人Xは、必ず1進みます。 dense_rank() over(order by NumVal)
旅人Aは、Val1 = 'A' and Val2 = 'X' の時のみ、1進みます。 Row_Number() over(partition by Val1,Val2 order by SortKey)
旅人Bは、Val1 = 'A' and Val2 = 'Y' の時のみ、1進みます。 Row_Number() over(partition by Val1,Val2 order by SortKey)
旅人Cは、Val1 = 'B' and Val2 = 'X' の時のみ、1進みます。 Row_Number() over(partition by Val1,Val2 order by SortKey)
旅人Dは、Val1 = 'B' and Val2 = 'Y' の時のみ、1進みます。 Row_Number() over(partition by Val1,Val2 order by SortKey)

そして、
旅人Xと旅人Aとの距離。旅人Xと旅人Bとの距離。
旅人Xと旅人Cとの距離。旅人Xと旅人Dとの距離。
を求めます

そして、旅人の種類(A,B,C,Dのいずれか)と、旅人Xとの距離
でグループ化してます。group by Val1,Val2,disTance

08 旅人算メソッドと同じ結果を得る方法

旅人算メソッドは、
Lag関数とCase式を組み合わせて、WillSumという値を求めてから、
sum関数で累計を求めるという方法で代用できます。

select min(NumVal),max(NumVal),count(*)
from (select NumVal,
      sum(WillSum) over(order by NumVal) as GID
      from (select NumVal,
            case when NumVal-1
               = Lag(NumVal) over(order by NumVal)
                 then 0 else 1 end as WillSum
            from Ex1))
group by GID
order by GID;

Min(NumVal)  Max(NumVal)   COUNT(*)
-----------  -----------  ---------
          1            3          3
          5            7          3
         10           12          3
         20           21          2

上記のSQLでは、インラインビューが2つ必要ですが、
旅人算メソッドを使えば、インラインビューが1つで済みます。

12cからは、Match_Recognize句を使う方法もあります。
Match_Recognize句を使えば、インラインビューは不要になります。

09 旅人算メソッドが使用された質問(日本語)

OTN 連続する項目の件数をカウントするには？
https://community.oracle.com/thread/2596029

10 旅人算メソッドが使用された質問(英語)

sql - Oracle : min max values within a repeating group - Stack Overflow
https://stackoverflow.com/questions/20632922/oracle-min-max-values-within-a-repeating-group

11 旅人算メソッドを紹介したブログ(日本語)

履歴管理されているマスタを圧縮するSQL - A.R.N [日記]
http://d.hatena.ne.jp/arn/20120823/p1

キー項目がブレイクしたタイミングでサマリ集計するSQL (ROW_NUMBER分析ファンクション)
https://gonsuke777.hatenablog.com/entries/2014/12/02

12 旅人算メソッドを紹介したブログ(英語)

About Oracle: Tabibitosan
http://rwijk.blogspot.com/2014/01/tabibitosan.html

12c MATCH_RECOGNIZE: Grouping sequences | An Oracle Programmer
https://stewashton.wordpress.com/2014/03/05/12c-match_recognize-grouping-sequences/