Trova il conteggio di tutti gli intervalli sovrapposti

Come hai correttamente menzionato, esistono diversi approcci con una complessità variabile inerente alla loro esecuzione. Questo fondamentalmente copre il modo in cui vengono eseguiti e quale implementare effettivamente dipende da quali dati e casi d'uso sono più adatti.

Corrispondenza dell'intervallo di corrente

MongoDB 3.6 $ricerca

L'approccio più semplice può essere impiegato utilizzando la nuova sintassi di $lookup operatore con MongoDB 3.6 che consente una pipeline da dare come espressione per "autounirsi" alla stessa collezione. Questo può sostanzialmente interrogare nuovamente la raccolta per tutti gli elementi in cui è starttime "o" endtime del documento in corso rientra tra gli stessi valori di qualsiasi altro documento, escluso ovviamente l'originale:

db.getCollection('collection').aggregate([
  { "$lookup": {
    "from": "collection",
    "let": {
      "_id": "$_id",
      "starttime": "$starttime",
      "endtime": "$endtime"
    },
    "pipeline": [
      { "$match": {
        "$expr": {
          "$and": [
            { "$ne": [ "$$_id", "$_id" },
            { "$or": [
              { "$and": [
                { "$gte": [ "$$starttime", "$starttime" ] },
                { "$lte": [ "$$starttime", "$endtime" ] }
              ]},
              { "$and": [
                { "$gte": [ "$$endtime", "$starttime" ] },
                { "$lte": [ "$$endtime", "$endtime" ] }
              ]}
            ]},
          ]
        },
        "as": "overlaps"
      }},
      { "$count": "count" },
    ]
  }},
  { "$match": { "overlaps.0": { "$exists": true }  } }
])

Il singolo $lookup esegue il "join" sulla stessa raccolta consentendo di mantenere i valori del "documento corrente" per il "_id" , "starttime" e "endtime" valori rispettivamente tramite il "let" opzione della fase del gasdotto. Queste saranno disponibili come "variabili locali" utilizzando il $$ prefisso nel successivo "pipeline" dell'espressione.

All'interno di questa "tubazione secondaria" utilizzi $match fase della pipeline e $expr operatore di query, che consente di valutare le espressioni logiche del framework di aggregazione come parte della condizione della query. Ciò consente il confronto tra i valori in quanto seleziona nuovi documenti che soddisfano le condizioni.

Le condizioni cercano semplicemente i "documenti elaborati" dove il "_id" il campo non è uguale al "documento corrente", $and dove il "starttime" $or "endtime" i valori del "documento corrente" rientrano tra le stesse proprietà del "documento elaborato". Notando qui che questi così come i rispettivi $gte e $lte gli operatori sono gli "operatori di confronto di aggregazione" e non l'"operatore di query" form, come risultato restituito valutato da $expr deve essere boolean nel contesto. Questo è ciò che fanno effettivamente gli operatori di confronto delle aggregazioni ed è anche l'unico modo per passare i valori per il confronto.

Dal momento che vogliamo solo il "conteggio" delle partite, il $count la fase della pipeline viene utilizzata per farlo. Il risultato del $lookup sarà un array di "elemento singolo" in cui c'era un conteggio o un "array vuoto" in cui non c'era corrispondenza con le condizioni.

Un caso alternativo sarebbe quello di "omettere" il $count fase e consentire semplicemente la restituzione dei documenti corrispondenti. Ciò consente una facile identificazione, ma come "array incorporato nel documento" è necessario essere consapevoli del numero di "sovrapposizioni" che verranno restituite come documenti interi e che ciò non provoca una violazione del limite BSON di 16 MB. Nella maggior parte dei casi questo dovrebbe andare bene, ma per i casi in cui si prevede un numero elevato di sovrapposizioni per un determinato documento questo può essere un caso reale. Quindi è davvero qualcosa di più di cui essere consapevoli.

Il $lookup la fase della pipeline in questo contesto restituirà "sempre" un array nel risultato, anche se vuoto. Il nome della proprietà di output "unione" nel documento esistente sarà "overlaps" come specificato nel "as" proprietà al $lookup fase.

A seguito di $lookup , possiamo quindi eseguire un semplice $match con un'espressione di query regolare che utilizza $exists prova per 0 valore di indice dell'array di output. Dove c'è effettivamente del contenuto nell'array e quindi "sovrappone" la condizione sarà vera e il documento restituito, mostrando il conteggio o i documenti "sovrapposti" secondo la tua selezione.

Altre versioni:query per "unirsi"

Il caso alternativo in cui il tuo MongoDB non ha questo supporto è "unirsi" manualmente emettendo le stesse condizioni di query descritte sopra per ogni documento esaminato:

db.getCollection('collection').find().map( d => {
  var overlaps = db.getCollection('collection').find({
    "_id": { "$ne": d._id },
    "$or": [
      { "starttime": { "$gte": d.starttime, "$lte": d.endtime } },
      { "endtime": { "$gte": d.starttime, "$lte": d.endtime } }
    ]
  }).toArray();

  return ( overlaps.length !== 0 ) 
    ? Object.assign(
        d,
        {
          "overlaps": {
            "count": overlaps.length,
            "documents": overlaps
          }
        }
      )
    : null;
}).filter(e => e != null);

Questa è essenzialmente la stessa logica, tranne per il fatto che in realtà è necessario "tornare al database" per emettere la query in modo che corrisponda ai documenti sovrapposti. Questa volta sono gli "operatori di query" utilizzati per trovare dove si trovano i valori del documento corrente tra quelli del documento elaborato.

Poiché i risultati sono già stati restituiti dal server, non esistono limiti BSON per l'aggiunta di contenuto all'output. Potresti avere limitazioni di memoria, ma questo è un altro problema. In poche parole, restituiamo l'array anziché il cursore tramite .toArray() quindi abbiamo i documenti corrispondenti e possiamo semplicemente accedere alla lunghezza dell'array per ottenere un conteggio. Se non hai effettivamente bisogno dei documenti, utilizza .count() invece di .find() è molto più efficiente poiché non c'è il sovraccarico di recupero del documento.

L'output viene quindi semplicemente unito al documento esistente, dove l'altra importante distinzione è che poiché le tesi sono "interrogazioni multiple" non c'è modo di fornire la condizione che debbano "corrispondere" a qualcosa. Quindi questo ci lascia con la considerazione che ci saranno risultati in cui il conteggio (o la lunghezza dell'array) è 0 e tutto ciò che possiamo fare in questo momento è restituire un null valore che possiamo in seguito .filter() dalla matrice dei risultati. Altri metodi di iterazione del cursore utilizzano lo stesso principio di base per "eliminare" i risultati laddove non li desideriamo. Ma nulla impedisce che la query venga eseguita sul server e questo filtro è "post-elaborazione" in una forma o nell'altra.

