Finden Sie die Anzahl aller überlappenden Intervalle

Wie Sie richtig erwähnen, gibt es verschiedene Ansätze mit unterschiedlicher Komplexität, die ihrer Ausführung inhärent sind. Dies deckt im Wesentlichen ab, wie sie durchgeführt werden, und welche Sie tatsächlich implementieren, hängt davon ab, für welche Daten und Anwendungsfälle Sie sich am besten eignen.

Aktuelle Reichweitenübereinstimmung

MongoDB 3.6 $lookup

Der einfachste Ansatz kann mit der neuen Syntax des verwendet werden $nachschlagen Operator mit MongoDB 3.6, der eine Pipeline zulässt als Ausdruck für "selbst beitreten" zu derselben Sammlung angegeben werden. Dies kann die Sammlung grundsätzlich erneut nach Elementen abfragen, bei denen die starttime "oder" Endzeit des aktuellen Dokuments zwischen die gleichen Werte jedes anderen Dokuments fällt, natürlich nicht das Original:

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 }  } }
])

Der einzelne $lookup führt den "Join" für dieselbe Sammlung durch, sodass Sie die Werte des "aktuellen Dokuments" für "_id" beibehalten können , "Startzeit" und "Endzeit" Werte jeweils über das "let" Option der Pipeline-Phase. Diese werden als "lokale Variablen" mit dem $$ verfügbar sein Präfix im nachfolgenden "pipeline" des Ausdrucks.

Innerhalb dieser „Sub-Pipeline“ verwenden Sie den $match Pipeline-Stufe und $expr Abfrageoperator, mit dem Sie logische Ausdrücke des Aggregationsframeworks als Teil der Abfragebedingung auswerten können. Dies ermöglicht den Vergleich zwischen Werten, wenn neue Dokumente ausgewählt werden, die den Bedingungen entsprechen.

Die Bedingungen suchen einfach nach den "bearbeiteten Dokumenten", bei denen die "_id" Feld ist nicht gleich dem "aktuellen Dokument", $and wobei entweder die "starttime" $or "Endzeit" Werte des "aktuellen Dokuments" zwischen die gleichen Eigenschaften des "verarbeiteten Dokuments" fallen. Beachten Sie hierbei, dass diese sowie die jeweiligen $gte und $lte Operatoren sind die "Aggregationsvergleichsoperatoren" und nicht der "Abfrageoperator" Form, als das zurückgegebene Ergebnis, ausgewertet von $expr muss boolean sein im Zusammenhang. Das ist es, was die Aggregationsvergleichsoperatoren tatsächlich tun, und es ist auch die einzige Möglichkeit, Werte zum Vergleich zu übergeben.

Da wir nur die "Zählung" der Übereinstimmungen wollen, ist der $count Dazu wird die Pipeline-Stufe verwendet. Das Ergebnis des gesamten $lookup wird ein "einzelnes Element"-Array sein, wenn es eine Anzahl gab, oder ein "leeres Array", wenn es keine Übereinstimmung mit den Bedingungen gab.

Ein alternativer Fall wäre das „Weglassen“ von $count Schritt und lassen Sie die passenden Dokumente einfach zurückkommen. Dies ermöglicht eine einfache Identifizierung, aber als „in das Dokument eingebettetes Array“ müssen Sie darauf achten, wie viele „Überschneidungen“ als ganze Dokumente zurückgegeben werden und dass dies nicht zu einer Verletzung der BSON-Grenze von 16 MB führt. In den meisten Fällen sollte dies in Ordnung sein, aber in Fällen, in denen Sie eine große Anzahl von Überschneidungen für ein bestimmtes Dokument erwarten, kann dies ein echter Fall sein. Es ist also wirklich etwas, dessen man sich bewusst sein sollte.

Der $lookup Die Pipeline-Stufe in diesem Kontext gibt "immer" ein Array als Ergebnis zurück, auch wenn es leer ist. Der Name der Ausgabeeigenschaft, die in das vorhandene Dokument "zusammengeführt" wird, lautet "overlaps" wie im "as" angegeben -Eigenschaft zu $lookup Stufe.

Folgen Sie dem $lookup , können wir dann einen einfachen $match durchführen mit einem regulären Abfrageausdruck, der $exists verwendet auf 0 testen Indexwert des Ausgabearrays. Wo tatsächlich etwas Inhalt im Array vorhanden ist und sich daher "überschneidet", ist die Bedingung wahr und das Dokument wird zurückgegeben, wobei entweder die Anzahl oder die "überlappenden" Dokumente gemäß Ihrer Auswahl angezeigt werden.

