Agrupamento ou Janela

13

Eu tenho uma situação que acho que pode ser resolvida usando a função de janela, mas não tenho certeza.

Imagine a seguinte tabela

CREATE TABLE tmp
  ( date timestamp,        
    id_type integer
  ) ;

INSERT INTO tmp 
    ( date, id_type )
VALUES
    ( '2017-01-10 07:19:21.0', 3 ),
    ( '2017-01-10 07:19:22.0', 3 ),
    ( '2017-01-10 07:19:23.1', 3 ),
    ( '2017-01-10 07:19:24.1', 3 ),
    ( '2017-01-10 07:19:25.0', 3 ),
    ( '2017-01-10 07:19:26.0', 5 ),
    ( '2017-01-10 07:19:27.1', 3 ),
    ( '2017-01-10 07:19:28.0', 5 ),
    ( '2017-01-10 07:19:29.0', 5 ),
    ( '2017-01-10 07:19:30.1', 3 ),
    ( '2017-01-10 07:19:31.0', 5 ),
    ( '2017-01-10 07:19:32.0', 3 ),
    ( '2017-01-10 07:19:33.1', 5 ),
    ( '2017-01-10 07:19:35.0', 5 ),
    ( '2017-01-10 07:19:36.1', 5 ),
    ( '2017-01-10 07:19:37.1', 5 )
  ;

Eu gostaria de ter um novo grupo a cada alteração na coluna id_type. EG 1º grupo de 7:19:21 a 7:19:25, 2º iniciando e terminando às 7:19:26, e assim por diante.
Depois que funcionar, quero incluir mais critérios para definir grupos.

Neste momento, usando a consulta abaixo ...

SELECT distinct 
    min(min(date)) over w as begin, 
    max(max(date)) over w as end,   
    id_type
from tmp
GROUP BY id_type
WINDOW w as (PARTITION BY id_type)
order by  begin;

Eu recebo o seguinte resultado:

begin                   end                     id_type
2017-01-10 07:19:21.0   2017-01-10 07:19:32.0   3
2017-01-10 07:19:26.0   2017-01-10 07:19:37.1   5

Enquanto eu gostaria:

begin                   end                     id_type
2017-01-10 07:19:21.0   2017-01-10 07:19:25.0   3
2017-01-10 07:19:26.0   2017-01-10 07:19:26.0   5
2017-01-10 07:19:27.1   2017-01-10 07:19:27.1   3
2017-01-10 07:19:28.0   2017-01-10 07:19:29.0   5
2017-01-10 07:19:30.1   2017-01-10 07:19:30.1   3
2017-01-10 07:19:31.0   2017-01-10 07:19:31.0   5
2017-01-10 07:19:32.0   2017-01-10 07:19:32.0   3
2017-01-10 07:19:33.1   2017-01-10 07:19:37.1   5

Depois de resolver esta primeira etapa, adicionarei mais colunas para usar como regras para quebrar grupos, e essas outras serão anuláveis.

Versão do Postgres: 8.4 (Temos o Postgres com o Postgis, por isso não é fácil atualizar. As funções do Postgis mudam de nome e existem outros problemas, mas espero que já estejamos escrevendo tudo e a nova versão use uma versão mais recente 9.X com postgis 2.x)

postgresql group-by window-functions gaps-and-islands postgresql-8.4 Lelo
fonte
2
Solução geral: dba.stackexchange.com/questions/35380/…
Erwin Brandstetter

Respostas:

4

Por alguns pontos,

  • Não chame uma tabela não temporária tmp que fica confusa.
  • Não use texto para timestamps (você está fazendo isso no seu exemplo, podemos dizer porque o timestamp não foi truncado e tem .0 )
  • Não chame um campo que tenha tempo nele date. Se tiver data e hora, é um carimbo de data / hora (e armazene-o como um)

Melhor usar uma função de janela ..

SELECT id_type, grp, min(date), max(date)
FROM (
  SELECT date, id_type, count(is_reset) OVER (ORDER BY date) AS grp
  FROM (
    SELECT date, id_type, CASE WHEN lag(id_type) OVER (ORDER BY date) <> id_type THEN 1 END AS is_reset
    FROM tmp
  ) AS t
) AS g
GROUP BY id_type, grp
ORDER BY min(date);

Saídas 

 id_type | grp |          min          |          max          
