In regelmäßigen Abständen stellt sich die Aufgabe, anhand einer Reihe von Schlüsseln nach verwandten Daten zu suchen. bis wir die erforderliche Gesamtzahl an Datensätzen erhalten.
Das „lebensechteste“ Beispiel ist die Anzeige 20 älteste Probleme, aufgeführt auf der Mitarbeiterliste (zum Beispiel innerhalb derselben Abteilung). Für verschiedene Management-Dashboards mit kurzen Zusammenfassungen der Arbeitsbereiche wird häufig ein ähnliches Thema benötigt.
In dem Artikel betrachten wir die Implementierung einer „naiven“ Version zur Lösung eines solchen Problems, eines „intelligenteren“ und sehr komplexen Algorithmus, auf PostgreSQL „Schleife“ in SQL mit einer Exit-Bedingung aus den gefundenen Daten, was sowohl für die allgemeine Entwicklung als auch für den Einsatz in anderen ähnlichen Fällen nützlich sein kann.
Nehmen wir einen Testdatensatz von . Damit die Ausgabedatensätze nicht von Zeit zu Zeit „springen“, wenn die sortierten Werte übereinstimmen, Erweitern Sie den Themenindex durch Hinzufügen eines Primärschlüssels. Gleichzeitig verleiht es ihm sofort Einzigartigkeit und garantiert uns die Einzigartigkeit der Sortierreihenfolge:
CREATE INDEX ON task(owner_id, task_date, id);
-- а старый - удалим
DROP INDEX task_owner_id_task_date_idx;So wie es gehört wird, so steht es auch geschrieben
Lassen Sie uns zunächst die einfachste Version der Anfrage skizzieren und dabei die IDs der Ausführenden übergeben :
SELECT
*
FROM
task
WHERE
owner_id = ANY('{1,2,4,8,16,32,64,128,256,512}'::integer[])
ORDER BY
task_date, id
LIMIT 20;
Ein bisschen traurig – wir haben nur 20 Platten bestellt und Index Scan hat uns zurückgeschickt 960 Begriff, die dann auch sortiert werden musste ... Und versuchen wir, weniger zu lesen.
unnest + ARRAY
Die erste Überlegung, die uns helfen wird – wenn wir es brauchen insgesamt 20 sortiert Aufzeichnungen, es reicht zum Lesen jeweils nicht mehr als 20 in der gleichen Reihenfolge sortiert Schlüssel. Gut, passender Index (owner_id, task_date, id) wir haben.
Lassen Sie uns den gleichen Mechanismus zum Extrahieren und „Umwandeln in Spalten“ verwenden. integraler Tabelleneintrag, wie in . Und wenden Sie die Faltung mithilfe der Funktion auch auf ein Array an ARRAY():
WITH T AS (
SELECT
unnest(ARRAY(
SELECT
t
FROM
task t
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 20 -- ограничиваем тут...
)) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
(r).*
FROM
T
ORDER BY
(r).task_date, (r).id
LIMIT 20; -- ... и тут - тоже
Oh, es ist schon viel besser! 40 % schneller und 4.5-mal weniger Daten musste lesen.
Materialisierung von Tabellendatensätzen über CTEIch werde das zur Kenntnis nehmen in einigen Fällen Ein Versuch, sofort mit den Datensatzfeldern zu arbeiten, nachdem in einer Unterabfrage danach gesucht wurde, ohne sie in einen CTE einzuschließen, kann dazu führen „Multiplikation“ InitPlan proportional zur Anzahl dieser Felder:
SELECT
((
SELECT
t
FROM
task t
WHERE
owner_id = 1
ORDER BY
task_date, id
LIMIT 1
).*);Result (cost=4.77..4.78 rows=1 width=16) (actual time=0.063..0.063 rows=1 loops=1)
Buffers: shared hit=16
InitPlan 1 (returns $0)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.031..0.032 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t (cost=0.42..387.57 rows=500 width=48) (actual time=0.030..0.030 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
InitPlan 2 (returns $1)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.009 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_1 (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
InitPlan 3 (returns $2)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_2 (cost=0.42..387.57 rows=500 width=48) (actual time=0.008..0.008 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4"
InitPlan 4 (returns $3)
-> Limit (cost=0.42..1.19 rows=1 width=48) (actual time=0.009..0.009 rows=1 loops=1)
Buffers: shared hit=4
-> Index Scan using task_owner_id_task_date_id_idx on task t_3 (cost=0.42..387.57 rows=500 width=48) (actual time=0.009..0.009 rows=1 loops=1)
Index Cond: (owner_id = 1)
Buffers: shared hit=4
Derselbe Datensatz wurde viermal „durchsucht“ … Bis PostgreSQL 4 trat dieses Verhalten regelmäßig auf, und die Lösung besteht darin, einen CTE „einzuschließen“, der in diesen Versionen eine unbedingte Grenze für den Optimierer darstellt.
rekursiver Akkumulator
In der vorherigen Version haben wir insgesamt gelesen 200 Begriff um der notwendigen 20 willen. Schon nicht 960, sondern noch weniger - ist das möglich?
Versuchen wir, das Wissen zu nutzen, das wir brauchen gesamt 20 Aufzeichnungen. Das heißt, wir wiederholen die Datensubtraktion nur so lange, bis die benötigte Menge erreicht ist.
Schritt 1: Startliste
Offensichtlich sollte unsere „Ziel“-Liste mit 20 Einträgen mit den „ersten“ Einträgen für einen unserer Owner_ID-Schlüssel beginnen. Deshalb finden wir zunächst solche „Allererste“ für jede der Tasten und fügen Sie es in die Liste ein und sortieren Sie es in der gewünschten Reihenfolge - (task_date, id).
Schritt 2: Finden Sie die „nächsten“ Datensätze
Nehmen wir nun den ersten Eintrag aus unserer Liste und beginnen „Schritt“ weiter nach unten im Index Mit dem Speichern des Owner_ID-Schlüssels sind alle gefundenen Datensätze nur die nächsten in der resultierenden Auswahl. Natürlich nur bis wir den angewandten Schlüssel kreuzen zweiter Eintrag in der Liste.
Wenn sich herausstellte, dass wir den zweiten Eintrag „überquert“ haben, dann Der zuletzt gelesene Eintrag sollte anstelle des ersten zur Liste hinzugefügt werden (mit der gleichen Owner_ID), danach wird die Liste erneut sortiert.
Das heißt, wir erhalten immer, dass die Liste nicht mehr als einen Eintrag für jeden Schlüssel enthält (wenn die Einträge zu Ende sind und wir uns nicht „gekreuzt“ haben, verschwindet der erste Eintrag einfach aus der Liste und es wird nichts hinzugefügt ), und sie immer sortiert in aufsteigender Reihenfolge des Anwendungsschlüssels (task_date, id).
Schritt 3: Datensätze filtern und erweitern
Im Teil der Zeilen unserer rekursiven Auswahl befinden sich einige Datensätze rv werden dupliziert - zuerst finden wir z. B. „Überschreiten der Grenze des 2. Eintrags der Liste“ und ersetzen ihn dann als 1. aus der Liste. Daher sollte das erste Vorkommen herausgefiltert werden.
Schreckliche letzte Frage
WITH RECURSIVE T AS (
-- #1 : заносим в список "первые" записи по каждому из ключей набора
WITH wrap AS ( -- "материализуем" record'ы, чтобы обращение к полям не вызывало умножения InitPlan/SubPlan
WITH T AS (
SELECT
(
SELECT
r
FROM
task r
WHERE
owner_id = unnest
ORDER BY
task_date, id
LIMIT 1
) r
FROM
unnest('{1,2,4,8,16,32,64,128,256,512}'::integer[])
)
SELECT
array_agg(r ORDER BY (r).task_date, (r).id) list -- сортируем список в нужном порядке
FROM
T
)
SELECT
list
, list[1] rv
, FALSE not_cross
, 0 size
FROM
wrap
UNION ALL
-- #2 : вычитываем записи 1-го по порядку ключа, пока не перешагнем через запись 2-го
SELECT
CASE
-- если ничего не найдено для ключа 1-й записи
WHEN X._r IS NOT DISTINCT FROM NULL THEN
T.list[2:] -- убираем ее из списка
-- если мы НЕ пересекли прикладной ключ 2-й записи
WHEN X.not_cross THEN
T.list -- просто протягиваем тот же список без модификаций
-- если в списке уже нет 2-й записи
WHEN T.list[2] IS NULL THEN
-- просто возвращаем пустой список
'{}'
-- пересортировываем словарь, убирая 1-ю запись и добавляя последнюю из найденных
ELSE (
SELECT
coalesce(T.list[2] || array_agg(r ORDER BY (r).task_date, (r).id), '{}')
FROM
unnest(T.list[3:] || X._r) r
)
END
, X._r
, X.not_cross
, T.size + X.not_cross::integer
FROM
T
, LATERAL(
WITH wrap AS ( -- "материализуем" record
SELECT
CASE
-- если все-таки "перешагнули" через 2-ю запись
WHEN NOT T.not_cross
-- то нужная запись - первая из спписка
THEN T.list[1]
ELSE ( -- если не пересекли, то ключ остался как в предыдущей записи - отталкиваемся от нее
SELECT
_r
FROM
task _r
WHERE
owner_id = (rv).owner_id AND
(task_date, id) > ((rv).task_date, (rv).id)
ORDER BY
task_date, id
LIMIT 1
)
END _r
)
SELECT
_r
, CASE
-- если 2-й записи уже нет в списке, но мы хоть что-то нашли
WHEN list[2] IS NULL AND _r IS DISTINCT FROM NULL THEN
TRUE
ELSE -- ничего не нашли или "перешагнули"
coalesce(((_r).task_date, (_r).id) < ((list[2]).task_date, (list[2]).id), FALSE)
END not_cross
FROM
wrap
) X
WHERE
T.size < 20 AND -- ограничиваем тут количество
T.list IS DISTINCT FROM '{}' -- или пока список не кончился
)
-- #3 : "разворачиваем" записи - порядок гарантирован по построению
SELECT
(rv).*
FROM
T
WHERE
not_cross; -- берем только "непересекающие" записи
Also wir 50 % Datenlesevorgänge wurden gegen 20 % Ausführungszeit eingetauscht. Das heißt, wenn Sie Grund zu der Annahme haben, dass das Lesen lange dauern kann (z. B. befinden sich die Daten häufig nicht im Cache und Sie müssen dafür auf die Festplatte gehen), können Sie sich auf diese Weise darauf verlassen, dass das Lesen kürzer ist.
Auf jeden Fall fiel die Ausführungszeit besser aus als bei der „naiven“ ersten Option. Welche dieser drei Optionen Sie nutzen, liegt jedoch bei Ihnen.
Source: habr.com