Query Recursiva

Article
11/10/2010

Você sabia que o SQL Server consegue criar uma Query Recursiva? Utilizamos, como exemplo, uma tabela que armazena as informações de MENU de uma página Web.

 CREATE TABLE tbMenu
    (
    id INT NOT NULL IDENTITY(1,1) PRIMARY KEY, 
    idPai INT NULL, 
    Nome VARCHAR(30) NOT NULL
    )

INSERT tbMenu (idPai,Nome) VALUES 
(NULL,'Menu'),(1,'Vestuario'),(1,'Brinquedo'),(1,'Informatica'),
(2,'Terno'),(2,'Casaco'),(2,'Sapato'),(2,'Meia'),(3,'Carrinho'),
(3,'Boneca'),(4,'Netbook'),(4,'Webcam'),(4,'Desktop')
            
SELECT * FROM tbMenu

Conhecendo a relação entre os itens do MENU, como podemos obter uma visualização de forma hierárquica? Ou como criar uma consulta que verifica que o produto Webcam, da categoria Informática, está dentro do Menu Principal?

Conceito

A idéia da query recursiva é montar o resultado por níveis, determinando quem são os registros “raízes”, depois os “descendentes de primeira ordem”, em seguida, “descendentes de segunda ordem”, e por aí vai.

Obter todos os registros de nível 1 – Esses são chamados de registros âncora (anchors)
Com base nos níveis âncoras, selecionar todos os registros do nível 2 (processo recursivo)
Com base nos registros de nível 2, selecionar todos os registros do nível 3
… e assim por diante…

Resultado:

Sintaxe

A sintaxe utilizada para query recursiva é feita através do auxílio das Common Table Expression (CTE) . Sempre utiliza-se uma query inicial determinada de âncora, que contém os registros raízes. Em seguida, os resultados são combinados através de uma operação de UNION ALL com a “query recursiva”: ela possui uma auto-referência.

 WITH cteMenuNivel(id,Nome,Nivel,NomeCompleto)
AS
(
    -- Ancora
    SELECT id,Nome,1 AS 'Nivel',CAST(Nome AS VARCHAR(255)) AS 'NomeCompleto' 
    FROM tbMenu WHERE idPai IS NULL
    
    UNION ALL
    
    -- Parte RECURSIVA
    SELECT 
        m.id,m.Nome,c.Nivel + 1 AS 'Nivel',
        CAST((c.NomeCompleto + '/' + m.Nome) AS VARCHAR(255)) 'NomeCompleto' 
    FROM tbMenu m INNER JOIN cteMenuNivel c ON m.idPai = c.id
    
)
SELECT Nivel,NomeCompleto FROM cteMenuNivel

Performance

O desempenho de query recursiva usando Common Table Expression é excelente para tabela com pouco volume de dados, mas há uma degradação perceptível quando usada em tabelas críticas de sistema e com mais de 10000 registros (comprovado em cliente!). A explicação para esse fato é feita através do plano de execução:

Passo 1: Os resultados da query “âncora” são obtidos a partir de uma operação de leitura da tabela
Passo 2: Os operadores de “Compute Scalar” realizam os cálculos e transformações de tipo de dados
Passo 3 e 4: O resultado parcial é armazenado em uma Tabela Temporária (Index Spool), que serve como fonte de dados para a recursão (Passo 4)
Passo 5: Como parte do processo recursivo, as informações da tabela são lidas novamente
Passo 6: Os novos níveis são identificados através da operação de JOIN entre tabelas. Nesse caso, a operação realizada foi de NESTED LOOP
Passo 7: Os registros do nível seguinte são armazenados na Tabela Temporária e o processo volta ao Passo 4
Quando não forem produzidos mais registros, o processo termina.

Quanto maior o número de passos executados no processo recursivo, maior o impacto na performance da query. Se fosse usada uma tabela com 1 milhão de registros, porém, houvesse poucas repetições dos passo 4-7, o desempenho seria ótimo.

Portanto, o problema não é exatamente o tamanho da tabela ou sua criticidade, mas a quantidade de registros retornados e o número de passos executados.

Query Recursiva

Additional resources