Ridurre la complessità

Quindi gli approcci di cui sopra funzionano con la struttura come descritto, ma ovviamente la complessità complessiva richiede che per ogni documento si debba essenzialmente esaminare ogni altro documento nella raccolta per cercare le sovrapposizioni. Pertanto, durante l'utilizzo di $lookup consente una certa "efficienza" nella riduzione delle spese generali di trasporto e risposta, soffre ancora dello stesso problema che stai ancora essenzialmente confrontando ogni documento con tutto.

Una soluzione migliore "dove puoi adattarlo" è invece memorizzare un "valore fisso"* rappresentativo dell'intervallo su ciascun documento. Ad esempio potremmo "presumere" che ci siano solidi periodi di "prenotazione" di un'ora in un giorno per un totale di 24 periodi di prenotazione. Questo "potrebbe" essere rappresentato in qualcosa del tipo:

{ "_id": "A", "booking": [ 10, 11, 12 ] }
{ "_id": "B", "booking": [ 12, 13, 14 ] }
{ "_id": "C", "booking": [ 7, 8 ] }
{ "_id": "D", "booking": [ 9, 10, 11 ] }

Con i dati organizzati in questo modo in cui c'era un indicatore impostato per l'intervallo, la complessità è notevolmente ridotta poiché in realtà è solo una questione di "raggruppamento" sul valore dell'intervallo dall'array all'interno di "booking" proprietà:

db.booking.aggregate([
  { "$unwind": "$booking" },
  { "$group": { "_id": "$booking", "docs": { "$push": "$_id" } } },
  { "$match": { "docs.1": { "$exists": true } } }
])

E l'output:

{ "_id" : 10, "docs" : [ "A", "D" ] }
{ "_id" : 11, "docs" : [ "A", "D" ] }
{ "_id" : 12, "docs" : [ "A", "B" ] }

Questo lo identifica correttamente per il 10 e 11 intervalli entrambi "A" e "D" contengono la sovrapposizione, mentre "B" e "A" sovrapposizione su 12 . Altri intervalli e corrispondenze di documenti sono esclusi tramite lo stesso $exists prova tranne questa volta su 1 index (o se è presente un secondo elemento dell'array) per vedere che c'era "più di un" documento nel raggruppamento, indicando quindi una sovrapposizione.

Questo utilizza semplicemente il $unwind fase della pipeline di aggregazione per "decostruire/denormalizzare" il contenuto dell'array in modo da poter accedere ai valori interni per il raggruppamento. Questo è esattamente ciò che accade nel $group fase in cui la "chiave" fornita è l'ID dell'intervallo di prenotazione e il $push operatore viene utilizzato per "raccogliere" i dati sul documento corrente che è stato trovato in quel gruppo. Il $match è come spiegato in precedenza.

Questo può anche essere ampliato per una presentazione alternativa:

db.booking.aggregate([
  { "$unwind": "$booking" },
  { "$group": { "_id": "$booking", "docs": { "$push": "$_id" } } },
  { "$match": { "docs.1": { "$exists": true } } },
  { "$unwind": "$docs" },
  { "$group": {
    "_id": "$docs",
    "intervals": { "$push": "$_id" }  
  }}
])

Con uscita:

{ "_id" : "B", "intervals" : [ 12 ] }
{ "_id" : "D", "intervals" : [ 10, 11 ] }
{ "_id" : "A", "intervals" : [ 10, 11, 12 ] }

È una dimostrazione semplificata, ma laddove i dati in tuo possesso lo consentirebbero per il tipo di analisi richiesto, questo è l'approccio molto più efficiente. Quindi, se è possibile mantenere la "granularità" da fissare a intervalli "impostati" che possono essere comunemente registrati su ciascun documento, l'analisi e la rendicontazione possono utilizzare quest'ultimo approccio per identificare in modo rapido ed efficiente tali sovrapposizioni.

In sostanza, questo è il modo in cui implementeresti comunque quello che hai sostanzialmente menzionato come un approccio "migliore", e il primo è un "lieve" miglioramento rispetto a ciò che avevi originariamente teorizzato. Scopri quale si adatta effettivamente alla tua situazione, ma questo dovrebbe spiegare l'implementazione e le differenze.