AllYouNeedIsBackend

Je suis un grand fan des bases de données. J’ai même voulu créer mon propre SGBD lorsque j’étais à l’université. Maintenant, je travaille à la fois avec des SGBD et des solutions NoSQL, et je suis très enthousiaste à ce sujet. Vous savez, il n’y a pas de marteau d’or, chaque problème a sa propre solution. Alternativement, un sous-ensemble de solutions.

Dans la série de billets de blog Le SQL que j’aime <3 je vous promène à travers quelques problèmes résolus avec SQL que j’ai trouvé particulièrement intéressants. Les solutions sont testées en utilisant une table avec plus de 100 millions d’enregistrements. Tous les exemples utilisent MySQL, mais les idées s’appliquent à d’autres magasins de données relationnelles comme PostgreSQL, Oracle et SQL Server.

Ce chapitre est axé sur l’analyse efficace d’une grande table en utilisant la pagination avec offset sur la clé primaire. Ceci est également connu sous le nom de pagination de keyset.

Background

Dans le chapitre, nous utilisons la structure de base de données suivante pour exemple. L’exemple canonique sur les utilisateurs devrait convenir à n’importe quel domaine.

CREATE TABLE `users` ( `user_id` int(11) unsigned NOT NULL AUTO_INCREMENT, `external_id` varchar(32) NOT NULL, `name` varchar(100) COLLATE utf8_unicode_ci NOT NULL, `metadata` text COLLATE utf8_unicode_ci, `date_created` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP, PRIMARY KEY (`user_id`), UNIQUE KEY `uf_uniq_external_id` (`external_id`), UNIQUE KEY `uf_uniq_name` (`name`), KEY `date_created` (`date_created`)) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci;

Quelques commentaires sur la structure :

• external_id colonne stocke la référence au même utilisateur dans un autre système au format UUID
• name représente Firstname Lastname
• metadata colonne contient un blob JSON avec toutes sortes de données non structurées

La table est relativement grande et contient environ 100 000 000 enregistrements. Commençons notre voyage d’apprentissage.

Scanning a Large Table

Problème : Vous devez parcourir la table, extraire chaque enregistrement, le transformer à l’intérieur du code de votre application et l’insérer à un autre endroit. Nous nous concentrons sur la première étape dans le post – le balayage de la table.

Solution évidente et mauvaise

SELECT user_id, external_id, name, metadata, date_createdFROM users;

Dans mon cas avec 100 000 000 d’enregistrements, la requête n’est jamais terminée. Le SGBD la tue tout simplement. Pourquoi ? Probablement, parce qu’elle a conduit à la tentative de charger toute la table en RAM. Avant de renvoyer les données au client. Autre hypothèse : le préchargement des données avant l’envoi a pris trop de temps et la requête s’est arrêtée. Quoi qu’il en soit, notre tentative d’obtenir tous les enregistrements dans les temps a échoué. Nous devons trouver une autre solution.

Solution #2

Nous pouvons essayer d’obtenir les données en pages. Comme les enregistrements ne sont pas garantis d’être ordonnés dans une table au niveau physique ou logique – nous devons les trier du côté du SGBD avec la clause ORDER BY.

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 0, 10 000;10 000 rows in set (0.03 sec)

Sweet. Cela a fonctionné. Nous avons demandé la première page de 10 000 enregistrements, et il n’a fallu que 0.03sec pour la retourner. Cependant, comment cela fonctionnerait-il pour la 5000ème page ?

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 50 000 000, 10 000; --- 5 000th page * 10 000 page size10 000 rows in set (40.81 sec)

En effet, c’est très lent. Voyons combien de temps est nécessaire pour obtenir les données de la dernière page.

SELECT user_id, external_id, name, metadata, date_createdFROM usersORDER BY user_id ASCLIMIT 99 990 000, 10 000; --- 9999th page * 10 000 page size10 000 rows in set (1 min 20.61 sec)

C’est insensé. Cependant, peut être OK pour les solutions qui fonctionnent en arrière-plan. Un autre problème caché avec l’approche peut être révélé si vous essayez de supprimer un enregistrement de la table au milieu de l’analyse. Disons que vous avez terminé la 10ème page (100 000 enregistrements ont déjà été visités) et que vous allez scanner les enregistrements entre 100 001 et 110 000. Mais les enregistrements 99 998 et 99 999 sont supprimés avant l’exécution suivante SELECT. Dans ce cas, la requête suivante renvoie le résultat inattendu :

 SELECT user_id, external_id, name, metadata, date_created FROM users ORDER BY user_id ASC LIMIT 100 000, 10 000; N, id, ... 1, 100 003, ... 2, 100 004, ...

Comme vous pouvez le voir, la requête a sauté les enregistrements avec les ids 100 001 et 100 002. Ils ne seront pas traités par le code de l’application avec l’approche car après les deux opérations de suppression, ils apparaissent dans les 100 000 premiers enregistrements. Par conséquent, la méthode n’est pas fiable si le jeu de données est mutable.

