SQL로만 순차적으로 정렬/조합

여러분도 표에 저장된 값에서 임의로 배열할 수 있습니다n\mathrm{P} _r와 조합n\mathrm{C} _나는 네가 r를 열거한 경험이 있다고 생각한다.
이 글에서는 SQL의 배열/조합만 열거할 수 있는지 Snowflake를 예로 들겠습니다.

일반적인 방법: Self Join

실제로 이것은 SQL과 유사한 고전적인 방법이다.그것은 셀프 조인, 즉 같은 탁자를 결합시키는 방법이다.
만약 배열이라면 이 줄과 다른 줄을 합치고, 조합이라면 이 줄보다 작은 줄을 조합하면 된다.
우선 샘플 데이터로 0에서 9까지의 숫자를 저장한 표nums를 만들었다.

create or replace table nums (i int) as
select seq4() from table(generator(rowcount => 10));
/*
0
1
2
...
7
8
9
*/

우선, 배열의 예로{10}\mathrm{P} _생각하다
같은 10개의 값을 저장한 3열에서 각각 다른 값을 취하면 된다. 조회는 다음과 같다.

select n1.i, n2.i, n3.i
from nums n1
join nums n2 on n1.i != n2.i
join nums n3 on n1.i != n3.i and n2.i != n3.i;
-- 720 rows

2 0 1
3 0 1
4 0 1
...
5 9 8
6 9 8
7 9 8

가 720줄의 결과를 정확하게 되돌려줍니다.
콤비네이션{10}\mathrm{C} _3도 마찬가지로 같은 10개의 값이 저장된 3열에서 왼쪽 열보다 작은 값을 하나씩 취하면 된다. 조회는 다음과 같다.

select n1.i, n2.i, n3.i
from nums n1
join nums n2 on n1.i > n2.i
join nums n3 on n2.i > n3.i;
-- 120 rows

2 1 0
3 1 0
4 1 0
...
9 8 5
9 8 6
9 8 7

Self Join 의 문제점

상술한 실시의 문제는 확장성이 부족하다는 것이다.
예컨대 이것은{100}\mathrm{P} _{99} 따위가 되면 99개의 JOIN 문장을 배열하고 결합 조건도 99개의 AND를 배열해야 한다.
또한 n과 r를 매개 변수의 표 함수로 삼으려면 JOIN 문장을 동적으로 늘리거나 열 수를 늘리기 어려우므로 더욱 유연하게 실시해야 한다.
그럼 조금 융통성 있는 설치 방법에 대해 논의해 봅시다.

보다 유연한 방법: Recursive CTE DFS

DFS(Dequence Fracture Support Search) 가 해결한 일반적인 문제입니다.
SQL로 DFS 같은 걸 할 수 있다고 하는데 SQL은 순환[1]이 없고 컴백이 있어요.Recursive CTE.
Recursive CTE는 대체로 이런 느낌의 기술이다.

with cte as (
    select <初期状態>
    from <テーブル>   
    union all
    select <更新処理>
    from <テーブル>, cte
    where <更新条件> and <終了条件>
)
select ... from cte

CTE(WITH 문장)의cte는 내부에서 자체cte를 참고하기 때문에 귀속 처리되어 종료 조건에 부합될 때까지 행(처리 결과)UNION ALL을 계속한다.
먼저{10}\mathrm{C} _3을 예로 들어 각각 생각하다.
위에서 설명한 대로 열 수를 변경할 수 없으므로 배열(ARRAY 유형)을 출력으로 사용합니다.

초기 상태

이번 목적은 요소수 3을 나타내는 조합의 배열을 생성하는 것이기 때문에 초기 상태는 nums 각 줄의 요소수 1의 배열을 저장할 수 있다.결과의 배열은 열 이름 combination 으로 유지됩니다.
또 현재 얼마나 많은 요소가 포함돼 있는지 개별ARRAY_SIZE()별로 확인하는 것보다 변수로 보관하기 쉬워 level열에 현재 등급을 그대로 뒀다.

