Warum ist es langsam, wenn Limit- und Offset-Paging-Szenarien verwendet werden?

Beginnen wir mit einer Frage

Als ich vor fünf Jahren bei Tencent war, stellte ich fest, dass die MySQL-Anforderungsgeschwindigkeit in Paging-Szenarien sehr langsam war. Wenn das Datenvolumen nur 10 W beträgt, dauert die Auswahl von xx von einer einzelnen Maschine etwa 2 bis 3 Sekunden.

Ich fragte meinen Meister nach dem Grund und er antwortete: „Wie hoch ist im Indexszenario die zeitliche Komplexität, um die n-te größte Zahl in MySQL zu erhalten?“

Die Suche nach Antworten

Bestätigen Sie das Szenario

Nehmen Sie an, dass ein Statusindex vorhanden ist. Wählen Sie * aus der Tabelle, wobei Status = xx, Limit 10, Offset 10000 ist.

Es wird sehr langsam sein. Bei kleineren Datenmengen kommt es zu einer Verzögerung von mehreren Sekunden.

Xiaobai antwortet

Damals fühlte ich mich sehr sicher. Mein Lehrer würde sich um mich kümmern, egal was passierte. Meine technischen Fähigkeiten waren sowieso die schlechtesten in der Gruppe, also machte ich eine blinde Vermutung und dachte, dass das Finden eines Knotens einfach log(N) sein würde. Natürlich ließ mich mein Meister es im Selbststudium lernen.

Dieser Schritt dauerte 10 Minuten.

Weiter beantworten

Bei sorgfältiger Analyse werden Sie feststellen, dass die Suche im Index umständlich ist. Da Sie die Verteilung der ersten 100 Zahlen im linken und rechten Teilbaum nicht kennen, ist es unmöglich, die Sucheigenschaften des Binärbaums zu verwenden.

Durch Lernen habe ich erfahren, dass der Index von MySQL ein B+-Baum ist.

Nach dem Betrachten dieses Bildes wurde alles klar. Der 100. größte Baum kann direkt über die aus Blattknoten bestehende verknüpfte Liste mit einer Komplexität von O(n) gefunden werden. Aber selbst wenn es O(n) ist, ist es nicht so langsam, dass es unverschämt wäre. Gibt es dafür einen Grund?

In dieser Phase suchte ich hauptsächlich online nach Informationen und nahm dafür mit Unterbrechungen jeweils 10 Tage in Anspruch.

Systemisches Lernen

Hier sind zwei Bücher zu empfehlen. Eines davon ist „MySQL Technology Insider InnoDB Storage Engine“, mit dem Sie ein tieferes Verständnis des Implementierungsmechanismus von InnoDB wie MVCC, Indeximplementierung und Dateispeicherung erhalten.

Das zweite ist „High Performance MySQL“, das auf der Nutzungsebene beginnt, aber in die Tiefe geht und viele Designideen erwähnt.

Durch die Kombination der beiden Bücher und wiederholtes Studium können Sie MySQL kaum meistern.

Hier gibt es zwei Schlüsselkonzepte:

• Clustered-Index: enthält den Primärschlüsselindex und die entsprechenden tatsächlichen Daten. Der Blattknoten des Index ist der Datenknoten.
• Hilfsindex: Er kann als sekundärer Knoten verstanden werden, dessen Blattknoten auch ein Indexknoten ist und die Primärschlüssel-ID enthält.

Auch wenn die ersten 10.000 weggeworfen werden, verwendet MySQL die Primärschlüssel-ID des Sekundärindex, um die Daten im Clusterindex zu überprüfen. Dies sind 10.000 zufällige IOs, daher ist es natürlich so langsam wie ein Husky.

Sie fragen sich vielleicht, warum dieses Verhalten auftritt. Dies hängt mit der Schichtung von MySQL zusammen. Der Grenzoffset kann nur für den von der Engine-Schicht zurückgegebenen Ergebnissatz verwendet werden. Mit anderen Worten, auch die Motorebene ist unschuldig und weiß nicht, dass diese 10.000 Teile weggeworfen werden.

Nachfolgend sehen Sie ein Diagramm der MySQL-Schichtung. Sie können erkennen, dass die Engine-Schicht und die Server-Schicht tatsächlich getrennt sind.

Bis zu diesem Punkt habe ich den Grund für die Langsamkeit ungefähr verstanden. Diese Phase dauerte ein Jahr.

durch Analogie verstehen

