Indices fonctionnels pour des requêtes ultrarapides sur les tables de relations de plusieurs à plusieurs

Supposons que vous ayez une application qui permette aux utilisateurs d'écrire des articles et de les commenter. (Attendez...  ça me dit quelque chose...)

L'objectif est de répertorier, pour un utilisateur donné, tous les messages publiés avec lesquels il a interagi, c'est-à-dire dont il est l'auteur ou qu'il a commentés. Comment faites-vous cela aussi vite que possible?

Voici à quoi pourraient ressembler les définitions de notre classe %Persistent comme point de départ (les définitions de stockage sont importantes, mais omises par souci de concision):

Class DC.Demo.Post Extends %Persistent
{

Property Title As %String(MAXLEN = 255) [ Required ];
Property Body As %String(MAXLEN = "") [ Required ];
Property Author As DC.Demo.Usr [ Required ];
Property Draft As %Boolean [ InitialExpression = 1, Required ];
}

Class DC.Demo.Usr Extends %Persistent
{

Property Name As %String [ Required ];
}

Class DC.Demo.Comment Extends %Persistent
{

Property Post As DC.Demo.Post [ Required ];
Property Usr As DC.Demo.Usr [ Required ];
Property Comment As %String(MAXLEN = "") [ Required ];
}

Et notre requête, comme point de départ:

select ID from DC_Demo.Post where (Author = ? or ID in (select distinct Post from DC_Demo.Comment where Usr = ?)) and Draft = 0

L' approche naïve consisterait simplement à:

• Ajoutez des indices bitmap sur Author et Draft dans DC.Demo.Post.
• Ajoutez un index standard sur (Usr, Post) dans DC.Démo.Commentaire..

Et ce n'est pas du tout une mauvaise approche! Pour certains cas d'utilisation, elle peut même être " suffisante ". Que va faire IRIS SQL sous le capot ? Nous pouvons examiner le plan de requête:

 Générer un flux de valeurs idkey en utilisant la combinaison multi-index:
     ((bitmap index DC_Demo.Post.Draft) INTERSECT ((bitmap index DC_Demo.Post.Author) UNION (bitmap index DC_Demo.Post.Draft)))
 Pour chaque valeur d'idkey:
     Affichage de la ligne.

Sous-requête C:
 Lecture de la carte d'index DC_Demo.Comment.UsrPost, en utilisant l'Usr et le Post donnés, et en bouclant sur l'ID.
 Pour chaque ligne:
     Détermination du résultat de la sous-requête.

Ce n'est pas dramatique. Supposons qu'il y ait 50000 publications et que chaque utilisateur ait commenté 500 d'entre elles en moyenne. Combien de références globales cette requête implique-t-elle? Eh bien, au minimum, trois pour les index bitmap, et environ 500 dans la sous-requête (itération sur l'index UsrPost). Il est clair que la sous-requête est le goulot d'étranglement. Comment pouvons-nous la rendre plus rapide?

La réponse est d'utiliser un index fonctionnel (une sous-classe de %Library.FunctionalIndex) avec la %FIND condition de prédicat (et une sous-classe de %SQL.AbstractFind). Notre index fonctionnel sera défini dans la classe Comment (commentaires), mais ne contiendra pas les identifiants des commentaires comme le ferait un index bitmap classique. Au lieu de cela, pour chaque utilisateur, il aura un bitmap d'identifiants de Post pour lesquels cet utilisateur a au moins un commentaire. Nous pouvons ensuite combiner très efficacement cette image bitmap avec d'autres conditions indexées par image bitmap dans la table Post. Il est évident que cela entraîne une certaine surcharge pour l'insertion/mise à jour/suppression de nouveaux commentaires, mais l'avantage en termes de performances pour les lectures peut la compenser.

