Recursive Query Processing in SQL++ (N1QL) Function

다음과 같은 문제가 발생했을 가능성이 매우 높습니다. 계층적 조회 또는 그래프 탐색 실제 사용 사례를 처리하는 개발자로서 애플리케이션에 대한 고민이 많습니다. 그리고 당연한 이유로 이러한 문제는 클라이언트 측이 아닌 데이터베이스 계층에서.

계층적 조회란 무엇인가요?

계층 구조 조회는 다음과 같은 계층 구조에서 데이터를 검색하고 검색하는 프로세스를 말합니다. 트리 또는 부모-자식 관계. 여기에는 조직도, 파일 시스템, 카테고리 트리와 같은 특정 데이터 요소나 관련 정보를 찾기 위해 계층 구조의 수준 또는 계층을 탐색하는 작업이 포함됩니다.

그래프는 기본적으로 주기를 가질 수 있는 트리이므로 주기를 처리할 수 있는 추가 구성이 있다면 경로 찾기 등의 사용 사례도 다룰 수 있습니다.

계층 구조가 있는 직원 컬렉션을 사용하는 예를 살펴봅시다. 직원은 관리자-부하 관계로 구성됩니다. 이 직원 계층 구조에 대한 작업을 Couchbase와 JavaScript UDF를 사용하여 수행하여 솔루션을 시연해 보겠습니다.

에서 직원 컬렉션 검색할 수 있습니다:

i) 일반 직원 수준:

ii) 각 직원에 대한 계층 구조:

이 블로그에서 다루는 내용

정말 좋아합니다. 유연성 의 기본 데이터 모델은 다음과 같습니다. JSON, 그렇기 때문에 데이터베이스 요구 사항을 위해 Couchbase를 선택한 것입니다 (훌륭한 선택입니다. :-) ).

이제 Couchbase를 데이터베이스로 사용하므로 위에서 언급한 문제를 해결하려고 합니다. 몇 가지 조사를 한 후 SQL++ 언어 참조 문서 이 없다는 결론에 도달했습니다. 성명서 또는 기능 와 같은 문제를 해결하기 위해 SQL++의 그래프 조회 MongoDB의 API 또는 재귀적 CTE 를 SQL 데이터베이스에 저장합니다.

하지만 기존 인프라를 통해 사용자는 자바스크립트 UDF를 사용하여 재귀적 CTE를 에뮬레이션할 수 있습니다. 다음 섹션에서는 이를 수행하는 방법과 그 이상을 설명합니다!

재귀 쿼리에 대한 솔루션

이 솔루션을 구현하려면 폭 우선 검색 알고리즘을 사용하여 직원 계층을 탐색하는 JavaScript UDF를 만들어야 합니다. UDF는 앵커 쿼리, a 재귀 쿼리및 매개변수로 구성 옵션. 앵커 쿼리는 초기 직원 집합을 검색하는 반면 재귀 쿼리는 이전 반복의 결과를 $1 매개변수를 사용할 수 있습니다. 구성 옵션을 사용하면 조기 종료 기준, 내부 쿼리에 대한 인수, 주기 감지, 쿼리 계획 설명 모드, 로깅 옵션 등의 사용자 지정이 가능합니다.

내부 쿼리 사용 방법

앵커 쿼리는 루트 수준 문서 를 대상 컬렉션에서 제거합니다.

재귀 쿼리는 JOIN 절의 한 쪽을 $1 와 다른 하나를 대상 컬렉션으로 지정하여 부모-자식 관계를 악용하고 한 수준에서 다른 수준으로 이동을 수행합니다.

기능에서, $1 는 재귀적 CTE에서 CTE 별칭이 수행하는 작업을 수행합니다.

JavaScript UDF 내에서 SQL++(N1QL)을 사용하는 방법을 더 잘 이해하려면 다음을 살펴보세요. N1QL에서 JavaScript로, 그리고 다시.

이제 프로세스를 단계별로 살펴보겠습니다. 우선 재귀 쿼리 처리가 정말 재귀 함수여야 하나요?