Ich hatte zu diesem Zeitpunkt bereits drei Jahre daran gearbeitet und begann, mir den Quellcode anzusehen. Nachdem ich etcd gelesen hatte, habe ich etwas TiDB-Quellcode gelesen. Unabhängig vom Datenbanktyp besteht eine Abfrageanweisung tatsächlich aus logischen Operatoren.

Einführung in logische Operatoren

Bevor wir spezifische Optimierungsregeln schreiben, stellen wir kurz einige logische Operatoren im Abfrageplan vor.

• DataSource ist die Datenquelle, also die Tabelle t in select * from t.
• Auswahl, z. B. „Select xxx from t where xx = 5“, wobei die Filterbedingung lautet.
• Projektion, das Auswählen von c aus t in der Abfrage „select c from t“ ist eine Projektionsoperation.
• Verbindung verbinden, xx aus t1, t2 auswählen, wobei t1.c = t2.c bedeutet, die beiden Tabellen t1 und t2 zu verbinden.

Auswahl, Projektion und Verknüpfung (kurz SPJ) sind die grundlegendsten Operatoren. Es gibt viele Verbindungsmodi, darunter Inner Join, Left Outer Join, Right Outer Join usw.

Nachdem „select b from t1, t2“ (wobei t1.c = t2.c und t1.a > 5) zu einem logischen Abfrageplan geworden ist, ist die DataSource, die t1 t2 entspricht, für das Abrufen der Daten verantwortlich.

Oben wird ein Join-Operator hinzugefügt, um die Ergebnisse der beiden Tabellen gemäß t1.c = t2.c zu verbinden, dann wird ein Auswahlfilter gemäß t1.a > 5 ausgeführt und schließlich wird Spalte b projiziert.

Die folgende Abbildung ist eine nicht optimierte Darstellung:

Es liegt also nicht daran, dass MySQL Limit und Offset nicht an die Engine-Ebene übergeben möchte, sondern daran, dass die logischen Operatoren aufgeteilt sind und es deshalb unmöglich ist, herauszufinden, wie viele qualifizierte Daten der jeweilige Operator enthält.

Wie man es löst

"High Performance MySQL" nennt zwei Lösungen

Lösung 1

Prüfen Sie entsprechend den tatsächlichen Geschäftsanforderungen, ob es durch die Funktionen „Nächste Seite“ und „Vorherige Seite“ ersetzt werden kann, insbesondere unter iOS und Android, wo die vorherige vollständige Seitenumschaltung nicht üblich war.

Hier werden Limit und Offset durch den Hilfsindex (also die Suchbedingung) id ersetzt. Wenn die ID erneut aufgerufen wird, muss sie an das Front-End zurückgegeben werden.

Lösung 2

Stellen Sie sich der Sache direkt. Hier ist ein Konzept: Indexabdeckung: Wenn die vom Hilfsindex abgefragten Daten nur die ID und den Hilfsindex selbst enthalten, muss der gruppierte Index nicht abgefragt werden.

Die Idee ist wie folgt: select xxx,xxx from in (select id from table where second_index = xxx limit 10 offset 10000) Dieser Satz bedeutet, dass wir zuerst nach dem eindeutigen Datenbank-ID-Wert suchen, der den Daten aus der bedingten Abfrage entspricht. Da sich der Primärschlüssel bereits im Sekundärindex befindet, muss er nicht zur Festplatte des Clustered-Index zurückkehren, um ihn abzurufen. Verwenden Sie dann diese 10 begrenzten Primärschlüssel-IDs, um den gruppierten Index abzufragen. Dadurch werden nur zehn zufällige E/A-Vorgänge durchgeführt.

Wenn das Unternehmen Paging wirklich benötigt, kann der Einsatz dieser Lösung die Leistung erheblich verbessern. Erfüllt normalerweise die Leistungsanforderungen.

Abschließende Gedanken

Ich bin meinem Meister für seine Anleitung und Geduld in den drei Jahren vor meinem Abschluss sehr dankbar. Er gab mir in den Ferien Leseaufgaben, überprüfte in der Mittagspause meinen Lernfortschritt und leitete mich an, Probleme durch Fragen zu ergründen. Nach meinem Abschluss bei Tencent gab er mir bei jedem Treffen viele Ratschläge, vermittelte mir sein Wissen, beantwortete meine Fragen und gab in jeder Hinsicht sein Bestes.

Das Obige ist der vollständige Inhalt dieses Artikels. Ich hoffe, er wird für jedermanns Studium hilfreich sein. Ich hoffe auch, dass jeder 123WORDPRESS.COM unterstützen wird.