Un index fonctionnel doit définir le comportement de l'index pour les opérations d'insertion, de mise à jour et de suppression, et mettre en œuvre quelques autres méthodes (purge, début de tri, fin de tri). Une Une implémentation %SQL.AbstractFind doit mettre en œuvre des méthodes pour parcourir et récupérer des fragments d'index bitmap. Pour s'amuser, nous utiliserons une implémentation générique %SQL.AbstractFind qui examine une structure d'index bitmap standard (avec une référence globale à son nœud racine).

Remarque - si vous ne savez pas ce qu'est un "fragment de bitmap" ou si vous avez l'impression que tout cela est du Chinois, nous vous conseillons de lire la documentation  sur les index de bitmap, en particulier les parties relatives à leur structure et à leur manipulation.

Passons au code, DC.Demo.ExistenceIndex est notre index fonctionnel:

Include %IFInclude
/// Données:
/// 
/// <code>
/// Class Demo.ClassC Extends %Persistent
/// {
/// Properiété PropA As Demo.ClassA;
/// Properiété PropB As Demo.ClassB;
/// Index BValuesForA On (PropA, PropB) As DC.Demo.ExistenceIndex;
/// }
/// </code>
/// 
/// Appel à partir de SQL comme suit, étant donné une valeur de PropA de 21532, pour retourner les valeurs de PropB associées à PropA=21532 dans ClassB:
/// <code>
/// selectionner * de Demo.ClassC où ID %FIND Demo.ClassB_BValuesForAFind(21532) et <other-bitmap-index-conditions>
/// </code>
Class DC.Demo.ExistenceIndex Extends %Library.FunctionalIndex [ System = 3 ]
{

/// Retourne une sous-classe %SQL.AbstractFind appropriée pour cet index fonctionnel
ClassMethod Find(pSearch As %Binary) As %Library.Binary [ CodeMode = generator, ServerOnly = 1, SqlProc ]
{
    If (%mode '= "method") {
        Set tIdxGlobal = ..IndexLocationForCompile(%class,%property)
        Set name = $Name(@tIdxGlobal@("id"))
        Set name = $Replace(name,$$$QUOTE("id"),"pSearch")
        $$$GENERATE(" Quit ##class(DC.Demo.ReferenceFind).%New($Name("_name_"))")
    }
}

/// Retrouve un "true" s'il existe un enregistrement avec (prop1val, prop2val).
ClassMethod Exists(prop1val, prop2val) [ CodeMode = generator, ServerOnly = 1 ]
{
    If (%mode '= "method") {
        Set indexProp1 = $$$comSubMemberKeyGet(%class,$$$cCLASSindex,%property,$$$cINDEXproperty,1,$$$cINDEXPROPproperty)
        Set indexProp2 = $$$comSubMemberKeyGet(%class,$$$cCLASSindex,%property,$$$cINDEXproperty,2,$$$cINDEXPROPproperty)
        Set table = $$$comClassKeyGet(%class,$$$cCLASSsqlschemaname)_"."_$$$comClassKeyGet(%class,$$$cCLASSsqltablename)
        Set prop1 = $$$comMemberKeyGet(%class,$$$cCLASSproperty,indexProp1,$$$cPROPsqlfieldname)
        If (prop1 = "") {
            Set prop1 = indexProp1
        }
        Set prop2 = $$$comMemberKeyGet(%class,$$$cCLASSproperty,indexProp2,$$$cPROPsqlfieldname)
        If (prop2 = "") {
            Set prop2 = indexProp2
        }
        $$$GENERATE(" &sql(select top 1 1 from "_table_" where "_prop1_" = :prop1val and "_prop2_" = :prop2val)")
        $$$GENERATE(" Quit (SQLCODE = 0)")
    }
}

/// Cette méthode est invoquée lorsqu'une nouvelle instance d'une classe est insérée dans la base de données
ClassMethod InsertIndex(pID As %CacheString, pArg... As %Binary) [ CodeMode = generator, ServerOnly = 1 ]
{
    If (%mode '= "method") {
        Set tIdxGlobal = ..IndexLocationForCompile(%class,%property)
        Set name = $Name(@tIdxGlobal@("id","chunk"))
        Set name = $Replace(name,$$$QUOTE("chunk"),"chunk")
        
        $$$GENERATE(" If ($Get(pArg(1)) '= """") && ($Get(pArg(2)) '= """") { ")
        $$$GENERATE("  $$$IFBITOFFPOS(pArg(2),chunk,position)")
        $$$GENERATE("  Set $Bit("_$Replace(name,$$$QUOTE("id"),"pArg(1)")_",position) = 1")
        $$$GENERATE(" }")
    }
}

/// Cette méthode est invoquée lorsqu'une instance existante d'une classe est mise à jour.
ClassMethod UpdateIndex(pID As %CacheString, pArg... As %Binary) [ CodeMode = generator, ServerOnly = 1 ]
{
    If (%mode '= "method") {
        Set tIdxGlobal = ..IndexLocationForCompile(%class,%property)
        Set name = $Name(@tIdxGlobal@("id","chunk"))
        Set name = $Replace(name,$$$QUOTE("chunk"),"chunk")
        $$$GENERATE(" If ($Get(pArg(3)) '= """") && ($Get(pArg(4)) '= """") { ")
        $$$GENERATE("  $$$IFBITOFFPOS(pArg(4),chunk,position)")
        $$$GENERATE("  Set $Bit("_$Replace(name,$$$QUOTE("id"),"pArg(3)")_",position) = .."_%property_"Exists(pArg(3),pArg(4))")
        $$$GENERATE(" }")
        
        $$$GENERATE(" If ($Get(pArg(1)) '= """") && ($Get(pArg(2)) '= """") { ")
        $$$GENERATE("  $$$IFBITOFFPOS(pArg(2),chunk,position)")
        $$$GENERATE("  Set $Bit("_$Replace(name,$$$QUOTE("id"),"pArg(1)")_",position) = 1")
        $$$GENERATE(" }")
    }
}

/// Cette méthode est invoquée lorsqu'une instance existante d'une classe est supprimée.
ClassMethod DeleteIndex(pID As %CacheString, pArg... As %Binary) [ CodeMode = generator, ServerOnly = 1 ]
{
    If (%mode '= "method") {
        Set tIdxGlobal = ..IndexLocationForCompile(%class,%property)
        Set name = $Name(@tIdxGlobal@("id","chunk"))
        Set name = $Replace(name,$$$QUOTE("chunk"),"chunk")
        $$$GENERATE(" If ($Get(pArg(1)) '= """") && ($Get(pArg(2)) '= """") { ")
        $$$GENERATE("  $$$IFBITOFFPOS(pArg(2),chunk,position)")
        $$$GENERATE("  Set $Bit("_$Replace(name,$$$QUOTE("id"),"pArg(1)")_",position) = .."_%property_"Exists(pArg(1),pArg(2))")
        $$$GENERATE(" }")
    }
}

/// Méthode auxiliaire permettant d'obtenir la référence globale pour le stockage d'un index donné.
ClassMethod IndexLocationForCompile(pClassName As %String, pIndexName As %String) As %String
{
    Set tStorage = ##class(%Dictionary.ClassDefinition).%OpenId(pClassName).Storages.GetAt(1).IndexLocation
    Quit $Name(@tStorage@(pIndexName))
}

/// Purge l'index
ClassMethod PurgeIndex() [ CodeMode = generator, ServerOnly = 1 ]
{
    If (%mode '= "method") {
        Set tIdxGlobal = ..IndexLocationForCompile(%class,%property)
        $$$GENERATE(" Kill " _ tIdxGlobal)
    }
}

/// Appelle SortBegin avant les opérations de masse
ClassMethod SortBeginIndex() [ CodeMode = generator, ServerOnly = 1 ]
{
    If (%mode '= "method") {
        Set tIdxGlobal = ..IndexLocationForCompile(%class,%property)
        // No-op
        $$$GENERATE(" Quit")
    }
}

/// Appelle SortEnd après les opérations de masse
ClassMethod SortEndIndex(pCommit As %Integer = 1) [ CodeMode = generator, ServerOnly = 1 ]
{
    If (%mode '= "method") {
        Set tIdxGlobal = ..IndexLocationForCompile(%class,%property)
        // No-op
        $$$GENERATE(" Quit")
    }
}

}

