Tausende Manager aus Vertriebsbüros im ganzen Land melden sich Zehntausende Kontakte täglich — Fakten der Kommunikation mit potenziellen oder bereits mit uns zusammenarbeitenden Kunden. Und für diesen Kunden müssen Sie ihn zunächst finden, und zwar am besten sehr schnell. Und das geschieht am häufigsten namentlich.
Daher ist es nicht verwunderlich, dass wir erneut „schwere“ Abfragen in einer der am stärksten belasteten Datenbanken analysieren – unserer eigenen , ich fand „oben“ Abfrage zur „schnellen“ Suche nach Namen für Visitenkarten.
Darüber hinaus ergaben weitere Untersuchungen ein interessantes Beispiel Zuerst Optimierung, dann Leistungseinbußen Die Aufgabe wurde durch die konsequente Umsetzung mehrerer Teams, die jeweils nach bestem Wissen und Gewissen agierten, erfüllt.
0: Was wollte der Benutzer?
[KDPV ]
Was meint der Nutzer normalerweise, wenn er von einer „schnellen“ Suche nach Namen spricht? Es stellt sich fast nie heraus, dass es sich um eine „faire“ Teilzeichenfolgensuche handelt ... LIKE '%роза%' - schließlich ist das Ergebnis dann nicht nur 'Розалия' и 'Магазин Роза'Aber 'Гроза' und sogar 'Дом Деда Мороза'.
Der Benutzer bedeutet auf Haushaltsebene, dass Sie ihn bereitstellen Suche am Anfang eines Wortes im Titel und zeigen Sie relevanteres, was startet um trat ein. Und TU es fast augenblicklich - mit tiefgestellter Eingabe.
1: Begrenzen Sie die Aufgabe
Und noch mehr, eine Person wird nicht ausdrücklich vorgestellt 'роз магаз'Sie müssen also für jedes Wort ein Präfix suchen. Nein, es ist für einen Benutzer viel einfacher, auf einen kurzen Hinweis für das letzte Wort zu reagieren, als die vorherigen Wörter absichtlich „unterzubetreten“ – sehen Sie, wie eine Suchmaschine das herausfindet.
Im Allgemeinen richtig Die Anforderungen an das Problem zu formulieren ist mehr als die halbe Lösung. Manchmal sorgfältige Anwendungsfallanalyse .
Was macht ein abstrakter Entwickler?
1.0: externe Suchmaschine
Oh, die Suche ist schwierig, Sie möchten überhaupt nichts tun - geben wir es den Entwicklern! Lassen Sie sie für uns eine Suchmaschine außerhalb der Datenbank bereitstellen: Sphinx, ElasticSearch, ...
Eine funktionierende, wenn auch zeitaufwändige Option im Hinblick auf die Synchronisierung und Effizienz von Änderungen. In unserem Fall jedoch nicht, da die Suche für jeden Kunden nur im Rahmen seiner Kontodaten durchgeführt wird. Und die Daten haben eine ziemlich hohe Variabilität – und wenn jetzt der Manager eine Karte eingegeben hat 'Магазин Роза', dann kann er sich nach 5-10 Sekunden schon daran erinnern, dass er dort vergessen hat, die E-Mail anzugeben und möchte sie finden und reparieren.
Deshalb - lasst uns Suche „direkt in der Datenbank“. Glücklicherweise ermöglicht uns PostgreSQL dies und mehr als eine Option – wir werden sie in Betracht ziehen.
1.1: „ehrlicher“ Teilstring
Wir bleiben beim Wort „Teilstring“. Aber genau für die Indexsuche nach Teilzeichenfolgen (und sogar nach regulären Ausdrücken!) gibt es eine hervorragende Lösung ! Erst dann ist eine korrekte Sortierung erforderlich.
Versuchen wir der Einfachheit halber, das folgende Modell zu verwenden:
CREATE TABLE firms(
id
serial
PRIMARY KEY
, name
text
);Wir laden dort 7.8 Millionen Datensätze realer Organisationen hoch und indizieren sie:
CREATE EXTENSION pg_trgm;
CREATE INDEX ON firms USING gin(lower(name) gin_trgm_ops);Suchen wir nach den ersten 10 Datensätzen für die Suche nach Teilzeichenfolgen:
SELECT
*
FROM
firms
WHERE
lower(name) ~ ('(^|s)' || 'роза')
ORDER BY
lower(name) ~ ('^' || 'роза') DESC -- сначала "начинающиеся на"
, lower(name) -- остальное по алфавиту
LIMIT 10;
Na ja, so... 26 ms, 31 MB Lesen Sie Daten und mehr als 1.7 gefilterte Datensätze – für 10 durchsuchte Datensätze. Der Overhead ist zu hoch. Kann man etwas Effizienteres machen?
1.2: Textsuche? es ist FTS!
Tatsächlich bietet PostgreSQL eine sehr leistungsstarke Funktion (Volltextsuche), auch mit der Möglichkeit der Präfixsuche. Tolle Option, Sie müssen nicht einmal Erweiterungen installieren! Lass es uns versuchen:
CREATE INDEX ON firms USING gin(to_tsvector('simple'::regconfig, lower(name)));SELECT
*
FROM
firms
WHERE
to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*')
ORDER BY
lower(name) ~ ('^' || 'роза') DESC
, lower(name)
LIMIT 10;
Die Parallelisierung der Abfrageausführung hat uns hier ein wenig geholfen und die Zeit um die Hälfte verkürzt 11 ms. Ja, und wir mussten insgesamt 1.5-mal weniger lesen 20MB. Und hier gilt: Je weniger, desto besser, denn je größer das Volumen, das wir subtrahieren, desto höher ist die Wahrscheinlichkeit eines Cache-Fehlers, und jede zusätzliche Datenseite, die von der Festplatte gelesen wird, stellt eine potenzielle „Bremse“ für die Anforderung dar.
1.3: immer noch LIKE?
Die vorherige Anfrage ist für alle gut, aber nur, wenn Sie sie hunderttausend Mal am Tag aufrufen, wird sie ausgeführt 2TB Daten lesen. Bestenfalls aus dem Gedächtnis, aber wenn Sie Pech haben, dann von der Festplatte. Versuchen wir also, es kleiner zu machen.
Denken Sie daran, was der Benutzer sehen möchte zuerst „das fängt an mit...“. Es ist also in seiner reinsten Form. über text_pattern_ops! Und nur wenn wir bis zu 10 erforderliche Datensätze „nicht haben“, müssen wir diese mit der FTS-Suche lesen:
CREATE INDEX ON firms(lower(name) text_pattern_ops);SELECT
*
FROM
firms
WHERE
lower(name) LIKE ('роза' || '%')
LIMIT 10;
Hervorragende Leistung – insgesamt 0.05 ms und knapp über 100 KB lesen! Wir haben es einfach vergessen Nach Name sortierendamit sich der Nutzer nicht in den Ergebnissen verliert:
SELECT
*
FROM
firms
WHERE
lower(name) LIKE ('роза' || '%')
ORDER BY
lower(name)
LIMIT 10;
Oh, etwas ist nicht mehr so schön - es scheint, dass es einen Index gibt, aber das Sortieren fliegt daran vorbei ... Natürlich ist es schon um ein Vielfaches effizienter als die Vorgängerversion, aber ...
1.4: „Mit einer Datei abschließen“
Es gibt jedoch einen Index, mit dem Sie nach Bereichen suchen können, und es ist normal, die Sortierung zu verwenden – regulärer Btree!
CREATE INDEX ON firms(lower(name));Lediglich die Anfrage dafür muss „manuell zusammengestellt“ werden:
SELECT
*
FROM
firms
WHERE
lower(name) >= 'роза' AND
lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых - chr(255)
ORDER BY
lower(name)
LIMIT 10;
Hervorragend – und die Sortierung funktioniert, und der Ressourcenverbrauch bleibt „mikroskopisch“, tausendmal effektiver als „reines“ FTS! Es bleibt noch, in einer einzigen Anfrage Folgendes zu sammeln:
(
SELECT
*
FROM
firms
WHERE
lower(name) >= 'роза' AND
lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых кодировок - chr(255)
ORDER BY
lower(name)
LIMIT 10
)
UNION ALL
(
SELECT
*
FROM
firms
WHERE
to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*') AND
lower(name) NOT LIKE ('роза' || '%') -- "начинающиеся на" мы уже нашли выше
ORDER BY
lower(name) ~ ('^' || 'роза') DESC -- используем ту же сортировку, чтобы НЕ пойти по btree-индексу
, lower(name)
LIMIT 10
)
LIMIT 10;
Beachten Sie, dass die zweite Unterabfrage ausgeführt wird nur, wenn der erste weniger zurückgab als erwartet zuletzt LIMIT anzahl der Zeilen. Über diese Art der Abfrageoptimierung, I .
Also ja, wir haben jetzt Btree und Gin gleichzeitig auf dem Tisch, aber statistisch gesehen hat es sich herausgestellt Weniger als 10 % der Anfragen erreichen die Ausführung des zweiten Blocks. Das heißt, mit solchen typischen Einschränkungen für die Aufgabe, die im Voraus bekannt waren, konnten wir den Gesamtverbrauch an Serverressourcen um fast das Tausendfache reduzieren!
1.5*: Auf eine Datei verzichten
Oben LIKE Wir wurden daran gehindert, die falsche Sortierung zu verwenden. Es kann jedoch durch Angabe des USING-Operators „auf den richtigen Weg gebracht“ werden:
Die Standardeinstellung ist
ASC. Darüber hinaus können Sie in der Klausel den Namen eines bestimmten Sortieroperators angebenUSING. Der Sortieroperator muss ein „kleiner als“ oder „größer als“-Mitglied einer Familie von B-Tree-Operatoren sein.ASCnormalerweise gleichwertigUSING <иDESCnormalerweise gleichwertigUSING >.
In unserem Fall ist „weniger“. ~<~:
SELECT
*
FROM
firms
WHERE
lower(name) LIKE ('роза' || '%')
ORDER BY
lower(name) USING ~<~
LIMIT 10;
2: Wie Anfragen sauer werden
Jetzt lassen wir unsere Anfrage sechs Monate oder ein Jahr lang „brauen“ und finden sie überrascht wieder „ganz oben“ mit Indikatoren für das gesamte tägliche „Pumpen“ des Gedächtnisses (Puffert gemeinsam genutzten Treffer) Im 5.5TB - also sogar mehr als ursprünglich.
Nein, natürlich, und unser Geschäft ist gewachsen und die Arbeitsbelastung ist gestiegen, aber nicht im gleichen Maße! Hier stimmt also etwas nicht – lasst es uns herausfinden.
2.1: Die Geburt des Paging
Irgendwann wollte ein anderes Entwicklungsteam es ermöglichen, aus einer schnellen tiefgestellten Suche mit denselben, aber erweiterten Ergebnissen in die Registrierung zu „springen“. Und welches Register ohne Paginierung? Lass es uns vermasseln!
( ... LIMIT <N> + 10)
UNION ALL
( ... LIMIT <N> + 10)
LIMIT 10 OFFSET <N>;Jetzt war es dem Entwickler möglich, das Suchergebnisregister mit einem „Seitentyp“-Ladevorgang ohne Anstrengung anzuzeigen.
Natürlich, in der Tat, Mit jeder nächsten Datenseite wird immer mehr gelesen (alles aus der vorherigen Zeit, was wir verwerfen, plus den gewünschten „Schwanz“) – das heißt, dies ist ein eindeutiges Anti-Muster. Und es wäre richtiger, die Suche bei der nächsten Iteration mit dem in der Schnittstelle gespeicherten Schlüssel zu starten, aber dazu ein anderes Mal mehr.
2.2: Lust auf Exotik
Irgendwann wollte der Entwickler Diversifizieren Sie die resultierende Stichprobe mit Daten aus einer anderen Tabelle, für die die gesamte vorherige Abfrage an den CTE gesendet wurde:
WITH q AS (
...
LIMIT <N> + 10
)
SELECT
*
, (SELECT ...) sub_query -- какой-то запрос к связанной таблице
FROM
q
LIMIT 10 OFFSET <N>;Und trotzdem nicht schlecht, denn die Unterabfrage wird nur für 10 zurückgegebene Datensätze ausgewertet, wenn nicht ...
2.3: AUSGEZEICHNET sinnlos und gnadenlos
Irgendwo im Prozess einer solchen Entwicklung ab der 2. Unterabfrage hat verloren NOT LIKE Zustand. Es ist klar, dass danach UNION ALL begann zurückzukehren einige Einträge doppelt - zuerst am Anfang der Zeile und dann noch einmal am Anfang des ersten Wortes dieser Zeile gefunden. Im Limit könnten alle Datensätze der 2. Unterabfrage mit den Datensätzen der ersten übereinstimmen.
Was macht ein Entwickler, anstatt nach einem Grund zu suchen?... Keine Frage!
- doppelt so groß Erstmuster
- UNTERSCHIEDLICH auferlegenum nur einzelne Instanzen jeder Zeile zu erhalten
WITH q AS (
( ... LIMIT <2 * N> + 10)
UNION ALL
( ... LIMIT <2 * N> + 10)
LIMIT <2 * N> + 10
)
SELECT DISTINCT
*
, (SELECT ...) sub_query
FROM
q
LIMIT 10 OFFSET <N>;Das heißt, es ist klar, dass das Ergebnis am Ende genau das gleiche ist, aber die Chance, in die 2. CTE-Unterabfrage zu „fliegen“, ist viel höher geworden, und auch ohne sie deutlich mehr lesen.
Aber das ist nicht das Traurigste. Da der Entwickler um Auswahl gebeten hat DISTINCT nicht für bestimmte, sondern für alle Felder gleichzeitig Datensätze, dann wird das Feld sub_query automatisch einbezogen – das Ergebnis der Unterabfrage. Nun zur Ausführung DISTINCT, die Datenbank musste bereits ausgeführt werden nicht 10 Unterabfragen, sondern alle <2 * N> + 10!
2.4: Zusammenarbeit steht an erster Stelle!
Also lebten die Entwickler - sie trauerten nicht, denn in der Registrierung „vermasselten“ sie signifikante N-Werte mit einer chronischen Verlangsamung beim Abrufen jeder nächsten „Seite“, der Benutzer hatte offensichtlich nicht die Geduld.
Bis Entwickler aus einer anderen Abteilung zu ihnen kamen und eine so bequeme Methode nicht nutzen wollten für iterative Suche - das heißt, wir nehmen ein Stück aus einer Stichprobe, filtern nach zusätzlichen Bedingungen, zeichnen das Ergebnis, dann das nächste Stück (was in unserem Fall durch Erhöhen von N erreicht wird) und so weiter, bis wir den Bildschirm füllen.
Im Allgemeinen bei einem gefangenen Exemplar N hat fast 17 erreicht, und in nur einem Tag wurden mindestens 4 solcher Anfragen „entlang der Kette“ ausgeführt. Der letzte von ihnen scannte bereits kühn vorbei 1 GB Speicher pro Iteration...
Insgesamt
Source: habr.com