select array_construct(i) combination, 1 level
from nums

프로세스 업데이트/조건 업데이트

업데이트 처리는ARRAY_APPEND(),추가적합한i만 추가하면 됩니다.또 level는 단순히 1대치로 설정하면 된다.
업데이트 조건은 왼쪽 열보다 작은 값인 Self Join의 설치와 같습니다.이곳의'왼쪽 열'은 combination열수 그룹의 가장 오른쪽 요소이기 때문에 0-indexlevel-1를 고려하여 값을 얻는다.

select array_append(cte.combination, nums.i), cte.level+1
from nums, cte
where combination[cte.level-1] > nums.i

종료 조건

종료 조건은 업데이트 후 배열 길이가 r이고 이번에 3이 되면 1, 2도 계속 처리해야 하기 때문에 업데이트 후 배열 길이level+1가 3 이하일 때만 처리하면 된다.

cte.level+1 <= 3

조립 조회

그럼 모두 조립 적용할게요.

with cte as (
    select array_construct(i) combination, 1 level
    from nums    
    union all
    select array_append(cte.combination, i), cte.level+1
    from nums, cte
    where combination[cte.level-1] > nums.i and cte.level+1 <= 3
)

이렇게 하면 Recursive CTE 부분이 완성됩니다.
그리고 CTE에서 결과를 얻는 거예요. 이번에 원하는 건.{10}\mathrm{C} _3의 조합, 즉 요소수 3의 배열만 있기 때문에 level = 3로 여과하세요.

with cte as (
    select array_construct(i) combination, 1 level
    from nums    
    union all
    select array_append(cte.combination, nums.i), cte.level+1
    from nums, cte
    where combination[cte.level-1] > nums.i and cte.level+1 <= 3
)
select combination from cte where level = 3;

이렇게 하면 완성됩니다.이 동작의 결과는 다음과 같습니다. 120줄을 되돌려줍니다.

[ 2, 1, 0 ]
[ 3, 1, 0 ]
[ 3, 2, 0 ]
...
[ 9, 8, 5 ]
[ 9, 8, 6 ]
[ 9, 8, 7 ]

참고로 ARRAY_CONTAINS()를 사용하여 업데이트 조건을'수조에 포함되지 않은 값'으로 바꾸면 순서대로 배열됩니다.

with cte as (
    select array_construct(i) permutation, 1 level
    from nums    
    union all
    select array_append(cte.permutation, nums.i), cte.level+1
    from nums, cte
    where array_contains(nums.i::variant, permutation) = false and cte.level+1 <= 3
)
select permutation from cte where level = 3;

[ 0, 1, 2 ]
[ 0, 1, 3 ]
[ 0, 1, 4 ]
...
[ 9, 8, 5 ]
[ 9, 8, 6 ]
[ 9, 8, 7 ]

적용:표 함수 만들기

Recursive CTE의 DFS 재구현에 따라 n과 r를 변수로 처리할 수 있으므로 테이블 함수로 변경할 수 있습니다.
우선 n과 r를 매개 변수로 하고 0~n-1의 수치로n\mathrm{C} _r와n\mathrm{P} _r의 데이터 생성 함수를 수조로 열거해 보십시오.

create or replace function combinations(n int, r int)
returns table(combination array)
language sql
as
$$
with
nums as (
    select seq4() i from table(generator(rowcount => n))
),
cte as (
    select array_construct(i) combination, 1 level
    from nums    
    union all
    select array_append(cte.combination, nums.i), cte.level+1
    from nums, cte
    where combination[cte.level-1] > nums.i and cte.level+1 <= r
)
select combination from cte where level = r
$$
;

원시 데이터는 줄 수를 생성하는 매개 변수 nGENERATOR()으로 검색 단수(정지 조건)가 매개 변수 r인 것을 제외하고 상기 검색과 같다.
표 함수로서 임의의 n, r를 열거를 되돌려 주는 함수로 다시 사용할 수 있다.