DC.Demo.ReferenceFind est notre implémentation générique de %SQL.AbstractFind qui permet de visualiser un tableau de fragments de cartes bitmap:

/// Utility class to wrap use of %SQL.AbstractFind against a bitmap index global reference
Class DC.Demo.ReferenceFind Extends %SQL.AbstractFind [ System = 3 ]
{

/// Référence globale à itérer sur / prendre en compte pour les méthodes d'opération %SQL.AbstractFind %FIND
Property reference As %String [ Private ];
Method %OnNew(pReference As %String) As %Status [ Private, ServerOnly = 1 ]
{
    Set ..reference = pReference
    Quit $$$OK
}

Method NextChunk(ByRef pChunk As %Integer = "") As %Binary
{
    Set pChunk=$Order(@i%reference@(pChunk),1,tChunkData)
    While pChunk'="",$bitcount(tChunkData)=0 {
        Set pChunk=$Order(@i%reference@(pChunk),1,tChunkData)
    }
    Return $Get(tChunkData)
}

Method PreviousChunk(ByRef pChunk As %Integer = "") As %Binary
{
    Set pChunk=$Order(@i%reference@(pChunk),-1,tChunkData)
    While pChunk'="",$bitcount(tChunkData)=0 {
        Set pChunk=$Order(@i%reference@(pChunk),-1,tChunkData)
    }
    Return $Get(tChunkData)
}

