introduction
J'ai présenté ce rapport en anglais lors de la conférence GopherCon Russia 2019 à Moscou et en russe lors d'une rencontre à Nijni Novgorod. Nous parlons d'un index bitmap - moins courant que le B-tree, mais non moins intéressant. Partage discours à la conférence en anglais et transcriptions de textes en russe.
Nous verrons comment fonctionne un index bitmap, quand il est meilleur, quand il est pire que les autres index et dans quels cas il est nettement plus rapide qu'eux ; Voyons quels SGBD populaires ont déjà des index bitmap ; Essayons d'écrire le nôtre dans Go. Et « pour le dessert », nous utiliserons des bibliothèques toutes faites pour créer notre propre base de données spécialisée ultra-rapide.
J'espère vraiment que mes travaux vous seront utiles et intéressants. Aller!
introduction
Salut tout le monde! Il est six heures du soir et nous sommes tous très fatigués. C’est le bon moment pour parler de la théorie ennuyeuse des index de bases de données, n’est-ce pas ? Ne vous inquiétez pas, j'aurai quelques lignes de code source ici et là. 🙂
Blague à part, le rapport regorge d’informations et nous n’avons pas beaucoup de temps. Alors, commençons.
Aujourd'hui, je vais parler des points suivants :
- que sont les index ;
- qu'est-ce qu'un index bitmap ;
- où il est utilisé et où il n'est PAS utilisé et pourquoi ;
- implémentation simple dans Go et un peu de difficulté avec le compilateur ;
- implémentation un peu moins simple, mais beaucoup plus productive dans l'assembleur Go ;
- « problèmes » d'index bitmap ;
- implémentations existantes.
Alors, que sont les index ?
L'index est une structure de données distincte que nous maintenons et mettons à jour en plus des données principales. Il est utilisé pour accélérer la recherche. Sans index, la recherche nécessiterait de parcourir complètement les données (un processus appelé analyse complète), et ce processus a une complexité algorithmique linéaire. Mais les bases de données contiennent généralement d’énormes quantités de données et la complexité linéaire est trop lente. Idéalement, nous obtiendrions une valeur logarithmique ou constante.
Il s'agit d'un sujet extrêmement complexe, rempli de subtilités et de compromis, mais après avoir examiné des décennies de développement et de recherche sur des bases de données, je suis prêt à dire qu'il n'existe que quelques approches largement utilisées pour créer des index de bases de données.
La première approche consiste à réduire hiérarchiquement l’espace de recherche, en divisant l’espace de recherche en parties plus petites.
Nous faisons généralement cela en utilisant différents types d’arbres. Un exemple serait une grande boîte de matériel dans votre placard qui contient des boîtes de matériel plus petites divisées en différents sujets. Si vous avez besoin de matériel, vous le chercherez probablement dans une case indiquant « Matériaux » plutôt que dans celle indiquant « Cookies », n'est-ce pas ?
La deuxième approche consiste à sélectionner immédiatement l'élément ou le groupe d'éléments souhaité. Nous faisons cela dans des cartes de hachage ou des index inversés. L'utilisation de cartes de hachage est très similaire à l'exemple précédent, mais au lieu d'une boîte de boîtes, vous avez un tas de petites boîtes d'articles finaux dans votre placard.
La troisième approche consiste à éliminer le besoin de recherche. Nous faisons cela en utilisant des filtres Bloom ou des filtres coucou. Les premiers donnent une réponse instantanément, vous évitant ainsi de devoir chercher.
La dernière approche consiste à utiliser pleinement toute la puissance que nous offre le matériel moderne. C'est exactement ce que nous faisons dans les index bitmap. Oui, lorsque nous les utilisons, nous devons parfois parcourir l’intégralité de l’index, mais nous le faisons de manière très efficace.
Comme je l'ai dit, le sujet des index de bases de données est vaste et plein de compromis. Cela signifie que nous pouvons parfois utiliser plusieurs approches en même temps : si nous devons accélérer encore plus la recherche, ou si nous devons couvrir tous les types de recherche possibles.
Aujourd'hui, je vais parler de l'approche la moins connue de celles-ci : les index bitmap.
Qui suis-je pour parler de ce sujet ?
Je travaille en tant que chef d'équipe chez Badoo (vous connaissez peut-être mieux notre autre produit, Bumble). Nous avons déjà plus de 400 millions d'utilisateurs dans le monde et de nombreuses fonctionnalités qui sélectionnent la meilleure solution pour eux. Nous faisons cela en utilisant des services personnalisés, notamment des index bitmap.
Alors, qu’est-ce qu’un index bitmap ?
Les index bitmap, comme leur nom l'indique, utilisent des bitmaps ou des jeux de bits pour implémenter un index de recherche. Vu d'ensemble, cet index se compose d'un ou plusieurs bitmaps représentant des entités (telles que des personnes) et leurs propriétés ou paramètres (âge, couleur des yeux, etc.), ainsi que d'un algorithme utilisant des opérations binaires (ET, OU, NON). ) pour répondre à la requête de recherche.
On nous dit que les index bitmap sont les mieux adaptés et très performants dans les cas où des recherches combinent des requêtes sur de nombreuses colonnes à faible cardinalité (pensez à « couleur des yeux » ou « état civil » par rapport à quelque chose comme « distance du centre-ville »). Mais je montrerai plus tard qu'ils fonctionnent également très bien pour les colonnes à cardinalité élevée.
Regardons l'exemple le plus simple d'un index bitmap.
Imaginez que nous ayons une liste de restaurants de Moscou avec des propriétés binaires comme celles-ci :
- près du métro;
- il y a un parking privé ;
- il y a une véranda (avec terrasse) ;
- vous pouvez réserver une table (accepte les réservations) ;
- convient aux végétariens (végétaliens) ;
- cher (cher).
Attribuons à chaque restaurant un numéro de séquence commençant à 0 et allouons de la mémoire pour 6 bitmaps (un pour chaque caractéristique). Nous peuplerons ensuite ces bitmaps selon que le restaurant possède ou non cette propriété. Si le restaurant 4 possède une véranda, alors le bit n°4 du bitmap « possède une véranda » sera mis à 1 (s'il n'y a pas de véranda, alors à 0).
Nous disposons désormais de l'index bitmap le plus simple possible et nous pouvons l'utiliser pour répondre à des requêtes telles que :
- « Montrez-moi des restaurants végétariens » ;
- "Montrez-moi des restaurants bon marché avec une véranda où vous pourrez réserver une table."
Comment? Jetons un coup d'oeil. La première demande est très simple. Tout ce que nous avons à faire est de prendre le bitmap « végétarien » et de le transformer en une liste de restaurants dont les éléments sont exposés.
La deuxième demande est un peu plus compliquée. Nous devons utiliser le bitmap NON sur le bitmap « cher » pour obtenir une liste de restaurants bon marché, puis ET avec le bitmap « puis-je réserver une table » et ET le résultat avec le bitmap « il y a une véranda ». Le bitmap résultant contiendra une liste d'établissements qui répondent à tous nos critères. Dans cet exemple, il s'agit uniquement du restaurant Yunost.
Cela implique beaucoup de théorie, mais ne vous inquiétez pas, nous verrons le code très bientôt.
Où les index bitmap sont-ils utilisés ?
Si vous utilisez des index bitmap Google, 90 % des réponses seront liées à Oracle DB d'une manière ou d'une autre. Mais d’autres SGBD prennent probablement aussi en charge une chose aussi intéressante, n’est-ce pas ? Pas vraiment.
Passons en revue la liste des principaux suspects.
MySQL ne prend pas encore en charge les index bitmap, mais il existe une proposition suggérant d'ajouter cette option ().
PostgreSQL ne prend pas en charge les index bitmap, mais utilise de simples bitmaps et opérations binaires pour combiner les résultats de recherche dans plusieurs autres index.
Tarantool possède des index de bits et prend en charge des recherches simples sur ceux-ci.
Redis a des champs de bits simples) sans possibilité de les rechercher.
MongoDB ne prend pas encore en charge les index bitmap, mais il existe également une proposition suggérant que cette option soit ajoutée.
Elasticsearch utilise des bitmaps en interne).
- Mais une nouvelle voisine est apparue dans notre maison : Pilosa. Il s'agit d'une nouvelle base de données non relationnelle écrite en Go. Il ne contient que des index bitmap et base tout sur eux. Nous en reparlerons un peu plus tard.
Implémentation en Go
Mais pourquoi les index bitmap sont-ils si rarement utilisés ? Avant de répondre à cette question, je voudrais vous montrer comment implémenter un index bitmap très simple dans Go.
Les bitmaps ne sont essentiellement que des morceaux de données. Dans Go, utilisons des tranches d'octets pour cela.
Nous avons un bitmap pour une caractéristique d'un restaurant, et chaque bit du bitmap indique si un restaurant particulier possède cette propriété ou non.
Nous aurons besoin de deux fonctions d'assistance. L’un sera utilisé pour remplir nos bitmaps avec des données aléatoires. Aléatoire, mais avec une certaine probabilité, le restaurant possède chaque propriété. Par exemple, je crois qu'il y a très peu de restaurants à Moscou où l'on ne peut pas réserver une table, et il me semble qu'environ 20 % des établissements conviennent aux végétariens.
La deuxième fonction convertira le bitmap en une liste de restaurants.
Pour répondre à la requête « Montrez-moi les restaurants bon marché qui disposent d’une terrasse et peuvent faire des réservations », nous avons besoin d’opérations en deux bits : NOT et AND.
Nous pouvons simplifier un peu notre code en utilisant l’opérateur AND NOT, plus complexe.
Nous avons des fonctions pour chacune de ces opérations. Tous deux parcourent les tranches, prennent les éléments correspondants de chacune, les combinent avec une petite opération et mettent le résultat dans la tranche résultante.
Et maintenant, nous pouvons utiliser nos bitmaps et nos fonctions pour répondre à la requête de recherche.
Les performances ne sont pas si élevées, même si les fonctions sont très simples et que nous avons économisé beaucoup d'argent en ne renvoyant pas une nouvelle tranche résultante à chaque appel de la fonction.
Après avoir fait un peu de profilage avec pprof, j'ai remarqué qu'il manquait au compilateur Go une optimisation très simple mais très importante : l'inlining de fonctions.
Le fait est que le compilateur Go a terriblement peur des boucles qui traversent des tranches et refuse catégoriquement d'intégrer des fonctions contenant de telles boucles.
Mais je n’ai pas peur et je peux tromper le compilateur en utilisant goto au lieu d’une boucle, comme au bon vieux temps.
Et, comme vous pouvez le voir, le compilateur intégrera désormais volontiers notre fonction ! En conséquence, nous parvenons à gagner environ 2 microsecondes. Pas mal!
Le deuxième goulot d’étranglement est facile à repérer si vous examinez attentivement le résultat de l’assemblage. Le compilateur a ajouté une vérification des limites de tranche directement dans notre boucle la plus chaude. Le fait est que Go est un langage sûr, le compilateur a peur que mes trois arguments (trois tranches) soient de tailles différentes. Après tout, il existera alors une possibilité théorique de ce que l'on appelle un débordement de tampon.
Rassurons le compilateur en lui montrant que toutes les tranches ont la même taille. Nous pouvons le faire en ajoutant une simple vérification au début de notre fonction.
Voyant cela, le compilateur ignore volontiers la vérification et nous finissons par économiser 500 nanosecondes supplémentaires.
Grosses bouches
D'accord, nous avons réussi à réduire certaines performances de notre simple implémentation, mais ce résultat est en réalité bien pire que ce qui est possible avec le matériel actuel.
Tout ce que nous faisons, ce sont des opérations binaires de base, et nos processeurs les exécutent très efficacement. Mais malheureusement, nous « nourrissons » notre processeur avec de très petites tâches. Nos fonctions effectuent des opérations octet par octet. Nous pouvons très facilement modifier notre code pour qu'il fonctionne avec des morceaux de 8 octets à l'aide de tranches UInt64.
Comme vous pouvez le constater, ce petit changement a accéléré notre programme huit fois en augmentant de huit fois la taille du lot. Le gain peut être considéré comme linéaire.
Implémentation en assembleur
Mais ce n’est pas la fin. Nos processeurs peuvent fonctionner avec des morceaux de 16, 32 et même 64 octets. De telles opérations « larges » sont appelées données multiples à instruction unique (SIMD ; une instruction, plusieurs données), et le processus de transformation du code afin qu'il utilise de telles opérations est appelé vectorisation.
Malheureusement, le compilateur Go est loin d'être excellent en matière de vectorisation. Actuellement, la seule façon de vectoriser le code Go est de prendre et de placer ces opérations manuellement à l'aide de l'assembleur Go.
Aller assembleur est une bête étrange. Vous savez probablement que le langage assembleur est fortement lié à l'architecture de l'ordinateur pour lequel vous écrivez, mais ce n'est pas le cas dans Go. Go Assembleur s'apparente davantage à un IRL (langage de représentation intermédiaire) ou à un langage intermédiaire : il est pratiquement indépendant de la plateforme. Rob Pike a donné une excellente performance sur ce sujet il y a plusieurs années à la GopherCon à Denver.
De plus, Go utilise un format Plan 9 inhabituel, qui diffère des formats AT&T et Intel généralement acceptés.
On peut dire sans se tromper qu'écrire l'assembleur Go à la main n'est pas des plus amusants.
Mais heureusement, il existe déjà deux outils de haut niveau qui nous aident à écrire un assembleur Go : PeachPy et avo. Les deux utilitaires génèrent un assembleur Go à partir de code de niveau supérieur écrit respectivement en Python et Go.
Ces utilitaires simplifient des choses comme l'allocation de registres, l'écriture de boucles et simplifient généralement le processus d'entrée dans le monde de la programmation assembleur dans Go.
Nous utiliserons avo, nos programmes seront donc des programmes Go presque réguliers.
Voici à quoi ressemble l’exemple le plus simple d’un programme avo. Nous avons une fonction main(), qui définit en elle-même la fonction Add(), dont le sens est d'ajouter deux nombres. Il existe ici des fonctions d'assistance pour obtenir les paramètres par nom et obtenir l'un des registres de processeur gratuits et appropriés. Chaque opération du processeur a une fonction correspondante sur avo, comme le montre ADDQ. Enfin, nous voyons une fonction d'assistance pour stocker la valeur résultante.
En appelant go generate, nous exécuterons le programme sur avo et du coup, deux fichiers seront générés :
- add.s avec le code résultant dans l'assembleur Go ;
- stub.go avec des en-têtes de fonctions pour connecter les deux mondes : Go et assembleur.
Maintenant que nous avons vu ce que fait avo et comment, regardons nos fonctions. J'ai implémenté les versions scalaire et vectorielle (SIMD) des fonctions.
Regardons d'abord les versions scalaires.
Comme dans l'exemple précédent, nous demandons un registre à usage général gratuit et valide, nous n'avons pas besoin de calculer les décalages et les tailles pour les arguments. avo fait tout cela pour nous.
Nous avions l'habitude d'utiliser des étiquettes et des goto (ou des sauts) pour améliorer les performances et tromper le compilateur Go, mais maintenant nous le faisons depuis le début. Le fait est que les cycles sont un concept de niveau supérieur. En assembleur, nous n'avons que des étiquettes et des sauts.
Le code restant devrait déjà être familier et compréhensible. Nous émulons une boucle avec des étiquettes et des sauts, prenons un petit morceau de données de nos deux tranches, les combinons avec une opération binaire (ET NON dans ce cas), puis mettons le résultat dans la tranche résultante. Tous.
Voici à quoi ressemble le code assembleur final. Nous n'avons pas eu besoin de calculer les décalages et les tailles (surlignés en vert) ni de suivre les registres utilisés (surlignés en rouge).
Si nous comparons les performances de l’implémentation du langage assembleur avec les performances de la meilleure implémentation dans Go, nous verrons que c’est la même chose. Et cela est attendu. Après tout, nous n’avons rien fait de spécial – nous avons simplement reproduit ce que ferait un compilateur Go.
Malheureusement, nous ne pouvons pas forcer le compilateur à intégrer nos fonctions écrites en langage assembleur. Le compilateur Go ne dispose actuellement pas d'une telle fonctionnalité, bien qu'il y ait une demande pour l'ajouter depuis un certain temps.
C'est pourquoi il est impossible de tirer le moindre bénéfice des petites fonctions du langage assembleur. Nous devons soit écrire des fonctions volumineuses, soit utiliser le nouveau package math/bits, soit contourner le langage assembleur.
Regardons maintenant les versions vectorielles de nos fonctions.
Pour cet exemple, j'ai décidé d'utiliser AVX2, nous utiliserons donc des opérations qui opèrent sur des morceaux de 32 octets. La structure du code est très similaire à la version scalaire : chargement des paramètres, demande d'un registre partagé gratuit, etc.
Une innovation réside dans le fait que les opérations vectorielles plus larges utilisent des registres larges spéciaux. Dans le cas de morceaux de 32 octets, ce sont des registres préfixés par Y. C'est pourquoi vous voyez la fonction YMM() dans le code. Si j'utilisais AVX-512 avec des morceaux de 64 bits, le préfixe serait Z.
La deuxième innovation est que j'ai décidé d'utiliser une optimisation appelée déroulement de boucle, ce qui signifie effectuer huit opérations de boucle manuellement avant de passer au début de la boucle. Cette optimisation réduit le nombre de branches dans le code, et est limitée par le nombre de registres gratuits disponibles.
Eh bien, qu'en est-il des performances ? Elle est belle! Nous avons atteint une accélération d'environ sept fois par rapport à la meilleure solution Go. Impressionnant, non ?
Mais même cette implémentation pourrait potentiellement être accélérée en utilisant AVX-512, la prélecture ou un JIT (compilateur juste à temps) pour le planificateur de requêtes. Mais c’est certainement un sujet qui fera l’objet d’un rapport distinct.
Problèmes avec les index bitmap
Maintenant que nous avons déjà examiné une implémentation simple d'un index bitmap dans Go et une implémentation beaucoup plus productive en langage assembleur, parlons enfin de la raison pour laquelle les index bitmap sont si rarement utilisés.
Des articles plus anciens mentionnent trois problèmes avec les index bitmap, mais des articles plus récents et moi-même soutenons qu'ils ne sont plus pertinents. Nous n’entrerons pas dans le détail de chacun de ces problèmes, mais les examinerons superficiellement.
Le problème de la cardinalité élevée
Ainsi, on nous dit que les index bitmap ne conviennent qu'aux champs à faible cardinalité, c'est-à-dire ceux qui ont peu de valeurs (par exemple, le sexe ou la couleur des yeux), et la raison en est que la représentation habituelle de ces champs (un bit par valeur) en cas de cardinalité élevée, cela prendra trop de place et, de plus, ces index bitmap seront mal (rarement) remplis.
Parfois, nous pouvons utiliser une représentation différente, telle que la représentation standard que nous utilisons pour représenter les nombres. Mais c’est l’avènement des algorithmes de compression qui a tout changé. Au cours des dernières décennies, les scientifiques et les chercheurs ont mis au point un grand nombre d’algorithmes de compression pour les bitmaps. Leur principal avantage est qu'il n'est pas nécessaire de décompresser les bitmaps pour effectuer des opérations sur les bits - nous pouvons effectuer des opérations sur les bits directement sur les bitmaps compressés.
Récemment, des approches hybrides ont commencé à apparaître, comme les bitmaps rugissants. Ils utilisent simultanément trois représentations différentes pour les bitmaps - les bitmaps eux-mêmes, les tableaux et ce qu'on appelle les exécutions de bits - et équilibrent entre elles pour maximiser les performances et minimiser la consommation de mémoire.
Vous pouvez trouver des bitmaps rugissants dans les applications les plus populaires. Il existe déjà un grand nombre d’implémentations pour une grande variété de langages de programmation, dont plus de trois implémentations pour Go.
Une autre approche qui peut nous aider à gérer une cardinalité élevée est appelée binning. Imaginez que vous ayez un champ représentant la taille d'une personne. La hauteur est un nombre à virgule flottante, mais nous, les humains, ne l'envisageons pas de cette façon. Pour nous, il n'y a pas de différence entre une hauteur de 185,2 cm et 185,3 cm.
Il s'avère que nous pouvons regrouper des valeurs similaires en groupes à moins de 1 cm.
Et si nous savons également que très peu de personnes mesurent moins de 50 cm et plus de 250 cm, alors nous pouvons essentiellement transformer un champ de cardinalité infinie en un champ de cardinalité d’environ 200 valeurs.
Bien entendu, si nécessaire, nous pouvons effectuer un filtrage supplémentaire par la suite.
Problème de bande passante élevée
Le prochain problème avec les index bitmap est que leur mise à jour peut être très coûteuse.
Les bases de données doivent être capables de mettre à jour les données pendant que potentiellement des centaines d'autres requêtes recherchent les données. Nous avons besoin de verrous pour éviter les problèmes d'accès simultané aux données ou d'autres problèmes de partage. Et là où il y a un gros verrou, il y a un problème : un conflit de verrous, lorsque ce verrou devient un goulot d'étranglement.
Ce problème peut être résolu ou contourné en utilisant le partitionnement ou l'utilisation d'index versionnés.
Le partage est une chose simple et bien connue. Vous pouvez partager un index bitmap comme vous le feriez pour n’importe quelle autre donnée. Au lieu d'un grand verrou, vous obtiendrez un tas de petits verrous et vous débarrasserez ainsi des conflits de verrouillage.
La deuxième façon de résoudre le problème consiste à utiliser des index versionnés. Vous pouvez avoir une copie de l'index que vous utilisez pour la recherche ou la lecture, et une autre que vous utilisez pour l'écriture ou la mise à jour. Et une fois sur une certaine période de temps (par exemple, une fois toutes les 100 ms ou 500 ms), vous les dupliquez et les échangez. Bien entendu, cette approche n'est applicable que dans les cas où votre application peut gérer un index de recherche légèrement en retard.
Ces deux approches peuvent être utilisées simultanément : vous pouvez avoir un index versionné fragmenté.
Requêtes plus complexes
Le dernier problème avec les index bitmap est qu’on nous dit qu’ils ne sont pas bien adaptés aux types de requêtes plus complexes, telles que les requêtes span.
En effet, si l’on y réfléchit, les opérations binaires comme AND, OR, etc. ne sont pas très adaptées aux requêtes du type « Montrez-moi les hôtels avec des tarifs de chambre de 200 à 300 dollars par nuit ».
Une solution naïve et très imprudente serait de prendre les résultats pour chaque valeur en dollars et de les combiner avec une opération OU au niveau du bit.
Une solution légèrement meilleure serait d’utiliser le regroupement. Par exemple, par groupes de 50 dollars. Cela accélérerait notre processus de 50 fois.
Mais le problème est également facilement résolu en utilisant une vue créée spécifiquement pour ce type de requête. Dans les articles scientifiques, on parle de bitmaps codés par plage.
Dans cette représentation, nous ne définissons pas simplement un bit pour une valeur (par exemple, 200), mais définissons cette valeur et tout plus haut. 200 et plus. Idem pour 300 : 300 et plus. Et ainsi de suite.
En utilisant cette représentation, nous pouvons répondre à ce type de requête de recherche en parcourant l'index seulement deux fois. Tout d’abord, nous obtiendrons une liste d’hôtels où la chambre coûte moins cher ou 300 $, puis nous en retirerons ceux où le coût de la chambre est inférieur ou 199 $. Prêt.
Vous serez surpris, mais même les géorequêtes sont possibles à l'aide d'index bitmap. L'astuce consiste à utiliser une représentation géométrique qui entoure vos coordonnées avec une figure géométrique. Par exemple, S2 de Google. La figure doit pouvoir être représentée sous la forme de trois lignes sécantes ou plus pouvant être numérotées. De cette façon, nous pouvons transformer notre géorequête en plusieurs requêtes « le long de l'écart » (le long de ces lignes numérotées).
Solutions prêtes
J'espère que je vous ai un peu intéressé et que vous avez maintenant un autre outil utile dans votre arsenal. Si jamais vous avez besoin de faire quelque chose comme ça, vous saurez dans quelle direction regarder.
Cependant, tout le monde n’a pas le temps, la patience ou les ressources nécessaires pour créer des index bitmap à partir de zéro. Surtout les plus avancés, utilisant SIMD par exemple.
Heureusement, il existe plusieurs solutions toutes faites pour vous aider.
Bitmaps rugissants
Premièrement, il y a la même bibliothèque de bitmaps rugissants dont j'ai déjà parlé. Il contient tous les conteneurs et opérations binaires nécessaires dont vous aurez besoin pour créer un index bitmap à part entière.
Malheureusement, pour le moment, aucune des implémentations Go n'utilise SIMD, ce qui signifie que les implémentations Go sont moins performantes que les implémentations C, par exemple.
Cheveu
Un autre produit qui peut vous aider est le SGBD Pilosa, qui, en fait, ne dispose que d'index bitmap. Il s’agit d’une solution relativement nouvelle, mais elle gagne rapidement les cœurs.
Pilosa utilise des bitmaps rugissants en interne et vous donne la possibilité de les utiliser, simplifie et explique toutes les choses dont j'ai parlé ci-dessus : le regroupement, les bitmaps codés par plage, le concept de champ, etc.
Jetons un coup d'œil rapide à un exemple d'utilisation de Pilosa pour répondre à une question que vous connaissez déjà.
L’exemple est très similaire à ce que vous avez vu auparavant. Nous créons un client sur le serveur Pilosa, créons un index et les champs nécessaires, puis remplissons nos champs avec des données aléatoires avec des probabilités et, enfin, exécutons la requête familière.
Après cela, on utilise NON sur le champ "cher", puis on croise le résultat (ou ET lui) avec le champ "terrasse" et avec le champ "réservations". Et enfin, nous obtenons le résultat final.
J'espère vraiment que dans un avenir proche, ce nouveau type d'index apparaîtra également dans les SGBD comme MySQL et PostgreSQL - index bitmap.
Conclusion
Si vous ne vous êtes pas encore endormi, merci. J'ai dû aborder brièvement de nombreux sujets en raison du temps limité, mais j'espère que l'exposé a été utile et peut-être même motivant.
Les index bitmap sont bons à connaître, même si vous n'en avez pas besoin pour le moment. Laissez-les être un autre outil dans votre boîte à outils.
Nous avons examiné diverses astuces de performances pour Go et des éléments que le compilateur Go ne gère pas encore très bien. Mais cela est absolument utile à tous les programmeurs Go.
C'est tout ce que je voulais te dire. Merci!
Source: habr.com