아니요, 시간 복잡성(재귀에서는 동일한 기능이 기하급수적이지만 반복 접근 방식에서는 선형적일 수 있음)과 재귀와 함께 발생하는 프레임 등의 다른 모든 문제를 고려할 때 이것은 나쁜 선택입니다. 관심이 있으시다면 다음을 확인해 보세요. 기사 를 사용하여 테일 재귀 함수를 반복으로 변환할 수 있습니다. 또한 JS UDF에는 사전 설정된 최대 재귀 깊이는 128입니다; 이는 우리가 하려는 일에 바람직하지 않습니다.

간단히 말해, 모든 반복 작업은 다음을 수행합니다:

저희는 이 점을 인정하고 싶습니다. 기사 의 접근 방식에 대해 설명합니다.

고려해야 할 사항

어떻게 상태 표현식 를 생성하고 쿼리에 매개 변수로 전달할 수 있나요(여기서는 재귀적인 부분)?

- SQL++ 기능을 사용하여 동적 쿼리 매개 변수 매개변수화된 쿼리를 사용하여 여러 레벨에 걸쳐 상태 값을 유지합니다.
- 당사는 다음을 사용합니다. $1 를 재귀 절에 사용하여 이전 반복 결과, 즉 상태 표현식을 참조합니다.

어떻게 최적화할 수 있을까요?

- 실행 시점에 쿼리 계획을 재사용할 수 있도록 앵커 쿼리와 재귀 쿼리를 모두 처음에 준비합니다.
- 쿼리 계획을 보는 방법 찾기( 설명 문)을 사용하여 내부 문(앵커 및 재귀)에 적절한 인덱스를 생성할 수 있습니다.

구현에 대한 개괄적인 개요는 다음과 같습니다:

JS UDF를 사용한 재귀적 CTE 코드

이것은 시작하고 실행하기에 매우 순진한 구현입니다. 우리는 범위 우선 검색 알고리즘을 사용하여 위의 개요에 따라 주문의 흐름을 설정합니다. 코드는 다음과 같습니다. 이 요점 링크:

function recursive_cte(anchor , recursive, config) {
    let isLog = false;
    let anchorArgs=[];
    let recursiveArgs=[];
    let cycleFields=[];
    let hash;    
    let levelLimit = -1;
    let isExplain = false;

    let res = {"res":[], "log":[]}


    if(config!=undefined) {
        if(config.log!=undefined && config.log==true) {
            isLog = true;
        }

        if(config.anchorArgs!=undefined) {
            anchorArgs = config.anchorArgs;
        }

        if(config.recursiveArgs!=undefined) {
            recursiveArgs = config.recursiveArgs;
        }

        if(config.levelLimit!=undefined && config.levelLimit>0) {
            levelLimit = config.levelLimit;
        }

        if(config.cycleFields!=undefined && config.cycleFields.length>0) {
            res['log'].push("Got cycle fields "+ config.cycleFields)
            // for(const field of config.cycleFields) {
            //     cycleFields.push(field);
            // }
            cycleFields = config.cycleFields;
            res['log'].push(cycleFields);
            // init hash
            hash = createhash();

        }

        if(config.explain!=undefined) {
            isExplain = true;
        }

    }
    

    // init state
    recursiveArgs.push(0);
    
    // Prepare anchor statement
    let anchorPname;
    let anchorPlan;
    try{
        const anchor_prep = N1QL("PREPARE FORCE "+anchor);
        
        for(const ap of anchor_prep) {
            anchorPname = ap["name"];
            anchorPlan = ap["operator"];
        }

        res['log'].push("prepared anchor");
    }
    catch(err) {
        res['log'].push("couldn't prepare anchor");
        throw err;
    }

     // prepare recursive statement

     let recursivePname;
     let recursivePlan;
     try{
         const recursive_prep = N1QL("PREPARE FORCE "+recursive);
 
         for(const rp of recursive_prep) {
             recursivePname = rp["name"];
             recursivePlan = rp["operator"];
         }
         res['log'].push("prepared recursive");
     }
     catch(err) {
         res['log'].push("couldn't prepare recursive");
         throw err;
     }


    // state expression 
    let workSet = []

    // execute anchor 
    try{
        const anchorExec = N1QL("EXECUTE `"+anchorPname+"`",anchorArgs);
        for(const doc of anchorExec) {
            workSet.push(doc);
        }
    }
    catch(err) {
        res['log'].push("failed to execute anchor");
        throw err;
    }

    // cycle check
    if(cycleFields.length>0) {
        res['log'].push("cycle check on fields "+cycleFields)
        workSet = cycleCheck(cycleFields, hash, workSet);
    }

    // populate root level( level 0 )
    res['res'].push(...workSet);


    let level = 0;

    while(workSet.length!=0) {

        // exit on level condition
        if(levelLimit>0 && level>=levelLimit) {
            res['log'].push("Exit on level condition: levelLimit="+levelLimit.toString())
            break;
        }

        // execute recursive query
        let newWorkSet = []

        // set state $1
        recursiveArgs[0] = workSet;

        try{
            const recursiveExec = N1QL("EXECUTE `"+recursivePname+"`", recursiveArgs)

            // empty workSet to populate again
            for(const doc of recursiveExec) {
                newWorkSet.push(doc)
            }
        }
        catch(err){
            res['log'].push("failed execute recursive");
            throw err;
        }

        // cycle check
        if(cycleFields.length>0) {
            newWorkSet = cycleCheck(cycleFields, hash, newWorkSet);
        }

        if(newWorkSet.length==0)
            break;

        
        res["res"].push(...newWorkSet);

        // update state expression
        workSet = newWorkSet;

        level++;
    }

    if(isExplain){
        res['log'].push("Anchor Plan:");
        res['log'].push(anchorPlan);
        res['log'].push("Recursive Plan");
        res["log"].push(recursivePlan);
        return res;
    }

    return isLog?res:res['res'];
}