Method GetChunk(pChunk As %Integer) As %Binary
{
    If $Data(@i%reference@(pChunk),tChunkData) {
        Return tChunkData
    } Else {
        Return ""
    }
}

}

Ainsi, DC.Demo.Comment ressemble maintenant à ceci, avec deux indices bitmap ajoutés (et les clés externes appropriées pour faire bonne mesure).:

Class DC.Demo.Comment Extends %Persistent
{

Property Post As DC.Demo.Post [ Required ];
Property Usr As DC.Demo.Usr [ Required ];
Property Comment As %String(MAXLEN = "") [ Required ];
Index Usr On Usr [ Type = bitmap ];
Index Post On Post [ Type = bitmap ];
Index UserPosts On (Usr, Post) As DC.Demo.ExistenceIndex;
ForeignKey UsrKey(Usr) References DC.Demo.Usr();
ForeignKey PostKey(Post) References DC.Demo.Post() [ OnDelete = cascade ];
}

Notre requête SQL devient alors:

select ID from DC_Demo.Post where (Author = ? or ID %FIND DC_Demo.Comment_UserPostsFind(?)) and Draft = 0

Et le plan de requête devient:

 Générer un flux de valeurs idkey en utilisant la combinaison multi-index:
     ((bitmap index DC_Demo.Post.Draft) INTERSECT ((bitmap index DC_Demo.Post.Author) UNION (given bitmap filter for DC_Demo.Post.%ID)))
 Pour chaque valeur d'idkey:
     Afficher la ligne.

Combien de références globales y a-t-il maintenant ? Une pour Author bitmap, une pour Draft bitmap, et une pour le nœud d'index de bitmap "posts for a given user" dans DC.Demo.Comment. Désormais, la liste "Quels sont les publications auxquelles j'ai participé?" ne sera pas (autant) ralentie si vous commentez de plus en plus!

Avertissement : malheureusement, la communauté des développeurs n'est pas réellement soutenue par InterSystems IRIS, vous ne devriez donc probablement pas faire autant de commentaires.