MongoDB
 sql >> Base de données >  >> NoSQL >> MongoDB

Trouver le nombre de tous les intervalles qui se chevauchent

Comme vous le mentionnez correctement, il existe différentes approches avec une complexité variable inhérente à leur exécution. Cela couvre essentiellement la façon dont ils sont effectués et celui que vous implémentez dépend en fait de vos données et de votre cas d'utilisation les mieux adaptés.

Correspondance de la plage actuelle

MongoDB 3.6 $recherche

L'approche la plus simple peut être employée en utilisant la nouvelle syntaxe du $lookup opérateur avec MongoDB 3.6 qui permet un pipeline à donner comme expression pour "s'auto-joindre" à la même collection. Cela peut fondamentalement interroger à nouveau la collection pour tous les éléments où le starttime "ou" endtime du document actuel se situe entre les mêmes valeurs de tout autre document, sans compter l'original bien sûr :

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

Le seul $lookup effectue le "join" sur la même collection permettant de conserver les valeurs "current document" pour le "_id" , "starttime" et "endtime" valeurs respectivement via le "let" option de l'étape du pipeline. Celles-ci seront disponibles en tant que "variables locales" en utilisant le $$ préfixe dans le "pipeline" suivant de l'expression.

Dans ce "sous-pipeline", vous utilisez le $match étape du pipeline et $expr opérateur de requête, qui vous permet d'évaluer les expressions logiques du cadre d'agrégation dans le cadre de la condition de requête. Cela permet la comparaison entre les valeurs car il sélectionne de nouveaux documents correspondant aux conditions.

Les conditions recherchent simplement les "documents traités" où le "_id" le champ n'est pas égal au "document actuel", $and où soit le "starttime" $or "endtime" valeurs du "document courant" se situent entre les mêmes propriétés du "document traité". Notant ici que ceux-ci ainsi que les $gte et $lte les opérateurs sont les "opérateurs de comparaison d'agrégation" et non l'"opérateur de requête" formulaire, comme le résultat renvoyé évalué par $expr doit être boolean Dans le contexte. C'est ce que font réellement les opérateurs de comparaison d'agrégation, et c'est aussi le seul moyen de transmettre des valeurs à comparer.

Puisque nous ne voulons que le "compte" des correspondances, le $count l'étape du pipeline est utilisée pour ce faire. Le résultat de l'ensemble $lookup sera un tableau "à élément unique" où il y avait un nombre, ou un "tableau vide" où il n'y avait pas de correspondance avec les conditions.

Un autre cas serait "d'omettre" le $count et laissez simplement les documents correspondants revenir. Cela permet une identification facile, mais en tant que "tableau intégré dans le document", vous devez être conscient du nombre de "chevauchements" qui seront renvoyés sous forme de documents entiers et que cela n'entraîne pas une violation de la limite BSON de 16 Mo. Dans la plupart des cas, cela devrait convenir, mais dans les cas où vous vous attendez à un grand nombre de chevauchements pour un document donné, cela peut être un cas réel. C'est donc quelque chose de plus dont il faut être conscient.

Le $lookup l'étape de pipeline dans ce contexte renverra "toujours" un tableau dans le résultat, même s'il est vide. Le nom de la propriété de sortie "merging" dans le document existant sera "overlaps" comme spécifié dans le "as" propriété à la $lookup scène.

Suite à la $lookup , on peut alors faire un simple $match avec une expression de requête régulière utilisant le $exists teste le 0 valeur d'index du tableau de sortie. Lorsqu'il y a réellement du contenu dans le tableau et donc "chevauchement", la condition sera vraie et le document renvoyé, montrant soit le nombre, soit les documents "chevauchant" selon votre sélection.

Autres versions - Requêtes pour "joindre"

Le cas alternatif où votre MongoDB n'a pas cette prise en charge est de "se joindre" manuellement en émettant les mêmes conditions de requête décrites ci-dessus pour chaque document examiné :

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

C'est essentiellement la même logique, sauf que nous devons en fait retourner "à la base de données" afin d'émettre la requête pour faire correspondre les documents qui se chevauchent. Cette fois, ce sont les "opérateurs de requête" utilisés pour trouver où les valeurs actuelles du document se situent entre celles du document traité.