Solution #3 – la dernière pour aujourd’hui

L’approche est très similaire à la précédente car elle utilise toujours la pagination, mais maintenant, au lieu de s’appuyer sur le nombre d’enregistrements scannés, nous utilisons le user_id du dernier enregistrement visité comme offset.

Algorithme simplifié:

1. Nous obtenons PAGE_SIZE nombre d’enregistrements de la table. La valeur de décalage de départ est 0.
2. Utiliser la valeur maximale retournée pour user_id dans le lot comme décalage pour la page suivante.
3. Recevoir le lot suivant à partir des enregistrements qui ont une valeur user_id supérieure à la valeur offset actuelle.

La requête en action pour la 5 000e page, chaque page contient des données sur 10 000 utilisateurs :

SELECT user_id, external_id, name, metadata, date_createdFROM usersWHERE user_id > 51 234 123 --- value of user_id for 50 000 000th recordORDER BY user_id ASCLIMIT 10 000;10 000 rows in set (0.03 sec)

Notez, que les valeurs de user_id ne sont pas séquentielles et peuvent avoir des écarts comme 25 348 est juste après 25 345. La solution fonctionne également si tous les enregistrements des pages futures sont supprimés – même dans ce cas, la requête ne saute pas les enregistrements. Super, non ?

Explication des performances

Pour un apprentissage plus approfondi, je recommande d’étudier les résultats de EXPLAIN EXTENDED pour chaque version de la requête pour obtenir les 10 000 enregistrements suivants après 50 000 000.

Mettons l’accent sur la différence essentielle entre les plans d’exécution des 2e et 3e solutions puisque la 1re n’est pas utile en pratique pour les grandes tables.

• Type de jointure : index vs range. Le premier signifie que tout l’arbre d’index est balayé pour trouver les enregistrements. Le type range nous indique que l’index est utilisé uniquement pour trouver les lignes correspondantes dans une plage spécifiée. Donc, le type range est plus rapide que index.
• Clés possibles : NULL vs PRIMARY. La colonne montre les clés qui peuvent être utilisées par MySQL. BTW, en regardant la colonne des clés, nous pouvons voir que finalement la clé PRIMARY est utilisée pour les deux requêtes.
• Rows : 50 010 000 vs 50 000 000. La valeur affiche un nombre d’enregistrements analysés avant de renvoyer le résultat. Pour la 2ème requête, la valeur dépend de la profondeur de notre scroll. Par exemple, si nous essayons d’obtenir les 10 000 enregistrements suivants après la 9999e page, alors 99 990 000 enregistrements sont examinés. À l’inverse, la troisième requête a une valeur constante ; peu importe que nous chargions les données de la première ou de la toute dernière page. C’est toujours la moitié de la taille de la table.
• Filtré : 200.00 vs 100.00. Cette colonne indique estimé le pourcentage de la table à filtrer avant traitement. Avoir la valeur la plus élevée est meilleur. La valeur de 100.00 signifie que la requête passe en revue l’ensemble de la table. Pour la 2ème requête, la valeur n’est pas constante et dépend du numéro de page : si nous demandons la 1ère page, la valeur de la colonne filtrée serait 1000000.00. Pour la toute dernière page, elle serait 100.00.
• Extra : NULL vs Using where. Fournit des informations supplémentaires sur la façon dont MySQL résout la requête. L’utilisation de WHERE sur la clé PRIMARY rend l’exécution de la requête plus rapide.

Je soupçonne que le type de jointure est le paramètre de la requête qui a le plus contribué aux performances pour rendre la 3e requête plus rapide. Une autre chose importante est que la 2e requête est extrêmement dépendante du nombre de pages à faire défiler. Une pagination plus profonde est plus lente dans ce cas.

Plus d’indications sur la compréhension de la sortie de la commande EXPLAIN peuvent être trouvées dans la documentation officielle de votre SGBDR.

Résumé

Le sujet principal pour le billet de blog était lié à l’analyse d’une grande table avec 100 000 000 d’enregistrements en utilisant offset avec une clé primaire (keyset pagination). Dans l’ensemble, 3 approches différentes ont été examinées et testées sur le jeu de données correspondant. Je ne recommande qu’une seule d’entre elles si vous avez besoin de scanner une grande table mutable.

En outre, nous avons révisé l’utilisation de la commande EXPLAIN EXTENDED pour analyser le plan d’exécution des requêtes MySQL. Je suis sûr que d’autres SGBDR ont des analogues pour cette fonctionnalité.

Dans le prochain chapitre, nous prêterons attention à l’agrégation de données et à l’optimisation du stockage. Restez à l’écoute !

Quelle est votre méthode d’analyse des grandes tables ?

Vous souvenez-vous d’un autre objectif de l’utilisation de la pagination des keysets comme dans la solution n°3 ?

.