---------+-----+-----------------------+-----------------------
       3 |   0 | 2017-01-10 07:19:21.0 | 2017-01-10 07:19:25.0
       5 |   1 | 2017-01-10 07:19:26.0 | 2017-01-10 07:19:26.0
       3 |   2 | 2017-01-10 07:19:27.1 | 2017-01-10 07:19:27.1
       5 |   3 | 2017-01-10 07:19:28.0 | 2017-01-10 07:19:29.0
       3 |   4 | 2017-01-10 07:19:30.1 | 2017-01-10 07:19:30.1
       5 |   5 | 2017-01-10 07:19:31.0 | 2017-01-10 07:19:31.0
       3 |   6 | 2017-01-10 07:19:32.0 | 2017-01-10 07:19:32.0
       5 |   7 | 2017-01-10 07:19:33.1 | 2017-01-10 07:19:37.1
(8 rows)

Explicação

Primeiro, precisamos de redefinições. Nós as geramos com lag()

SELECT date, id_type, CASE WHEN lag(id_type) OVER (ORDER BY date) <> id_type THEN 1 END AS is_reset
FROM tmp
ORDER BY date;

         date          | id_type | is_reset 
-----------------------+---------+----------
 2017-01-10 07:19:21.0 |       3 |         
 2017-01-10 07:19:22.0 |       3 |         
 2017-01-10 07:19:23.1 |       3 |         
 2017-01-10 07:19:24.1 |       3 |         
 2017-01-10 07:19:25.0 |       3 |         
 2017-01-10 07:19:26.0 |       5 |        1
 2017-01-10 07:19:27.1 |       3 |        1
 2017-01-10 07:19:28.0 |       5 |        1
 2017-01-10 07:19:29.0 |       5 |         
 2017-01-10 07:19:30.1 |       3 |        1
 2017-01-10 07:19:31.0 |       5 |        1
 2017-01-10 07:19:32.0 |       3 |        1
 2017-01-10 07:19:33.1 |       5 |        1
 2017-01-10 07:19:35.0 |       5 |         
 2017-01-10 07:19:36.1 |       5 |         
 2017-01-10 07:19:37.1 |       5 |         
(16 rows)

Então contamos para obter grupos.

SELECT date, id_type, count(is_reset) OVER (ORDER BY date) AS grp
FROM (
  SELECT date, id_type, CASE WHEN lag(id_type) OVER (ORDER BY date) <> id_type THEN 1 END AS is_reset
  FROM tmp
  ORDER BY date
) AS t
ORDER BY date

         date          | id_type | grp 
-----------------------+---------+-----
 2017-01-10 07:19:21.0 |       3 |   0
 2017-01-10 07:19:22.0 |       3 |   0
 2017-01-10 07:19:23.1 |       3 |   0
 2017-01-10 07:19:24.1 |       3 |   0
 2017-01-10 07:19:25.0 |       3 |   0
 2017-01-10 07:19:26.0 |       5 |   1
 2017-01-10 07:19:27.1 |       3 |   2
 2017-01-10 07:19:28.0 |       5 |   3
 2017-01-10 07:19:29.0 |       5 |   3
 2017-01-10 07:19:30.1 |       3 |   4
 2017-01-10 07:19:31.0 |       5 |   5
 2017-01-10 07:19:32.0 |       3 |   6
 2017-01-10 07:19:33.1 |       5 |   7
 2017-01-10 07:19:35.0 |       5 |   7
 2017-01-10 07:19:36.1 |       5 |   7
 2017-01-10 07:19:37.1 |       5 |   7
(16 rows)

Em seguida, embrulhe em uma subselect GROUP BYe ORDERe selecione o min max (intervalo)

SELECT id_type, grp, min(date), max(date)
FROM (
  .. stuff
) AS g
GROUP BY id_type, grp
ORDER BY min(date);
Evan Carroll
fonte
16

1. Funções da janela mais subconsultas

Conte as etapas para formar grupos, semelhantes à idéia de Evan , com modificações e correções:

SELECT id_type
     , min(date) AS begin
     , max(date) AS end
     , count(*)  AS row_ct  -- optional addition
FROM  (
   SELECT date, id_type, count(step OR NULL) OVER (ORDER BY date) AS grp
   FROM  (
      SELECT date, id_type
           , lag(id_type, 1, id_type) OVER (ORDER BY date) <> id_type AS step
      FROM   tmp
      ) sub1
   ) sub2