Andere Versionen - Anfragen zum "Beitreten"

Der alternative Fall, in dem Ihrer MongoDB diese Unterstützung fehlt, ist das manuelle "Beitreten", indem Sie für jedes untersuchte Dokument dieselben Abfragebedingungen wie oben beschrieben ausgeben:

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);

Dies ist im Wesentlichen die gleiche Logik, außer dass wir tatsächlich „zurück zur Datenbank“ gehen müssen, um die Abfrage zum Abgleich der sich überschneidenden Dokumente auszugeben. Diesmal sind es die "Abfrageoperatoren", die verwendet werden, um herauszufinden, wo die aktuellen Dokumentwerte zwischen denen des verarbeiteten Dokuments liegen.

Da die Ergebnisse bereits vom Server zurückgegeben werden, gibt es keine BSON-Beschränkung für das Hinzufügen von Inhalt zur Ausgabe. Möglicherweise haben Sie Speicherbeschränkungen, aber das ist ein anderes Problem. Einfach ausgedrückt geben wir das Array und nicht den Cursor über .toArray() zurück Wir haben also die übereinstimmenden Dokumente und können einfach auf die Array-Länge zugreifen, um eine Zählung zu erhalten. Wenn Sie die Dokumente nicht wirklich benötigen, verwenden Sie .count() statt .find() ist weitaus effizienter, da der Overhead für das Abrufen von Dokumenten entfällt.

Die Ausgabe wird dann einfach mit dem vorhandenen Dokument zusammengeführt, wobei der andere wichtige Unterschied darin besteht, dass es keine Möglichkeit gibt, die Bedingung bereitzustellen, dass sie etwas „übereinstimmen“ müssen, da es sich bei Thesen um „mehrere Abfragen“ handelt. Dies lässt uns also mit der Überlegung zurück, dass es Ergebnisse geben wird, bei denen die Anzahl ( oder Array-Länge ) 0 ist und alles, was wir zu diesem Zeitpunkt tun können, ist ein null zurückzugeben Wert, den wir später .filter() können aus dem Ergebnisarray. Andere Methoden zum Iterieren des Cursors verwenden das gleiche Grundprinzip des "Verwerfens" von Ergebnissen, wo wir sie nicht wollen. Aber nichts hindert die Abfrage daran, auf dem Server ausgeführt zu werden, und diese Filterung ist in irgendeiner Form eine "Nachbearbeitung".

Reduzierung der Komplexität

Die obigen Ansätze funktionieren also mit der beschriebenen Struktur, aber natürlich erfordert die Gesamtkomplexität, dass Sie für jedes Dokument im Wesentlichen jedes andere Dokument in der Sammlung untersuchen müssen, um nach Überschneidungen zu suchen. Daher bei Verwendung von $lookup ermöglicht eine gewisse "Effizienz" Bei der Reduzierung des Transport- und Antwortaufwands leidet es immer noch unter dem gleichen Problem, dass Sie im Wesentlichen immer noch jedes Dokument mit allem vergleichen.

Eine bessere Lösung "wo man es passend machen kann" besteht darin, stattdessen einen "harten Wert"* zu speichern, der das Intervall auf jedem Dokument darstellt. Beispielsweise könnten wir "annehmen", dass es feste "Buchungs"-Perioden von einer Stunde innerhalb eines Tages für insgesamt 24 Buchungsperioden gibt. Dieses "könnte" etwa so dargestellt werden:

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

Mit Daten, die so organisiert sind, dass es einen gesetzten Indikator für das Intervall gibt, wird die Komplexität stark reduziert, da es wirklich nur eine Frage der "Gruppierung" nach dem Intervallwert aus dem Array innerhalb des "booking" ist Eigenschaft:

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

Und die Ausgabe:

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

Das identifiziert das für 10 korrekt und 11 Intervalle beide "A" und "D" enthalten die Überlappung, während "B" und "A" überlappen sich auf 12 . Andere Intervalle und übereinstimmende Dokumente werden über denselben $exists außer diesmal auf 1 testen index ( oder das zweite Array-Element ist vorhanden ), um zu sehen, dass es "mehr als ein" Dokument in der Gruppierung gab, was auf eine Überschneidung hinweist.

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

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