É extremamente provável que você tenha se deparado com problemas com pesquisas hierárquicas ou passagem de gráficos em seu aplicativo como um desenvolvedor que lida com casos de uso do mundo real. E, por motivos óbvios, você prefere resolvê-los no nível camada de banco de dados e não no lado do cliente.
O que são pesquisas hierárquicas?
A pesquisa hierárquica refere-se ao processo de pesquisa e recuperação de dados de uma estrutura hierárquica, como um ou uma relação pai-filho. Envolve a navegação pelos níveis ou camadas da hierarquia para localizar elementos de dados específicos ou informações relacionadas, por exemplo, organogramas, sistemas de arquivos e árvores de categorias.
Os gráficos são basicamente árvores que podem ter ciclos, portanto, além disso, também poderíamos cobrir casos de uso como localização de caminhos etc., desde que tenhamos configurações adicionais para lidar com ciclos.
Considere um exemplo usando uma coleção de funcionários com uma estrutura hierárquica. Os funcionários são organizados em uma relação gerente-subordinado. Realizaremos operações nessa hierarquia de funcionários usando o Couchbase e UDFs JavaScript para demonstrar a solução.
Indo do Coleção de funcionários que podemos recuperar:
i) nível de funcionário genérico:
ii) hierarquia para cada funcionário:
O que este blog aborda
Você realmente gosta do flexibilidade de bancos de dados NoSQL, e seu modelo de dados subjacente é JSON, e é por isso que você escolheu o Couchbase para suas necessidades de banco de dados (ótima escolha, aliás :-) ).
Agora que você tem o Couchbase como banco de dados, quer resolver o problema mencionado acima. Depois de fazer algumas pesquisas no SQL++ Documentos de referência de idioma você chegou à conclusão de que não há Declaração ou Função no SQL++ para resolver nosso problema, como o graphLookup API no MongoDB ou CTE recursivo em bancos de dados SQL.
Mas Com a infraestrutura existente, os usuários podem emular o CTE recursivo usando UDFs de JavaScript. As seções a seguir demonstrarão como fazer isso e muito mais!
Solução para consultas recursivas
Para implementar essa solução, precisamos criar um UDF em JavaScript que utilize um algoritmo de pesquisa de amplitude em primeiro lugar para percorrer a hierarquia de funcionários. O UDF recebe um consulta de âncora, a consulta recursivae opções de configuração como parâmetros. A consulta âncora recupera o conjunto inicial de funcionários, enquanto a consulta recursiva faz referência aos resultados da iteração anterior usando o parâmetro $1 parâmetro. As opções de configuração permitem a personalização, incluindo critérios de saída antecipada, argumentos para consultas internas, detecção de ciclo, modo de explicação para planejamento de consultas e opções de registro.
Como usar as consultas internas
A consulta de âncora obtém o documentos de nível raiz da coleção de destino.
A consulta recursiva pode usar um JUNTAR com um lado como $1 e a outra como a coleção de destino, para explorar a relação pai-filho e executar a passagem de um nível para outro.
Em nossa função, $1 faz o que o alias do CTE faz no CTE recursivo.
Para entender melhor como usamos o SQL++ (N1QL) em UDFs JavaScript, dê uma olhada em De N1QL para JavaScript e vice-versa.
Agora vamos examinar o processo passo a passo. Em primeiro lugar, O processamento recursivo de consultas realmente precisa ser uma função recursiva?
Não, essa seria uma má escolha, considerando a complexidade de tempo (a mesma funcionalidade em uma abordagem recursiva pode ser exponencial, mas linear em uma abordagem iterativa) e todos os outros problemas, como quadros, etc., que vêm junto com a recursão. Se estiver interessado, dê uma olhada no seguinte artigo sobre a conversão de funções de recursão de cauda em iterativas. Além disso, as UDFs JS têm uma predefinição profundidade máxima de recursão de 128; isso não é preferível para o que estamos tentando fazer.
Para simplificar, qualquer tarefa iterativa faz o seguinte:
Gostaríamos de reconhecer isso artigo por sua abordagem.
Pontos a ponderar
Como podemos manter o expressão de estado e passá-lo como um parâmetro para a consulta (parte recursiva aqui)?
-
- Usamos a capacidade do SQL++ de passar parâmetros de consulta dinâmicos e usar consultas parametrizadas para manter o valor do estado em todos os níveis.
- Usamos $1 na cláusula recursiva para fazer referência aos resultados das iterações anteriores, ou seja, a expressão de estado
Como podemos otimizar?
-
- Prepare inicialmente as consultas âncora e recursivas para que possamos reutilizar os planos de consulta no momento da execução.
- Encontre uma maneira de examinar o plano de consulta (semelhante a um EXPLICAR ) para que possamos gerar índices apropriados para instruções internas (âncoras e recursivas).
A visão geral de alto nível da implementação é a seguinte:
Código para CTE recursivo usando JS UDFs
Essa é uma implementação muito ingênua para começar a funcionar. Configuramos o Breadth-First-Search estabelecendo o fluxo da ordem de acordo com a visão geral acima. Aqui está o código, de este Gist link:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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 |
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; } |
Como adicionar a função
Aqui está um link para adicionar isso a uma biblioteca JavaScript (por exemplo "mylibrary" (minha biblioteca)) em seu serviço de consulta e um link para criar o UDF a partir da biblioteca adicionada.
Crie o UDF a partir da biblioteca usando o SQL++:
|
1 2 |
CREATE FUNCTION recursiveCte(anchor, recursive, config) LANGUAGE JAVASCRIPT as "recursive_cte" AT "mylibrary"; |
Uso
Argumento 1: Âncora consulta, string
Argumento 2: Recursivo consulta, string (usa $1 (expressão de estado) para se referir aos resultados da iteração anterior)
Argumento 3: Configuração opções, objeto
Todos são obrigatóriomas você pode passar um objeto vazio, ou seja, {} se não estiver usando nenhuma opção de configuração.
Opções de configuração
Saída antecipada
levelLimit(1 a N) - Especifica o nível em que podemos parar. A contagem de níveis começa em 0 para obter resultados de ancoragem, 1 para a primeira iteração/nível, 2 para o segundo, etc.
Argumentos para a consulta interna
anchorArgs - como nomeado, por exemplo,{"arg:1} ou argumentos posicionais, por exemplo, [1] para usar na consulta de âncora.
recursiveArgs - Só podem ser argumentos posicionais, e 0 deve ser reservado para a expressão de estado. Por exemplo: [0, 1] - sempre define o 0º índice ($1 arg) para 0para que possamos usá-lo na cláusula recursiva como expressão de estado.
Detecção de ciclo
cycleFields - Matriz de nomes de campos, por exemplo, ["_from", "_to"]
Explicar
explicar - Verificar o plano de consulta nos logs (sets registro por padrão)
Registros
registro - Exibir registros que ajudam quando se deseja registrar durante o desenvolvimento
Consultas de amostra
1. Contar números de 1 a N - exemplo mais simples de uma consulta que mostra como o CTE recursivo funciona.
Faça uma breve pausa para pensar em como você poderia fazer isso no N1QL sem a função que desenvolvemos agora. Isso é possível? (Ou será que acabamos de fazer N1QL Turing completo!)
2. Exemplo de funcionários - referem-se à coleção de funcionários que vimos anteriormente.
A. Encontre o nível organizacional de um funcionário
B. Por funcionário se reporta à hierarquia
Consulta de âncora:
|
1 2 3 |
SELECT e1.*, 0 as hlevel FROM `employees` e1 WHERE e1.manager_id=" || to_str(e.employee_id) |
Isso pode parecer muito detalhado ao adicionar um ONDE predicado da consulta externa. We pode usar o anchorArgs opção para mitigar isso!
Argumentos (anchorArgs/recursiveArgs)
Explicar
Fornecer {"explain": true} - Você pode ver o plano de consulta no campo de registro
Saída antecipada
Conjunto levelLimit como {"levelLimit":2} - se você quiser apenas 2 níveis de recursão
Detecção de ciclo
Sem detecção de ciclo a consulta para encontrar a hierarquia de nível de funcionário será inserida em um loop infinito e travar no tempo limite da função, desperdiçando recursos da CPU.
Considerando que, quando trabalhamos com dados de gráficos, é muito provável que tenhamos ciclos presentes, e é o responsabilidade do chamador da função de definir a detecção de ciclo dos campos apropriados.
Aqui, o "employee_id", "manager_id" é suficiente para sair no ciclo.
Obrigado por acompanhar esse tópico desafiador. Esperamos que ele revele mais opções para alguns de seus desafios de consulta recursiva!
Referências
-
- Converter funções recursivas em funções iterativas (Baeldung)
- Documentos de referência da linguagem SQL++
- Referência do graphLookup do MongoDB
- Referência de CTE recursivo Snowflake
- Blog: De N1QL para JavaScript e vice-versa - Parte 1
- Referência de consulta do PostgreSQL, cláusula WITH
- Documentos de consultas e resultados do SQL++
- Criando uma biblioteca JavaScript docs
- Criação de funções definidas pelo usuário (UDF) no Couchbase