Étant donné que les résultats sont déjà renvoyés par le serveur, il n'y a aucune restriction de limite BSON sur l'ajout de contenu à la sortie. Vous pourriez avoir des restrictions de mémoire, mais c'est un autre problème. En termes simples, nous renvoyons le tableau plutôt que le curseur via .toArray() nous avons donc les documents correspondants et pouvons simplement accéder à la longueur du tableau pour obtenir un décompte. Si vous n'avez pas réellement besoin des documents, utilisez .count() au lieu de .find() est beaucoup plus efficace puisqu'il n'y a pas de surcharge de récupération de document.

La sortie est ensuite simplement fusionnée avec le document existant, où l'autre distinction importante est que, puisque les thèses sont des "requêtes multiples", il n'y a aucun moyen de fournir la condition qu'elles doivent "correspondre" à quelque chose. Donc, cela nous laisse avec l'idée qu'il y aura des résultats où le nombre (ou la longueur du tableau) est 0 et tout ce que nous pouvons faire pour le moment est de renvoyer un null valeur que nous pourrons plus tard .filter() du tableau de résultat. D'autres méthodes d'itération du curseur utilisent le même principe de base consistant à « rejeter » les résultats là où nous n'en voulons pas. Mais rien n'empêche l'exécution de la requête sur le serveur et ce filtrage est un "post-traitement" sous une forme ou une autre.

Réduire la complexité

Ainsi, les approches ci-dessus fonctionnent avec la structure décrite, mais bien sûr, la complexité globale exige que pour chaque document, vous deviez essentiellement examiner tous les autres documents de la collection afin de rechercher les chevauchements. Par conséquent, tout en utilisant $lookup permet une certaine "efficacité" en réduisant les frais généraux de transport et de réponse, il souffre toujours du même problème que vous comparez toujours essentiellement chaque document à tout.

Une meilleure solution "où vous pouvez l'adapter" est de stocker à la place une "valeur dure"* représentative de l'intervalle sur chaque document. Par exemple, nous pourrions "présumer" qu'il y a des périodes de "réservation" solides d'une heure dans une journée pour un total de 24 périodes de réservation. Ce "pourrait" être représenté par quelque chose comme :

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

Avec des données organisées comme ça où il y avait un indicateur défini pour l'intervalle, la complexité est considérablement réduite car il s'agit en réalité de "regrouper" la valeur de l'intervalle à partir du tableau dans le "booking" propriété :

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

Et le résultat :

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

Cela identifie correctement cela pour le 10 et 11 intervalles les deux "A" et "D" contenir le chevauchement, tandis que "B" et "A" chevauchement sur 12 . Les autres intervalles et documents correspondants sont exclus via le même $exists test sauf cette fois sur le 1 index (ou deuxième élément de tableau étant présent) afin de voir qu'il y avait "plus d'un" document dans le groupement, indiquant ainsi un chevauchement.

Cela utilise simplement le $unwind étape de pipeline d'agrégation pour "déconstruire/dénormaliser" le contenu du tableau afin que nous puissions accéder aux valeurs internes pour le regroupement. C'est exactement ce qui se passe dans le $group étape où la "clé" fournie est l'identifiant de l'intervalle de réservation et le $push L'opérateur est utilisé pour "collecter" des données sur le document courant qui a été trouvé dans ce groupe. Le $match est comme expliqué précédemment.

Cela peut même être étendu pour une présentation alternative :

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

Avec sortie :

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

C'est une démonstration simplifiée, mais là où les données dont vous disposez le permettraient pour le type d'analyse requise, c'est l'approche la plus efficace. Donc, si vous pouvez conserver la "granularité" à fixer à des intervalles "définis" qui peuvent être couramment enregistrés sur chaque document, l'analyse et le reporting peuvent utiliser cette dernière approche pour identifier rapidement et efficacement ces chevauchements.

Essentiellement, c'est ainsi que vous mettriez en œuvre ce que vous avez essentiellement mentionné comme une "meilleure" approche de toute façon, et la première étant une "légère" amélioration par rapport à ce que vous aviez théorisé à l'origine. Voyez lequel correspond réellement à votre situation, mais cela devrait expliquer la mise en œuvre et les différences.