function createhash() {
    let h = {};

    const getVal = function(key) {
        return h[key]==undefined?false:true;
    }

    const setVal = function(key) {
        h[key] = true;
    }

    return {setVal, getVal};
}

function cycleCheck(cycleFields, hash, workSet) {
    let cycleTrim = [];
    for(const doc of workSet) {
        let key = [];
        for(const field of cycleFields) {
            if(doc[field]!=undefined){
                key.push(String(doc[field]));
            }
        }

        // create hashKey
        hashKey = key.join(String.fromCharCode(30));


        if(hash.getVal(hashKey)==true){
            continue;
        }
        else{
            hash.setVal(hashKey);
            cycleTrim.push(doc);
        }
    }

    return cycleTrim;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

함수 recursive_cte(앵커 , 재귀적, 구성) {

let isLog = false;

let anchorArgs=[];

let recursiveArgs=[];

let 주기 필드=[];

let 해시;

let levelLimit = -1;

let isExplain = false;

let res = {"res":[], "log":[]}

만약(구성!=정의되지 않음) {

만약(구성.로그!=정의되지 않음 && 구성.로그==true) {

isLog = true;

}

만약(구성.anchorArgs!=정의되지 않음) {

anchorArgs = 구성.anchorArgs;

}

만약(구성.recursiveArgs!=정의되지 않음) {

recursiveArgs = 구성.recursiveArgs;

}

만약(구성.levelLimit!=정의되지 않음 && 구성.levelLimit>0) {

levelLimit = 구성.levelLimit;

}

만약(구성.주기 필드!=정의되지 않음 && 구성.주기 필드.길이>0) {

res['log'].push("주기 필드가 있습니다."+ 구성.주기 필드)

// for(config.cycleFields의 const field) {

// cycleFields.push(field);

// }

주기 필드 = 구성.주기 필드;

res['log'].push(주기 필드);

// 초기화 해시

해시 = createhash();

}

만약(구성.설명!=정의되지 않음) {

isExplain = true;

}

// 초기화 상태

recursiveArgs.push(0);

// 앵커 문 준비

let 앵커 이름;

let 앵커플랜;

시도{

const 앵커 준비 = N1QL("힘 준비"+앵커);

에 대한(const ap 의 앵커 준비) {

앵커 이름 = ap["name"];

앵커플랜 = ap["운영자"];

}

res['log'].push("준비된 앵커");

}

catch(err) {

res['log'].push("앵커를 준비할 수 없음");

throw err;

}

// 재귀문 준비

let recursivePname;

let 재귀적 계획;

시도{

const 재귀적_준비 = N1QL("힘 준비"+재귀적);

에 대한(const rp 의 재귀적_준비) {

recursivePname = rp["name"];

재귀적 계획 = rp["운영자"];

}

res['log'].push("준비된 재귀");

}

catch(err) {

res['log'].push("재귀를 준비할 수 없음");

throw err;

}

// 상태 표현식

let workSet = []

// 실행 앵커

시도{

const anchorExec = N1QL("실행 `"+앵커 이름+"`",anchorArgs);

에 대한(const doc 의 anchorExec) {

workSet.push(doc);

}

catch(err) {

res['log'].push("앵커를 실행하지 못했습니다");

throw err;

}

// 주기 확인

만약(주기 필드.길이>0) {

res['log'].push("필드에 대한 주기 확인 "+주기 필드)

workSet = 주기 확인(주기 필드, 해시, workSet);

}

// 루트 레벨 채우기( 레벨 0 )

res['res'].push(...workSet);

let 레벨 = 0;

동안(workSet.길이!=0) {

// 레벨 조건에서 종료

만약(levelLimit>0 && 레벨>=levelLimit) {

res['log'].push("레벨 조건에서 종료: levelLimit="+levelLimit.toString())

break;

}

// 재귀 쿼리 실행

let 새로운 워크셋 = []

// 상태 $1 설정

recursiveArgs[0] = workSet;

시도{

const recursiveExec = N1QL("실행 `"+recursivePname+"`", recursiveArgs)

// 빈 작업 다시 채우도록 설정

에 대한(const doc 의 recursiveExec) {

새로운 워크셋.push(doc)

}

catch(err){

res['log'].push("재귀 실행 실패");

throw err;

}

// 주기 확인

만약(주기 필드.길이>0) {

새로운 워크셋 = 주기 확인(주기 필드, 해시, 새로운 워크셋);

}

만약(새로운 워크셋.길이==0)

break;

res["res"].push(...새로운 워크셋);

// 상태 표현식 업데이트

workSet = 새로운 워크셋;

레벨++;

}

만약(isExplain){

res['log'].push("앵커 플랜:");

res['log'].push(앵커플랜);

res['log'].push("재귀적 계획");

res["log"].push(재귀적 계획);

반환 res;

}

반환 isLog?res:res['res'];

}

함수 createhash() {

let h = {};

const getVal = 함수(키) {

반환 h[키]==정의되지 않음?false:true;

}

const setVal = 함수(키) {

h[키] = true;

}

반환 {setVal, getVal};

}

함수 주기 확인(주기 필드, 해시, workSet) {

let cycleTrim = [];

에 대한(const doc 의 workSet) {

let 키 = [];

에 대한(const 필드 의 주기 필드) {

만약(doc[필드]!=정의되지 않음){

키.push(문자열(doc[필드]));

}

// 해시키 생성

해시키 = 키.join(문자열.fromCharCode(30));

만약(해시.getVal(해시키)==true){

계속;

}

else{

해시.setVal(해시키);

cycleTrim.push(doc);

}

반환 cycleTrim;

}

기능 추가 방법

다음은 링크 를 사용하여 자바스크립트 라이브러리에 추가할 수 있습니다(예 "mylibrary"), 쿼리 서비스 내에서 링크 를 클릭하여 추가된 라이브러리에서 UDF를 생성합니다.

SQL++를 사용하여 라이브러리에서 UDF를 생성합니다:

CREATE FUNCTION recursiveCte(anchor, recursive, config) 
LANGUAGE JAVASCRIPT as "recursive_cte" AT "mylibrary";

1 2	만들기 기능 recursiveCte(앵커, 재귀적, 구성) 언어 자바스크립트 as "recursive_cte" AT "mylibrary";

사용법

인수 1: 앵커 쿼리, 문자열
인수 2: 재귀적 쿼리, 문자열 (사용 $1(상태 표현식) 이전 반복의 결과를 참조하기 위해)
인수 3: 구성 옵션객체

모두 필수를 전달할 수 있지만 빈 개체즉., {} 구성 옵션을 사용하지 않는 경우 를 입력합니다.

구성 옵션

조기 종료

levelLimit(1 ~ N) - 멈출 수 있는 레벨을 지정합니다. 레벨 카운트는 다음에서 시작됩니다. 0 앵커 결과를 확인합니다, 1 를 첫 번째 반복/레벨에 사용합니다, 2 두 번째 등

내부 쿼리에 대한 인수

anchorArgs - 예를 들어{"arg:1} 또는 위치 인자(예: [1] 를 사용하여 앵커 쿼리에 사용할 수 있습니다.

recursiveArgs - 위치 인수만 가능하며 0 인덱스는 상태 표현식을 위해 예약해야 합니다. 예를 들어 [0, 1] - 항상 0번째 인덱스($1 인수)에서 0를 사용하여 재귀 절에서 상태 표현식으로 사용할 수 있습니다.

주기 감지

주기 필드 - 필드 이름의 배열(예:, ["_from", "_to"]

설명

설명 - 로그에서 쿼리 계획 확인(세트 로그 기본값)

로그

로그 - 개발 중 로깅을 하고 싶을 때 도움이 되는 로그 표시

샘플 쿼리

1. 숫자 1부터 N까지 세기 - 재귀적 CTE의 작동 방식을 보여주는 가장 간단한 쿼리 예제입니다.

잠시 멈춰서 N1QL에서 이 기능을 사용하지 않고 어떻게 이 작업을 수행할 수 있는지 생각해 보세요. 유틸리티를 개발했습니다. 가능할까요? (아니면 방금 N1QL 튜링 완료!)

2. 직원 예시 - 앞서 살펴본 직원 컬렉션을 참조하세요.

A. 직원의 조직 수준 찾기

B. 계층 구조에 대한 직원별 보고서

앵커 쿼리:

SELECT e1.*, 0 as hlevel 
FROM `employees` e1 
WHERE e1.manager_id=" || to_str(e.employee_id)

선택 e1.*, 0 as hlevel

FROM `직원` e1

어디 e1.관리자_id=" || to_str(e.employee_id)

추가할 때 너무 장황해 보일 수 있습니다. 어디 술어를 외부 쿼리에서 가져옵니다. W를 사용할 수 있습니다. anchorArgs 옵션 를 사용하여 이를 완화할 수 있습니다!

인수(앵커Args/재귀Args)

설명

제공 {"explain": true} - 로그 필드에서 쿼리 계획을 확인할 수 있습니다.

조기 종료

설정 levelLimit 같은 {"levelLimit":2} - 2단계 재귀만 원하는 경우

주기 감지

사이클 감지 기능 없음 직원 수준 계층을 찾기 위한 쿼리는 무한 루프 함수 타임아웃 시 충돌이 발생하여 CPU 리소스를 낭비합니다.

그래프 데이터로 작업할 때 사이클이 존재할 가능성이 높다는 점을 고려하면 적절한 필드의 주기 감지를 설정하는 것은 함수 호출자의 책임입니다.

여기에서 "employee_id", "manager_id" 쌍은 주기적으로 종료하기에 충분합니다.

이 어려운 주제에 관심을 가져주셔서 감사드리며, 재귀 쿼리 문제를 해결할 수 있는 더 많은 옵션이 공개되기를 바랍니다!

참조

가우라브 자야라즈 - 소프트웨어 엔지니어

이 문서 공유하기

Platform

Self-Managed

Services

Capabilities

Why Couchbase?

Migrate to Capella

By Use Case

By Industry

By Application Need

Popular Docs

By Developer Role

Quickstart

Resource Center

About

Partnerships

Our Services

Partners: Register a Deal

Ready to register a deal with Couchbase?

Marriott

SQL++의 재귀 쿼리 처리(N1QL)

계층적 조회란 무엇인가요?

이 블로그에서 다루는 내용

재귀 쿼리에 대한 솔루션

내부 쿼리 사용 방법

고려해야 할 사항

JS UDF를 사용한 재귀적 CTE 코드

기능 추가 방법

샘플 쿼리

인수(앵커Args/재귀Args)

참조

받은 편지함에서 카우치베이스 블로그 업데이트 받기

작성자

게시자 가우라브 자야라즈 - 소프트웨어 엔지니어

댓글 남기기 응답 취소

카우치베이스 카펠라를 시작할 준비가 되셨나요?

구축 시작

카펠라 무료 사용

연락하기