Mot de bienvenue
J'ai présenté cette conférence en anglais à la conférence GopherCon Russia 2019 à Moscou et en russe lors du meetup à Nijni Novgorod. Elle porte sur l'index bitmap—moins répandu que l'index B-tree, mais tout aussi intéressant. Je partage de la présentation à la conférence en anglais et la transcription textuelle en russe.
Nous examinerons comment fonctionne l'index bitmap, quand il est meilleur, quand il est moins efficace que d'autres index, et dans quels cas il est beaucoup plus rapide que ceux-ci ; nous verrons dans quelles SGBD populaires des index bitmap existent déjà ; nous essaierons d'en écrire un en Go. Et pour le dessert, nous utiliserons des bibliothèques prêtes à l'emploi pour créer notre base de données spécialisée ultra-rapide.
J'espère sincèrement que mes travaux vous seront utiles et intéressants. Allons-y !
Introduction
Bonjour à tous ! Il est six heures du soir, nous sommes tous super fatigués. Un moment idéal pour parler de la théorie ennuyeuse des index de bases de données, n'est-ce pas ? Ne vous inquiétez pas, il y aura quelques lignes de code source ici et là. 🙂
Sans plaisanter, la présentation est remplie d'informations, et nous n'avons pas beaucoup de temps. Alors commençons.
Aujourd'hui, je vais parler des sujets suivants :
- Qu'est-ce que les index ;
- Qu'est-ce que l'index bitmap ;
- Où il est utilisé et où il n'est PAS utilisé et pourquoi ;
- Une implémentation simple en Go et un peu de lutte avec le compilateur ;
- Une implémentation un peu moins simple mais beaucoup plus performante en Go-assembleur ;
- Les « problèmes » des index bitmap ;
- Les implémentations existantes.
Alors, qu'est-ce que les index ?
Un index est une structure de données distincte que nous maintenons et mettons à jour en complément des données principales. Elle est utilisée pour accélérer les recherches. Sans index, la recherche nécessiterait un passage complet des données (processus appelé full scan), et ce processus a une complexité algorithmique linéaire. Mais les bases de données contiennent généralement une immense quantité de données et une complexité linéaire est trop lente. Idéalement, nous aimerions obtenir une complexité logarithmique ou constante.
C'est un sujet vaste et complexe, rempli de nuances et de compromis, mais après avoir examiné des décennies de développement et de recherche sur différentes bases de données, je suis convaincu qu'il existe seulement quelques approches largement utilisées pour créer des index de SGBD.
La première approche consiste à réduire hierarchiquement la zone de recherche, en divisant cette zone en parties plus petites.
En général, nous faisons cela en utilisant différents types d'arbres. Par exemple, une grande boîte avec des matériaux dans votre armoire, contenant des petites boîtes avec des matériaux séparés par différents thèmes. Si vous avez besoin de matériaux, vous chercherez probablement dans la boîte étiquetée « Matériaux », et non dans celle étiquetée « Biscuits », n'est-ce pas ?
La deuxième approche consiste à identifier immédiatement l'élément ou le groupe d'éléments requis. Nous faisons cela dans des tables de hachage ou des index inversés. L'utilisation des tables de hachage est très similaire à l'exemple précédent, sauf qu'au lieu d'une boîte avec des boîtes, vous avez dans votre armoire une pile de petites boîtes avec des items finaux.
La troisième approche consiste à éliminer le besoin de recherche. Nous faisons cela à l'aide de filtres de Bloom ou de filtres de cuckoo. Les premiers donnent une réponse instantanément, vous évitant ainsi de faire une recherche.
La dernière approche consiste à utiliser pleinement toutes les capacités offertes par le matériel moderne. C'est ce que nous faisons avec les index bitmap. Oui, lors de leur utilisation, il arrive que nous devions parcourir tout l'index, mais nous le faisons de manière super efficace.
Comme je l'ai déjà dit, le sujet des index de bases de données est vaste et rempli de compromis. Cela signifie que parfois, nous pouvons utiliser plusieurs approches simultanément : si nous devons encore accélérer la recherche ou si nous devons couvrir tous les types de recherche possibles.
Aujourd'hui, je vais parler de l'approche la moins connue parmi celles mentionnées — des index bitmap.
Qui suis-je pour parler de ce sujet ?
Je travaille en tant que leader 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'occupent de cela, en leur proposant le meilleur partenaire. Nous faisons cela grâce à des services personnalisés, utilisant également des index bitmap.
Alors, qu'est-ce qu'un index bitmap ?
Les index bitmap, comme leur nom l'indique, utilisent des bitmaps ou des bits sets pour implémenter un index de recherche. À vol d'oiseau, cet index est constitué d'un ou plusieurs de ces bitmaps, représentant des entités (comme des personnes) et leurs propriétés ou paramètres (âge, couleur des yeux, etc.), ainsi que d'un algorithme utilisant des opérations bit à bit (ET, OU, NON) pour répondre à une requête de recherche.
On nous dit que les index bitmap conviennent le mieux et sont très performants dans les cas où il y a des recherches combinant des requêtes sur de nombreuses colonnes ayant une faible cardinalité (imaginez « couleur des yeux » ou « situation familiale » par rapport à quelque chose comme « distance du centre-ville »). Mais plus tard, je montrerai qu'ils fonctionnent également très bien avec des colonnes à haute cardinalité.
Considérons un exemple simple d'index bitmap.
Imaginons que nous avons une liste de restaurants à Moscou avec des propriétés binaires telles que celles-ci :
- près du métro (near metro);
- dispose d'un parking privé (has private parking);
- dispose d'une terrasse (has terrace);
- accepte les réservations (accepts reservations);
- convient aux végétariens (vegan friendly);
- cher (expensive).
Attribuons à chaque restaurant un numéro d'ordre commençant par 0 et allouons de la mémoire pour 6 bitmaps (un pour chaque caractéristique). Ensuite, nous remplirons ces bitmaps en fonction de la possession ou non par le restaurant de cette caractéristique. Si le restaurant 4 a une terrasse, alors le bit n°4 dans le bitmap « dispose d'une terrasse » sera positionné à 1 (s'il n'y a pas de terrasse, il sera à 0).
Nous avons maintenant l'index bitmap le plus simple qui soit, et nous pouvons l'utiliser pour répondre à des requêtes telles que :
- « Montre-moi les restaurants compatibles avec les végétariens » ;
- « Montre-moi les restaurants abordables avec une terrasse, où il est possible de réserver une table ».
Comment ? Voyons cela. La première requête est très simple. Tout ce que nous avons à faire est de prendre le bitmap « convient aux végétariens » et de le convertir en une liste de restaurants dont les bits sont positions.
La deuxième requête est un peu plus complexe. Nous devons utiliser l'opération bitwise NOT sur le bitmap "cher" pour obtenir la liste des restaurants bon marché, puis faire un AND avec le bitmap "peut réserver une table" et ensuite un AND avec le bitmap "a une terrasse". Le bitmap résultant contiendra la liste des établissements qui répondent à tous nos critères. Dans cet exemple, il s'agit uniquement du restaurant "Jeunesse".
Il y a beaucoup de théorie ici, mais ne vous inquiétez pas, nous verrons le code très bientôt.
Où sont utilisés les index bitmap ?
Si vous "googlisez" les index bitmap, 90% des réponses seront liées d'une manière ou d'une autre à Oracle DB. Mais d'autres SGBD doivent également prendre en charge une telle fonctionnalité, 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 pour ajouter cette option ().
PostgreSQL ne prend pas en charge les index bitmap, mais utilise des bitmaps simples et des opérations bit pour combiner les résultats de la recherche sur plusieurs autres index.
Tarantool a des index bitset, il prend en charge la recherche simple sur eux.
Redis a des champs binaires simples) sans possibilité de recherche sur eux.
MongoDB ne prend pas encore en charge les index bitmap, mais il y a également une proposition pour ajouter cette option
Elasticsearch utilise des bitmaps à l'intérieur).
- Mais un nouveau voisin a fait son apparition dans notre maison : Pilosa. C'est une nouvelle base de données non relationnelle, écrite en Go. Elle contient uniquement des index bitmap et s'appuie entièrement sur eux. Nous en parlerons 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 une implémentation d'un index bitmap très simple en Go.
Les bitmaps sont essentiellement représentés comme de simples morceaux de données. En Go, utilisons pour cela des slices de bytes.
Nous avons un bitmap pour une caractéristique de restaurant, et chaque bit dans le bitmap indique si un restaurant spécifique possède cette caractéristique ou non.
Nous aurons besoin de deux fonctions auxiliaires. L'une sera utilisée pour remplir nos bitmaps de données aléatoires. Aléatoires, mais avec une probabilité déterminée que le restaurant possède chaque propriété. Par exemple, je pense qu'il y a très peu de restaurants à Moscou où l'on ne peut pas réserver de table, et il me semble qu'environ 20 % des établissements conviennent aux végétariens.
La deuxième fonction convertira le bitmap en liste de restaurants.
Pour répondre à la requête « Montre-moi des restaurants bon marché avec une terrasse où l'on peut réserver une table », nous aurons besoin de deux opérations bit à bit : NOT et AND.
Nous pouvons simplifier un peu notre code en utilisant une opération AND NOT plus complexe.
Nous avons des fonctions pour chacune de ces opérations. Les deux parcourent les slices, prennent les éléments correspondants de chacun, les combinent en une opération bit à bit et mettent le résultat dans un slice de résultats.
Et maintenant, nous pouvons utiliser nos bitmaps et fonctions pour répondre à la requête de recherche.
La performance n'est pas très élevée, même si les fonctions sont très simples et que nous avons économisé sur le fait de ne pas renvoyer un nouveau slice de résultats à chaque appel de fonction.
En faisant un peu de profilage avec pprof, j'ai remarqué que le compilateur Go avait ignoré une optimisation très simple mais cruciale : l'inlining de fonction.
En effet, le compilateur Go craint terriblement les boucles qui parcourent les slices et refuse catégoriquement d'inliner les fonctions qui contiennent de telles boucles.
Mais je n'ai pas peur et je peux tromper le compilateur en utilisant goto à la place d'une boucle, comme au bon vieux temps.
Et comme vous pouvez le voir, le compilateur est maintenant heureux d'inliner notre fonction ! Au final, nous parvenons à économiser environ 2 microsecondes. Pas mal !
Le deuxième goulet d'étranglement est facile à voir si l'on regarde attentivement la sortie assembleur. Le compilateur a ajouté une vérification des limites du slice directement dans notre boucle la plus chaude. Le fait est que Go est un langage sûr, le compilateur craint que mes trois arguments (trois slices) aient des tailles différentes. Cela créerait alors une possibilité théorique de débordement de tampon.
Calmons le compilateur en lui montrant que tous les slices ont la même taille. Nous pouvons le faire en ajoutant une simple vérification au début de notre fonction.
En voyant cela, le compilateur passe la vérification avec joie, et nous économisons ainsi 500 nanosecondes.
Gros batches
D'accord, nous avons réussi à extraire une certaine performance de notre simple implémentation, mais ce résultat est en réalité bien inférieur à ce qui est possible avec le matériel actuel.
Tout ce que nous faisons, ce sont des opérations de base sur des bits, et nos processeurs les exécutent très efficacement. Mais, malheureusement, nous 'nourrissons' notre processeur avec de très petits morceaux de travail. Nos fonctions effectuent des opérations byte par byte. Nous pouvons facilement optimiser notre code pour qu’il fonctionne avec des morceaux de 8 octets en utilisant des slices UInt64.
Comme vous pouvez le voir, ce petit changement a accéléré notre programme par huit grâce à une augmentation du batch par huit. Le gain est, on peut le dire, linéaire.
Implémentation en assembleur
Mais ce n'est pas encore la fin. Nos processeurs peuvent travailler avec des morceaux de 16, 32 et même 64 octets. Ces 'opérations larges' sont appelées single instruction multiple data (SIMD ; une instruction, plusieurs données), et le processus de transformation du code pour qu'il utilise de telles opérations s'appelle vectorisation.
Malheureusement, le compilateur Go n’est pas un expert en vectorisation. Actuellement, la seule façon de vectoriser du code en Go est de prendre et d'écrire manuellement les opérations à l'aide de l’assembleur Go.
L'assembleur Go est une bête étrange. Vous savez probablement que l'assembleur est quelque chose de fortement lié à l'architecture de l'ordinateur pour lequel vous écrivez, mais en Go, ce n'est pas le cas. L'assembleur Go ressemble davantage à un langage de représentation intermédiaire (IRL) : il est pratiquement indépendant de la plateforme. Rob Pike a donné une excellente à ce sujet il y a quelques années à GopherCon à Denver.
En plus de cela, Go utilise un format inhabituel Plan 9, différent des formats reconnus AT&T et Intel.
On peut dire avec certitude que rédiger manuellement de l’assembleur Go n’est pas l’activité la plus amusante.
Mais heureusement, il existe déjà deux outils de haut niveau qui nous aident à écrire en assembleur Go : PeachPy et avo. Ces deux utilitaires génèrent de l’assembleur Go à partir de code de niveau supérieur écrit en Python et en Go respectivement.
Ces utilitaires simplifient des aspects tels que l'allocation de registres (choix des registres processeur), l'écriture de boucles, et facilitent globalement l'entrée dans le monde de la programmation en assembleur en Go.
Nous allons utiliser avo, de sorte que nos programmes seront presque des programmes Go ordinaires.
Voilà à quoi ressemble l'exemple le plus simple d'un programme avo. Nous avons une fonction main() qui définit en son sein une fonction Add(), dont le but est d'additionner deux nombres. Voici des fonctions d'assistance pour obtenir les paramètres par nom et obtenir l'un des registres processeur libres et appropriés. Chaque opération processeur a une fonction correspondante sur avo, comme le montre ADDQ. Enfin, nous avons une fonction d'assistance pour sauvegarder la valeur résultante.
En appelant go generate, nous allons exécuter le programme sur avo et deux fichiers seront générés en fin de compte :
- add.s avec le code résultant en assembleur Go ;
- stub.go avec les en-têtes de fonctions pour relier les deux mondes : Go et assembleur.
Maintenant que nous avons vu ce que fait et comment fonctionne avo, regardons nos fonctions. J'ai implémenté à la fois les versions scalaires et vectorielles (SIMD) des fonctions.
Commençons par examiner les versions scalaires.
Comme dans l'exemple précédent, nous demandons un registre général libre et correct, nous n'avons pas besoin de calculer les décalages et les tailles des arguments. Tout cela est fait pour nous par avo.
Auparavant, nous utilisions des étiquettes et des sauts (ou des jumps) pour améliorer la performance et tromper le compilateur Go, mais maintenant nous le faisons dès le départ. En fait, les boucles 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 une petite portion de données de nos deux slices, les combinons par opération binaire (AND NOT dans ce cas) et plaçons ensuite le résultat dans le slice résultant. C'est tout.
Voici à quoi ressemble le code final en assembleur. Nous n'avons pas eu besoin de calculer les décalages et les tailles (mis en évidence en vert) ou de surveiller les registres utilisés (mis en évidence en rouge).
Lorsqu'on compare la performance d'une implémentation en assembleur avec celle de la meilleure implémentation en Go, on constate qu'elles sont identiques. C'est prévisible. En effet, nous n'avons rien fait de particulier — nous avons simplement reproduit ce que ferait le compilateur Go.
Malheureusement, nous ne pouvons pas forcer le compilateur à inliner nos fonctions écrites en assembleur. Actuellement, le compilateur Go ne dispose pas de cette possibilité, bien que la demande d'ajout de cette fonctionnalité existe depuis un certain temps.
C'est pourquoi il est impossible d'obtenir des avantages en utilisant de petites fonctions en assembleur. Nous devons soit écrire de grandes fonctions, soit utiliser le nouveau paquet math/bits, soit éviter l'assembleur.
Regardons maintenant les versions vectorielles de nos fonctions.
Pour cet exemple, j'ai décidé d'appliquer AVX2, donc nous allons utiliser des opérations fonctionnant avec des morceaux de 32 octets. La structure du code est très similaire à celle de la version scalaire : chargement des paramètres, demande d'un registre général libre, etc.
Une des innovations concerne le fait que des opérations vectorielles plus larges utilisent des registres spéciaux plus larges. Dans le cas des morceaux de 32 octets, ce sont des registres avec le préfixe Y. C'est pourquoi vous voyez la fonction YMM() dans le code. Si j'avais utilisé AVX-512 avec des morceaux de 64 bits, le préfixe aurait été Z.
La deuxième innovation concerne le fait que j'ai décidé d'utiliser une optimisation appelée déroulement de boucle (loop unrolling), c'est-à-dire de réaliser huit opérations de boucle manuellement avant de sauter 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 libres disponibles.
Et qu'en est-il de la performance ? Elle est excellente ! Nous avons obtenu un gain d'environ sept fois par rapport à la meilleure solution en Go. Impressionnant, n'est-ce pas ?
Mais même cette implémentation pourrait potentiellement être accélérée en utilisant AVX-512, le pré-fetching ou le JIT (compilateur just-in-time) pour le planificateur de requêtes. Mais c'est clairement un sujet pour une présentation distincte.
Problèmes des index bitmap
Maintenant que nous avons examiné une simple implémentation d'index bitmap en Go et une version beaucoup plus performante en assembleur, parlons enfin de la raison pour laquelle les index bitmap sont si rarement utilisés.
Des études scientifiques anciennes mentionnent trois problèmes liés aux index bitmap, mais des travaux plus récents et moi-même affirmons qu'ils ne sont plus d'actualité. Nous ne plongerons pas en profondeur dans chacun de ces problèmes, mais nous les examinerons survol.
Problème de grande cardinalité
On nous dit donc que les index bitmap sont adaptés uniquement aux champs à faible cardinalité, c'est-à-dire ceux qui ont peu de valeurs (comme le sexe ou la couleur des yeux), et la raison en est que la représentation classique de ces champs (un bit par valeur) en cas de grande cardinalité occuperait trop d'espace et, de plus, ces index bitmap seraient faiblement (rarement) remplis.
Parfois, nous pouvons utiliser une autre représentation, comme celle standard que nous utilisons pour représenter des nombres. Mais c'est l'émergence des algorithmes de compression qui a tout changé. Au cours des dernières décennies, des scientifiques et des chercheurs ont conçu un grand nombre d'algorithmes de compression pour les bitmap. Leur principal avantage est qu'il n'est pas nécessaire de décompresser les bitmap pour effectuer des opérations bit à bit — nous pouvons réaliser des opérations directement sur les bitmap compressés.
Récemment, des approches hybrides ont également commencé à apparaître, comme les bitmap roaring. Ils utilisent simultanément trois représentations différentes pour les bitmap — des bitmap à proprement parler, des tableaux et ce qu'on appelle des bit runs — et équilibrent entre elles pour maximiser la performance tout en minimisant la consommation de mémoire.
Vous pouvez trouver des bitmap roaring dans les applications les plus populaires. Il existe déjà un grand nombre d'implémentations pour divers langages de programmation, y compris plus de trois implémentations pour Go.
Une autre approche qui peut nous aider à gérer la grande cardinalité s'appelle le regroupement (binning). Imaginez que vous avez un champ représentant la taille d'une personne. La taille est un nombre à virgule flottante, mais nous, humains, ne pensons pas de cette manière. Pour nous, il n'y a pas de différence entre une taille de 185,2 cm et 185,3 cm.
Nous pouvons donc regrouper des valeurs similaires en groupes dans une plage de 1 cm.
Et si nous savons en plus que très peu de personnes mesurent moins de 50 cm ou plus de 250 cm, nous pouvons, en fait, transformer un champ à cardinalité infinie en un champ avec une cardinalité d'environ 200 valeurs.
Bien sûr, si nécessaire, nous pouvons effectuer un filtrage supplémentaire par la suite.
Le problème de la grande bande passante
Le problème suivant des index bitmap est que leur mise à jour peut être très coûteuse.
Les bases de données doivent permettre la mise à jour des données au moment où potentiellement des centaines d'autres requêtes recherchent ces données. Nous avons besoin de verrous pour éviter les problèmes d'accès concurrent aux données ou d'autres problèmes d'accès partagé. Là où il y a un grand verrou, il y a un problème — la contention de verrou, lorsque ce verrou devient un goulet d'étranglement.
Ce problème peut être résolu ou contourné en utilisant le sharding ou des index versionnés.
Le sharding est une chose simple et bien connue. Vous pouvez shardiser un index bitmap de la même manière que vous shardisiez d'autres données. Au lieu d'un grand verrou, vous obtiendrez un tas de petits verrous et ainsi vous éliminerez la contention de verrou.
Un autre moyen de résoudre le problème est d'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 pour l'écriture ou la mise à jour. Et à intervalles réguliers (par exemple, toutes les 100 ms ou 500 ms), vous les dupliquez et les échangez. Bien sûr, cette approche n'est applicable que dans les cas où votre application peut fonctionner avec un index de recherche légèrement obsolète.
Ces deux approches peuvent être utilisées simultanément : vous pouvez avoir un index versionné shardé.
Requêtes plus complexes
Le dernier problème des index bitmap est que, comme on nous le dit, ils ne conviennent pas bien aux types de requêtes plus complexes, comme les requêtes « par intervalle ».
En effet, si l'on y réfléchit, les opérations bit à bit comme AND, OR, etc., ne sont pas très adaptées aux requêtes de type « Montre-moi les hôtels avec un prix de chambre entre 200 et 300 dollars par nuit ».
Une solution naïve et très peu judicieuse serait de prendre les résultats pour chaque valeur en dollars et de les combiner avec une opération bit à bit OR.
Une solution un peu plus correcte serait d'utiliser le groupement. 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 représentation conçue spécifiquement pour ce type de requêtes. Dans les travaux de recherche, cela s'appelle des bitmaps codés par plage.
Dans cette représentation, nous n'attribuons pas simplement un bit pour une valeur donnée (par exemple, 200), mais nous définissons cette valeur et tout ce qui est au-dessus. 200 et plus. La même chose pour 300 : 300 et plus. Et ainsi de suite.
En utilisant cette représentation, nous pouvons répondre à ce genre de requêtes de recherche en parcourant l'index seulement deux fois. D'abord, nous obtenons la liste des hôtels où le tarif est inférieur à 300 dollars, puis nous éliminons ceux dont le tarif est inférieur à 199 dollars. C'est prêt.
Vous serez surpris, mais même les requêtes géospatiales sont possibles avec des index bitmap. Le truc est d'utiliser une représentation géographique qui entoure vos coordonnées avec une forme géométrique. Par exemple, S2 de Google. La forme doit pouvoir être représentée par trois lignes ou plus qui se croisent et que l'on peut numéroter. Ainsi, nous pourrons transformer notre requête géospatiale en plusieurs requêtes « par intervalle » (sur ces lignes numérotées).
Solutions prêtes à l'emploi
J'espère vous avoir intéressé un peu et que vous avez désormais un autre outil utile dans votre arsenal. Si jamais vous avez besoin de faire quelque chose de similaire, vous saurez dans quelle direction regarder.
Cependant, tout le monde n'a pas le temps, la patience et les ressources pour créer des index bitmap à partir de zéro. Surtout des index plus avancés utilisant SIMD, par exemple.
Heureusement, il existe plusieurs solutions toutes prêtes qui peuvent vous aider.
Bitmaps Roaring
Tout d'abord, il y a la bibliothèque roaring bitmaps que j'ai déjà mentionnée. Elle contient tous les conteneurs nécessaires et les opérations bit à bit dont vous aurez besoin pour créer un index bitmap complet.
Malheureusement, jusqu'à présent, aucune des réalisations en Go n'utilise SIMD, ce qui signifie que les réalisations en Go sont moins performantes que celles en C, par exemple.
Pilosa
Un autre produit qui peut vous aider est la base de données Pilosa, qui est essentiellement uniquement composée d'index bitmap. C'est une solution relativement nouvelle, mais qui conquiert les cœurs à une vitesse incroyable.
Pilosa utilise des bitmaps roaring en son sein et vous permet de les utiliser, simplifie et explique toutes les choses dont j'ai parlé ci-dessus : regroupement, bitmaps codés par plage, notion 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 déjà vu. Nous créons un client pour le serveur Pilosa, nous créons un index et les champs nécessaires, puis nous remplissons nos champs avec des données aléatoires selon des probabilités et, enfin, nous exécutons la requête familière.
Ensuite, nous utilisons NOT sur le champ « expensive », puis nous croisons le résultat (ou avec AND) avec le champ « terrace » et le champ « reservations ». Enfin, nous obtenons le résultat final.
J'espère vraiment qu'à l'avenir, des systèmes de gestion de bases de données comme MySQL et PostgreSQL introduiront également ce nouveau type d'index — les index bitmap.
Conclusion
Merci si vous ne vous êtes pas endormi. J'ai dû effleurer de nombreux sujets en raison du temps limité, mais j'espère que la présentation a été utile et peut-être même motivante.
Il est bon de connaître les index bitmap, même si vous n'en avez pas besoin pour l'instant. Qu'ils soient un outil supplémentaire dans votre boîte à outils.
Nous avons examiné divers trucs pour améliorer les performances de Go et les choses que le compilateur Go ne gère pas encore très bien. Cela, en revanche, est absolument essentiel à savoir pour tout programmeur Go.
C'est tout ce que je voulais dire. Merci !
Source : habr.com