select * from table(combinations(3, 2));
-- 3 rows
/*
[ 1, 0 ]
[ 2, 0 ]
[ 2, 1 ]
*/

select * from table(combinations(100, 3));
-- 161,700 rows
/*
[ 2, 1, 0 ]
[ 3, 1, 0 ]
[ 3, 2, 0 ]
...
[ 99, 98, 95 ]
[ 99, 98, 96 ]
[ 99, 98, 97 ]
*/

정렬도 같은 표 함수를 사용할 수 있다.

create or replace function permutations(n int, r int)
returns table(permutation array)
language sql
as
$$
with
nums as (
    select seq4() i from table(generator(rowcount => n))
),
cte as (
    select array_construct(i) permutation, 1 level
    from nums    
    union all
    select array_append(cte.permutation, nums.i), cte.level+1
    from nums, cte
    where array_contains(nums.i::variant, permutation) = false and cte.level+1 <= r
)
select permutation from cte where level = r
$$
;

정확{100}\mathrm{P} _3 970200 줄(100*99*98)을 반환합니다.

select * from table(permutations(3, 2));
-- 6 rows
/*
[ 0, 1 ]
[ 0, 2 ]
[ 1, 0 ]
[ 1, 2 ]
[ 2, 0 ]
[ 2, 1 ]
*/

select * from table(permutations(100, 3));
-- 970,200 rows
/*
[ 0, 1, 2 ]
[ 0, 1, 3 ]
[ 0, 1, 4 ]
...

[ 99, 98, 95 ]
[ 99, 98, 96 ]
[ 99, 98, 97 ]
*/

물론 가상 데이터가 아니라 실제 표의 모든 줄에서 조합된 함수를 열거할 수도 있다.LIMIT를 변수로 줄 수를 압축하거나 필터 조건을 변수로 하여 원하는 대로 적용할 수 있습니다.

create or replace table friends (name varchar) as
select * from values ('Mell'), ('Chico'), ('Aro'), ('Marin'), ('Poco'), ('Lou'), ('Nina');

create or replace function friends_combinations(r int)
returns table(combination array)
language sql
as
$$
with
cte as (
    select array_construct(name) combination, 1 level
    from friends    
    union all
    select array_append(cte.combination, friends.name), cte.level+1
    from friends, cte
    where combination[cte.level-1] > friends.name and cte.level+1 <= r
)
select combination from cte where level = r
$$
;

select * from table(friends_combinations(6));
-- 7 rows
/*
[ "Poco", "Mell", "Marin", "Lou", "Chico", "Aro" ]
[ "Poco", "Nina", "Mell", "Marin", "Chico", "Aro" ]
[ "Poco", "Nina", "Mell", "Marin", "Lou", "Chico" ]
[ "Poco", "Nina", "Mell", "Marin", "Lou", "Aro" ]
[ "Poco", "Nina", "Mell", "Lou", "Chico", "Aro" ]
[ "Poco", "Nina", "Marin", "Lou", "Chico", "Aro" ]
[ "Nina", "Mell", "Marin", "Lou", "Chico", "Aro" ]
*/

총결산

이번에 우리는 SQL에 대해서만 배열/조합의 열거를 했다. 위에서 말한 Recursive CTE는 SQL에 절차적 처리를 제출할 수 있는 강력한 문법이다.
문법은 이해하기 어렵지만 이 글처럼 각 부분을 분해해 조립하면 의외로 간단하게 기술할 수 있다.
또한 업데이트 조건/종료 조건에 공을 들여 배열/조합은 물론 데이터베이스의 줄에 대해 자유롭게 DFS를 할 수 있다.
이게 필요한 경우는 드물겠지만 복귀가 필요하지만 글씨를 잘 못 쓸 때 참고할 수 있을 것 같아요.
각주
PL/SQL 및 Transact-SQL은 SQL이 아님↩︎