Início / coding / Perguntas / 79489212
Accepted
gherkins
Asked: 2025-03-06 19:38:05 +0800 CST

Consultar objetos sobrepondo intervalos de tempo em várias categorias

  • 772
  • 10M+ Marcadores (Intervalos de tempo em certos)
  • Mais de 300 mil objetos referenciados (vídeos)

Marcadores com uma estrutura como esta:

{
  id: 123,
  category: 2,
  object: 'A',
  start: 10,
  end: 25
}

...resultando em intervalos ao longo das diferentes categorias, como:

category-1: ----------[===========]---------------------------- ref-object: A
category-1: --------------------------[====================]--- ref-object: A
category-1: ------------------[============================]--- ref-object: A
category-1: -----------------[==========================]------ ref-object: C
category-1: ------------------------------[================]--- ref-object: C

category-2: ----[===================]-------------------------- ref-object: A
category-2: -----[==========================]------------------ ref-object: B
category-2: -----[====================]------------------------ ref-object: C
category-2: -------------------------[=================]------- ref-object: C
category-2: ------------[===================================]-- ref-object: C

category-3: ----------------[=============]-------------------- ref-object: A
category-3: ----[===================================]---------- ref-object: A
category-3: -------[=======================================]--- ref-object: B
category-3: ----------------------------[====]----------------- ref-object: C
category-3: -------------[=================]------------------- ref-object: C

Agora para responder algo como isto:

Encontre todos os objetos, tendo intervalos sobrepostos(!) category 1e category 2
idealmente ordenados pela soma do tempo sobreposto

Eu consigo pensar nesses passos

  • consulta: comece com uma categoria, busque todos os marcadores nessa categoria
  • código: reduza os intervalos para alguns intervalos de tempo maiores (remova intervalos de tempo redundantes)
  • consulta: buscar marcadores da próxima categoria que correspondam a um desses intervalos de tempo
  • código: reduza os intervalos combinados para alguns intervalos de tempo maiores (remova intervalos de tempo redundantes)
  • [...]
  • código: calcular o período de tempo coberto por item e classificar de acordo

Isso é algo que você gostaria de fazer em SQL?

Existe um nome para esse tipo de consulta? (Essas não são exatamente consultas de intervalo, são?)

Existe um banco de dados com recursos integrados nesse caso, dada a quantidade de dados?

Atualmente, todos os dados são armazenados dentro de um índice Apache SOLR, mas isso também pode se tornar Elasticsearch, InfluxDB etc.

sql

1 respostas

  1. Best Answer

    Isso é algo que você gostaria de fazer em SQL?

    Claro! E como é bem simples, por que não tentar?

    with
    -- Where do segments intersect each other? 
    cuts as
    (
        select category, object, start t from m
        union -- Without "all" to deduplicate.
        select category, object, "end" from m
    ),
    -- Give those cuts an index, and compute the stop of the subsegment they start
    -- (the last cut having no next cut, will get a null stop:
    --  thus it's the only one that will not be considered a segment in the following joins)
    icuts as
    (
        select
            row_number() over () id,
            category, object,
            t ts, lead(t) over w te, lead(t) over w - t + 1 len
        from cuts
        window w as (partition by category, object order by t)
    ),
    -- Atomic marker segments: parts of markers that cannot be split anymore.
    mseg as
    (
        select m.id mid, m.category, m.object, s.id sid
        from m join icuts s on (s.category, s.object) = (m.category, m.object) and m.start <= s.ts and m.end >= s.te
    ),
    overl as
    (
        select sid, count(1) noverlaps
        from mseg
        group by sid
        having count(1) > 1
    )
select category, object, sum(len) totaloverlap
from overl o join icuts s on s.id = o.sid
group by 1, 2
order by 3 desc, 1, 2;

    Retornaria do seu exemplo (contando o [e ]nos marcadores, portanto o último marcador do seu exemplo, [====], é considerado de duração 6) :

    categoria objeto sobreposição total
    2 C 34
    1 UM 27
    1 C 15
    3 UM 15
    3 C 4

    ( aqui está o violino se você quiser brincar com ele)

    10 milhões não seria tão grande para um servidor PostgreSQL, mas não há como saber sem testar (… e eu vou preservar o DBFiddle de tal carga). No entanto, estou convencido de que ele rodará mais rápido do que com roundtrips do banco de dados para o aplicativo .

    Ainda há espaço para melhorias: todos (category, object)os pares podem ser reduzidos a um único integer;
    e os CTEs podem ser despejados em tabelas e então indexados.

    • 1

relate perguntas