GROUP  BY id_type, grp
ORDER  BY min(date);

Isso pressupõe que as colunas envolvidas são NOT NULL. Caso contrário, você precisa fazer mais.

Supondo também dateque esteja definido UNIQUE, você precisará adicionar um desempatador às ORDER BYcláusulas para obter resultados determinísticos. Gostar:ORDER BY date, id .

Explicação detalhada (resposta a pergunta muito semelhante):

Observe em particular:

  • Em casos relacionados, lag()com 3 parâmetros pode ser essencial para cobrir a caixa de canto da primeira (ou última) linha com elegância. (O terceiro parâmetro é usado como padrão se não houver linha anterior (próxima).

    lag(id_type, 1, id_type) OVER ()

    Como estamos interessados ​​apenas em uma mudança real de id_type( TRUE), isso não importa neste caso específico. NULLe FALSEambos não contam como step.

  • count(step OR NULL) OVER (ORDER BY date) é a sintaxe mais curta que também funciona no Postgres 9.3 ou anterior. count()conta apenas valores não nulos ...

    No Postgres moderno, a sintaxe mais limpa e equivalente seria:

    count(step) FILTER (WHERE step) OVER (ORDER BY date)

    Detalhes:

2. Subtraia duas funções da janela, uma subconsulta

Semelhante à idéia de Erik com modificações:

SELECT min(date) AS begin
     , max(date) AS end
     , id_type
FROM  (
   SELECT date, id_type
        , row_number() OVER (ORDER BY date)
        - row_number() OVER (PARTITION BY id_type ORDER BY date) AS grp
   FROM   tmp
   ) sub
GROUP  BY id_type, grp
ORDER  BY min(date);

Se datedefinido UNIQUE, como mencionei acima (você nunca esclareceu), dense_rank()seria inútil, pois o resultado é o mesmo que para row_number()e o último é substancialmente mais barato.

Se nãodate estiver definido (e não sabemos que as únicas duplicatas estão ativadas ), todas essas consultas serão inúteis, pois o resultado é arbitrário.UNIQUE(date, id_type)

Além disso, uma subconsulta é normalmente mais barata que uma CTE no Postgres. Use CTEs somente quando precisar deles.

Respostas relacionadas com mais explicações:

Em casos relacionados em que já temos um número em execução na tabela, podemos nos contentar com uma única função da janela:

3. Desempenho superior com função plpgsql

Como essa pergunta se tornou inesperadamente popular, adicionarei outra solução para demonstrar o melhor desempenho.

O SQL possui muitas ferramentas sofisticadas para criar soluções com sintaxe curta e elegante. Mas uma linguagem declarativa tem seus limites para requisitos mais complexos que envolvem elementos processuais.

Uma função procedural do servidor é mais rápida para isso do que qualquer coisa postada até o momento, porque precisa apenas de uma única varredura seqüencial sobre a tabela e uma operação de classificação única . Se um índice de ajuste estiver disponível, mesmo apenas uma única varredura de índice.

CREATE OR REPLACE FUNCTION f_tmp_groups()
  RETURNS TABLE (id_type int, grp_begin timestamp, grp_end timestamp) AS
$func$
DECLARE
   _row  tmp;                       -- use table type for row variable
BEGIN
   FOR _row IN
      TABLE tmp ORDER BY date       -- add more columns to make order deterministic
   LOOP
      CASE _row.id_type = id_type 
      WHEN TRUE THEN                -- same group continues
         grp_end := _row.date;      -- remember last date so far
      WHEN FALSE THEN               -- next group starts
         RETURN NEXT;               -- return result for last group
         id_type   := _row.id_type;
         grp_begin := _row.date;
         grp_end   := _row.date;
      ELSE                          -- NULL for 1st row
         id_type   := _row.id_type; -- remember row data for starters
         grp_begin := _row.date;
         grp_end   := _row.date;
      END CASE;
   END LOOP;

   RETURN NEXT;                     -- return last result row      
END
$func$ LANGUAGE plpgsql;

Ligar:

SELECT * FROM f_tmp_groups();

Teste com:

EXPLAIN (ANALYZE, TIMING OFF)  -- to focus on total performance
SELECT * FROM  f_tmp_groups();

Você pode tornar a função genérica com tipos polimórficos e passar o tipo de tabela e os nomes de colunas. Detalhes:

Se você não deseja ou não pode persistir em uma função para isso, pagaria até criar uma função temporária em tempo real. Custa alguns ms.

dbfiddle para Postgres 9.6, comparando o desempenho dos três. Construindo nocaso de teste de Jack, modificado.

dbfiddle para Postgres 8.4, onde as diferenças de desempenho são ainda maiores.

Erwin Brandstetter
fonte
Leia isso algumas vezes - ainda sem saber o que você está falando com o atraso de três argumentos ou quando você teria que usar count(x or null)ou mesmo o que está fazendo lá. Talvez você possa mostrar algumas amostras onde é necessário, porque não é necessário aqui. E o que determinaria a exigência de cobrir esses casos de canto. BTW, mudei meu downvote para upvote apenas para o exemplo pl / pgsql. Isso é muito legal. (Mas geralmente sou contra as respostas que resumem outras respostas ou cobrem casos de canto - embora eu odeie dizer que esse é um caso de canto porque não o entendo).
Evan Carroll
Eu os colocaria em duas perguntas auto-respondidas separadas, porque tenho certeza de que não sou a única a pensar no que count(x or null)faz. Ficarei feliz em fazer as duas perguntas, se você preferir.
Evan Carroll
Aqui está uma pergunta. Em que caso é count(x or null)necessário nas lacunas e ilhas?
Evan Carroll
7

Você pode fazer isso como uma simples subtração de ROW_NUMBER()operações (ou se suas datas não forem únicas, embora ainda sejam únicas por id_type, use-as em DENSE_RANK()vez disso, embora seja uma consulta mais cara):

WITH IdTypes AS (
   SELECT
      date,
      id_type,
      Row_Number() OVER (ORDER BY date)
         - Row_Number() OVER (PARTITION BY id_type ORDER BY date)
         AS Seq
   FROM
      tmp
)
SELECT
   Min(date) AS begin,
   Max(date) AS end,
   id_type
FROM IdTypes
GROUP BY id_type, Seq
ORDER BY begin
;

Veja este trabalho no DB Fiddle (ou veja a versão DENSE_RANK )

Resultado:

begin                  end                    id_type
---------------------  ---------------------  -------
2017-01-10 07:19:21    2017-01-10 07:19:25    3
2017-01-10 07:19:26    2017-01-10 07:19:26    5
2017-01-10 07:19:27.1  2017-01-10 07:19:27.1  3
2017-01-10 07:19:28    2017-01-10 07:19:29    5
2017-01-10 07:19:30.1  2017-01-10 07:19:30.1  3
2017-01-10 07:19:31    2017-01-10 07:19:31    5
2017-01-10 07:19:32    2017-01-10 07:19:32    3
2017-01-10 07:19:33.1  2017-01-10 07:19:37.1  5

Logicamente, você pode pensar nisso como um simples DENSE_RANK()com a PREORDER BY, ou seja, você deseja que DENSE_RANKtodos os itens sejam classificados juntos e que eles sejam ordenados pelas datas, basta lidar com o incômodo problema de que a cada alteração na data, DENSE_RANKserá incrementado. Você faz isso usando a expressão como mostrei acima. Imagine se você tivesse esta sintaxe: DENSE_RANK() OVER (PREORDER BY date, ORDER BY id_type)onde o PREORDERé excluído do cálculo de classificação e apenas o ORDER BYé contado.

Observe que é importante GROUP BYtanto para a Seqcoluna gerada quanto para a id_typecoluna. SeqNÃO é único por si só, pode haver sobreposições - você também deve agrupar por id_type.

Para mais informações sobre este tópico:

Esse primeiro link fornece um código que você pode usar se desejar que a data de início ou término seja igual à data de término / início do período anterior ou seguinte (para que não haja lacunas). Além de outras versões que podem ajudá-lo em sua consulta. Embora eles tenham que ser traduzidos da sintaxe do SQL Server ...

ErikE
fonte
6

No Postgres 8.4, você pode usar uma função RECURSIVE .

Como eles fazem isso

A função recursiva adiciona um nível a cada id_type diferente, selecionando as datas uma a uma em ordem decrescente.

       date           | id_type | lv
--------------------------------------
2017-01-10 07:19:21.0      3       8
2017-01-10 07:19:22.0      3       8
2017-01-10 07:19:23.1      3       8
2017-01-10 07:19:24.1      3       8
2017-01-10 07:19:25.0      3       8
2017-01-10 07:19:26.0      5       7
2017-01-10 07:19:27.1      3       6
2017-01-10 07:19:28.0      5       5
2017-01-10 07:19:29.0      5       5
2017-01-10 07:19:30.1      3       4
2017-01-10 07:19:31.0      5       3
2017-01-10 07:19:32.0      3       2
2017-01-10 07:19:33.1      5       1
2017-01-10 07:19:35.0      5       1
2017-01-10 07:19:36.1      5       1
2017-01-10 07:19:37.1      5       1

Em seguida, use o agrupamento MAX (data), MIN (data) por nível, id_type para obter o resultado desejado.

with RECURSIVE rdates as 
(
    (select   date, id_type, 1 lv 
     from     yourTable
     order by date desc
     limit 1
    )
    union
    (select    d.date, d.id_type,
               case when r.id_type = d.id_type 
                    then r.lv 
                    else r.lv + 1 
               end lv    
    from       yourTable d
    inner join rdates r
    on         d.date < r.date
    order by   date desc
    limit      1)
)
select   min(date) StartDate,
         max(date) EndDate,
         id_type
from     rdates
group by lv, id_type
;

+---------------------+---------------------+---------+
| startdate           |       enddate       | id_type |
+---------------------+---------------------+---------+
| 10.01.2017 07:19:21 | 10.01.2017 07:19:25 |    3    |
| 10.01.2017 07:19:26 | 10.01.2017 07:19:26 |    5    |
| 10.01.2017 07:19:27 | 10.01.2017 07:19:27 |    3    |
| 10.01.2017 07:19:28 | 10.01.2017 07:19:29 |    5    |
| 10.01.2017 07:19:30 | 10.01.2017 07:19:30 |    3    |
| 10.01.2017 07:19:31 | 10.01.2017 07:19:31 |    5    |
| 10.01.2017 07:19:32 | 10.01.2017 07:19:32 |    3    |
| 10.01.2017 07:19:33 | 10.01.2017 07:19:37 |    5    |
+---------------------+---------------------+---------+

Verifique: http://rextester.com/WCOYFP6623

McNets
fonte
5

Aqui está outro método, que é semelhante ao de Evan e Erwin, na medida em que usa o GAL para determinar ilhas. Difere dessas soluções, pois utiliza apenas um nível de aninhamento, sem agrupamento e consideravelmente mais funções de janela:

SELECT
  id_type,
  date AS begin,
  COALESCE(
    LEAD(prev_date) OVER (ORDER BY date ASC),
    last_date
  ) AS end
FROM
  (
    SELECT
      id_type,
      date,
      LAG(date) OVER (ORDER BY date ASC) AS prev_date,
      MAX(date) OVER () AS last_date,
      CASE id_type
        WHEN LAG(id_type) OVER (ORDER BY date ASC)
        THEN 0
        ELSE 1
      END AS is_start
    FROM
      tmp
  ) AS derived
WHERE
  is_start = 1
ORDER BY
  date ASC
;

A is_startcoluna computada no SELECT aninhado marca o início de cada ilha. Além disso, o SELECT aninhado expõe a data anterior de cada linha e a data do último conjunto de dados.

Para linhas que são o início de suas respectivas ilhas, a data anterior efetivamente é a data de término da ilha anterior. É assim que o SELECT principal o usa. Ele pega apenas as linhas que correspondam à is_start = 1condição, e para cada linha retornada que mostra a linha própria datecomo begine a seguinte linha é prev_datecomo end. Como a última linha não possui uma linha seguinte, LEAD(prev_date)retorna um nulo, para o qual a função COALESCE substitui a última data do conjunto de dados.

Você pode jogar com esta solução no dbfiddle .

Ao introduzir colunas adicionais identificando as ilhas, você provavelmente desejará introduzir uma subcláusula PARTITION BY na cláusula OVER de cada função da janela. Por exemplo, se você deseja detectar as ilhas nos grupos definidos por a parent_id, a consulta acima provavelmente terá a seguinte aparência:

SELECT
  parent_id,
  id_type,
  date AS begin,
  COALESCE(
    LEAD(prev_date) OVER (PARTITION BY parent_id ORDER BY date ASC),
    last_date
  ) AS end
FROM
  (
    SELECT
      parent_id,
      id_type,
      date,
      LAG(date) OVER (PARTITION BY parent_id ORDER BY date ASC) AS prev_date,
      MAX(date) OVER (PARTITION BY parent_id) AS last_date,
      CASE id_type
        WHEN LAG(id_type) OVER (PARTITION BY parent_id ORDER BY date ASC)
        THEN 0
        ELSE 1
      END AS is_start
    FROM
      tmp
  ) AS derived
WHERE
  is_start = 1
ORDER BY
  date ASC
;

E se você optar pela solução de Erwin ou Evan, acredito que uma mudança semelhante precisará ser adicionada a ela também.

Andriy M
fonte
5

Mais por interesse acadêmico do que por uma solução prática, você também pode conseguir isso com um agregado definido pelo usuário . Como as outras soluções, isso funcionará mesmo no Postgres 8.4, mas como outros comentaram, atualize, se puder.

O agregado manipula nullcomo se fosse um diferente foo_type, portanto, execuções de nulos teriam o mesmo grp- que pode ou não ser o que você deseja.

create function grp_sfunc(integer[],integer) returns integer[] language sql as $$
  select array[$1[1]+($1[2] is distinct from $2 or $1[3]=0)::integer,$2,1];
$$;
create function grp_finalfunc(integer[]) returns integer language sql as $$
  select $1[1];
$$;
create aggregate grp(integer)(
  sfunc = grp_sfunc
, stype = integer[]
, finalfunc = grp_finalfunc
, initcond = '{0,0,0}'
);
select min(foo_at) begin_at, max(foo_at) end_at, foo_type
from (select *, grp(foo_type) over (order by foo_at) from foo) z
group by grp, foo_type
order by 1;
begin_at | end_at | foo_type
: -------------------- | : -------------------- | -------:
2017-01-10 07:19:21 | 2017-01-10 07:19:25 | 3
2017-01-10 07:19:26 | 2017-01-10 07:19:26 | 5
2017-01-10 07: 19: 27.1 | 2017-01-10 07: 19: 27.1 | 3
2017-01-10 07:19:28 | 2017-01-10 07:19:29 | 5
2017-01-10 07: 19: 30.1 | 2017-01-10 07: 19: 30.1 | 3
2017-01-10 07:19:31 | 2017-01-10 07:19:31 | 5
2017-01-10 07:19:32 | 2017-01-10 07:19:32 | 3
2017-01-10 07: 19: 33.1 | 2017-01-10 07: 19: 37.1 | 5

dbfiddle aqui

Jack diz que tenta topanswers.xyz
fonte
4

Isso pode ser feito RECURSIVE CTEpara passar o "horário de início" de uma linha para a seguinte e alguns preparativos extras (conveniência).

Esta consulta retorna o resultado que você deseja:

WITH RECURSIVE q AS
(
    SELECT
        id_type,
        "date",
        /* We compute next id_type for convenience, plus row_number */
        row_number()  OVER (w) AS rn,
        lead(id_type) OVER (w) AS next_id_type
    FROM
        t
    WINDOW
        w AS (ORDER BY "date") 
)

após a preparação ... parte recursiva

, rec AS 
(
    /* Anchor */
    SELECT
        q.rn,
        q."date" AS "begin",
        /* When next_id_type is different from Look also at **next** row to find out whether we need to mark an end */
        case when q.id_type is distinct from q.next_id_type then q."date" END AS "end",
        q.id_type
    FROM
        q
    WHERE
        rn = 1

    UNION ALL

    /* Loop */
    SELECT
        q.rn,
        /* We keep copying 'begin' from one row to the next while type doesn't change */
        case when q.id_type = rec.id_type then rec.begin else q."date" end AS "begin",
        case when q.id_type is distinct from q.next_id_type then q."date" end AS "end",
        q.id_type
    FROM
        rec
        JOIN q ON q.rn = rec.rn+1
)
-- We filter the rows where "end" is not null, and project only needed columns
SELECT
    "begin", "end", id_type
FROM
    rec
WHERE
    "end" is not null ;

Você pode verificar isso em http://rextester.com/POYM83542

Este método não escala bem. Para uma tabela de 8_641 linhas, são necessários 7s; para uma tabela com o dobro desse tamanho, são necessários 28s. Mais algumas amostras mostram os tempos de execução parecidos com O (n ^ 2).

O método de Evan Carrol leva menos de 1s (ou seja: vá em frente!) E se parece com O (n). As consultas recursivas são absolutamente ineficientes e devem ser consideradas um último recurso.

joanolo
fonte