Und selbst bei Implementierungen im Code, einschließlich JavaScript, gibt es viele - vom "Canonical" von John Resig über verschiedene optimierte Versionen bis hin zu einer Reihe von Modulen in NPM .
Warum mussten wir es für einen Dienst zum Sammeln und Analysieren von PostgreSQL-Plänen und sogar zum „Radfahren“ einer neuen Implementierung verwenden?
Geklebte Protokolle
Schauen wir uns einen kleinen Teil des PostgreSQL-Serverprotokolls an:
2020-09-11 14:49:53.281 MSK [80927:619/4255507] [explain.tensor.ru] 10.76.182.154(59933) pgAdmin III - ???????????????????? ???????????????? LOG: duration: 0.016 ms plan:
Query Text: explain analyze
SELECT
*
FROM
pg_class
WHERE
relname = '
';
Index Scan using pg_class_relname_nsp_index on pg_class (cost=0.29..2.54 rows=1 width=265) (actual time=0.014..0.014 rows=0 loops=1)
Index Cond: (relname = '
'::name)
Buffers: shared hit=2Wir können das durch die Variable log_line_prefix festgelegte Format verwenden, um die Kopfzeile zu identifizieren und zu kürzen , die mit einem Datum beginnt :
SHOW log_line_prefix;
-- "%m [%p:%v] [%d] %r %a "
Es braucht ziemlich viel Regex-Magie
const reTS = "\\d{4}(?:-\\d{2}){2} \\d{2}(?::\\d{2}){2}"
, reTSMS = reTS + "\\.\\d{3}"
, reTZ = "(?:[A-Za-z]{3,5}|GMT[+\\-]\\d{1,2})";
var re = {
// : log_line_prefix
'%a' : "(?:[\\x20-\\x7F]{0,63})"
, '%u' : "(?:[\\x20-\\x7F]{0,63})"
, '%d' : "[\\x20-\\x7F]{0,63}?"
, '%r' : "(?:(?:\\d{1,3}(?:\\.\\d{1,3}){3}|[\\-\\.\\_a-z0-9])\\(\\d{1,5}\\)|\\[local\\]|)"
, '%h' : "(?:(?:\\d{1,3}(?:\\.\\d{1,3}){3}|[\\-\\.\\_a-z0-9])|\\[local\\]|)"
, '%p' : "\\d{1,5}"
, '%t' : reTS + ' ' + reTZ
, '%m' : reTSMS + ' ' + reTZ
, '%i' : "(?:SET|SELECT|DO|INSERT|UPDATE|DELETE|COPY|COMMIT|startup|idle|idle in transaction|streaming [0-9a-f]{1,8}\/[0-9a-f]{1,8}|)(?: waiting)?"
, '%e' : "[0-9a-z]{5}"
, '%c' : "[0-9a-f]{1,8}\\.[0-9a-f]{1,8}"
, '%l' : "\\d+"
, '%s' : "\\d{4}(?:-\\d{2}){2} \\d{2}(?::\\d{2}){2} [A-Z]{3}"
, '%v' : "(?:\\d{1,9}\\/\\d{1,9}|)"
, '%x' : "\\d+"
, '%q' : ""
, '%%' : "%"
// : log_min_messages
, '%!' : "(?:DEBUG[1-5]|INFO|NOTICE|WARNING|ERROR|LOG|FATAL|PANIC)"
// : log_error_verbosity
, '%@' : "(?:DETAIL|HINT|QUERY|CONTEXT|LOCATION|STATEMENT)"
};
re['%#'] = "(?:" + re['%!'] + "|" + re['%@'] + ")";
// log_line_prefix RegExp
let lre = self.settings['log_line_prefix'].replace(/([\[\]\(\)\{\}\|\?\$\\])/g, "\\\$1") + '%#: ';
self.tokens = lre.match(new RegExp('(' + Object.keys(re).join('|') + ')', 'g'));
let matcher = self.tokens.reduce((str, token) => str.replace(token, '(' + re[token] + ')'), lre);
self.matcher = new RegExp('^' + matcher, '');
Aber dann haben wir eine Anfrage zusammen mit einem Plan - und wie kann man verstehen, wo einer endet und ein anderer beginnt? ..
Es scheint, dass der Plan eine Textdarstellung eines Baumes ist , also sollte es eine "Wurzel" geben? Das heißt, die erste Zeile von unten mit der minimalen Einrückung (Auslassen
Trigger ...) - die gewünschte Wurzel und der Beginn des Plans?
Leider nein. In unserem Beispiel ist eine solche Zeichenfolge der "Schwanz"
'::name)aus der in Teile geteilten mehrzeiligen Zeichenfolge. Wie soll ich sein?
Benutze Trie, Luke!
Beachten Sie jedoch, dass der Plan von einem der Knoten ausgehen muss:
Seq Scan, Index Scan, Sort, Aggregate, ...- weder mehr noch weniger, sondern 133 verschiedene Optionen, mit Ausnahme CTE, InitPlan SubPlanderjenigen, die nicht root sein können.
Tatsächlich wissen wir nicht, welcher der Knoten, die wir kennen, am Anfang dieser Zeile steht (und wenn überhaupt), aber wir wollen ihn finden. Dies ist , wo der Präfixbaums uns helfen wird .
Unveränderliche Trie
Aber unser Baum, den wir bauen wollen, hat mehrere Eigenschaften:
- Kompaktheit
Wir haben Dutzende / Hunderte von möglichen Elementen von ziemlich begrenzter Länge, daher kann es keine Situation mit einer großen Anzahl sehr langer, fast identischer Schlüssel geben, die sich nur im letzten Zeichen unterscheiden. Der längste unserer Schlüssel ist wahrscheinlich'Parallel Index Only Scan Backward'. -
. . -
. , . - -
, «» Garbage Collector'.
Die letzte Anforderung ist darauf zurückzuführen, dass die Analyse der Protokolle auf unseren Kollektoren im Streaming-Modus ohne Unterbrechungen durchgeführt wird. Und je weniger wir "wegwerfen" können, desto mehr Ressourcen werden wir für nützliche Aktivitäten verwenden, anstatt nach uns selbst aufzuräumen.
Zwei nützliche Funktionen helfen uns dabei:
String.prototype.charCodeAt(index)Mit dieser Option können Sie den Zeichencode an einer bestimmten Position in der Zeichenfolge ermittelnString.prototype.startsWith(searchString[, position])prüft, ob der Anfang eines Strings [von einer bestimmten Position] mit der Suche übereinstimmt
Eine Karte erstellen
Schauen wir uns ein Beispiel an, wie Sie eine Karte erstellen können, um mit diesen beiden Operationen schnell die Elemente zu finden, die Sie aus dem ursprünglichen Satz benötigen: Hmm ... sie haben das gleiche "In" -Präfix !
Insert
Index Scan
Index Scan Backward
Index Only Scan
Index Only Scan Backward
// Longest Common Prefix
let len, lcp;
for (let key of keys) {
//
if (lcp === undefined) {
len = key.length;
lcp = key.slice(off);
continue;
}
len = Math.min(len, key.length);
// , "" LCP
if (lcp == '' || key.startsWith(lcp, off)) {
continue;
}
// LCP
for (let i = 0; i < lcp.length; i++) {
if (lcp.charCodeAt(i) != key.charCodeAt(off + i)) {
lcp = lcp.slice(0, i);
break;
}
}
}
Und da es dasselbe ist, können wir durch Überprüfen der Symbole in keiner Weise neue Informationen erhalten - was bedeutet, dass wir nur die Symbole überprüfen müssen, die weiter gehen, bis zur Länge des kürzesten Elements . Sie helfen uns dabei, alle Elemente in mehrere Gruppen aufzuteilen: In diesem Fall spielte es keine Rolle, welches Symbol wir für die Aufteilung verwenden (z. B. 3. oder 5.) - die Zusammensetzung der Gruppen bleibt unverändert, sodass genau dieselbe Kombination der Aufteilung in Gruppen wiederholt wird es besteht keine Notwendigkeit zu verarbeiten :
Insert
Index Scan
Index Scan Backward
Index Only Scan
Index Only Scan Backward
//
let grp = new Set();
res.pos = {};
for (let i = off + lcp.length; i < len; i++) {
// [i]-
let chr = keys.reduce((rv, key) => {
if (key.length < i) {
return rv;
}
let ch = key.charCodeAt(i);
rv[ch] = rv[ch] || [];
rv[ch].push(key);
return rv;
}, {});
//
let cmb = Object.values(chr)
.map(seg => seg.join('\t'))
.sort()
.join('\n');
if (grp.has(cmb)) {
continue;
}
else {
grp.add(cmb);
}
res.pos[i] = chr;
}
Optimale Metrik
Es bleibt nur zu verstehen - und wenn die Gruppen beim 3. und 5. Symbol unterschiedlich waren - welchen dieser Äste sollten Sie wählen? Zu diesem Zweck führen wir eine Metrik ein, die uns die Antwort auf diese Frage gibt - die Anzahl der Vergleiche einzelner Zeichen , um jeden der Schlüssel zu finden.
Hier vernachlässigen wir die Tatsache, dass einige der Knoten in den Plänen in der Realität viel häufiger vorkommen als andere, und wir betrachten sie als gleich.
, 3-'s',startsWith, , 6 , ,Insert.
: 1 (.charCodeAt(2)) + 6 (.startsWith('Insert')) = 7 .
'd', 7-, ,'O''S'. —'Index Scan Backward'(+19 )'Index Scan'(+10 ).
,'Index Scan Backward', 19 ,'Index Scan'— 19 + 10 = 29.
: 1 (.charCodeAt(2)) + 1 (.charCodeAt(6)) + 19 + 29 (.startsWith(...)) = 50 .
In unserem Beispiel sieht die optimale Karte daher folgendermaßen aus:
{
'$pos' : 2 // 3-
, '$chr' : Map {
100 => { // 'd'
'$pos' : 6 // 7-
, '$chr' : Map {
79 => [ 'Index Only Scan Backward', 'Index Only Scan' ] // 'O'
, 83 => [ 'Index Scan Backward', 'Index Scan' ] // 'S'
}
}
, 115 => 'Insert' // 's'
}
}
Vzhuh!
Jetzt müssen Sie nur noch alles zusammenführen, eine Suchfunktion und einige Optimierungen hinzufügen - und Sie können Folgendes verwenden:
//
const fill = (obj, off, hash) => {
off = off || 0;
hash = hash || {};
let keys = obj.src;
//
let H = keys.join('\n');
hash[off] = hash[off] || {};
if (hash[off][H]) {
obj.res = hash[off][H];
return;
}
obj.res = {};
hash[off][H] = obj.res;
let res = obj.res;
// -
if (keys.length == 1) {
res.lst = [...keys];
res.cmp = res.lst[0].length;
return;
}
// Longest Common Prefix
let len, lcp;
for (let key of keys) {
//
if (lcp == undefined) {
len = key.length;
lcp = key.slice(off);
continue;
}
len = Math.min(len, key.length);
// , "" LCP
if (lcp == '' || key.startsWith(lcp, off)) {
continue;
}
// LCP
for (let i = 0; i < lcp.length; i++) {
if (lcp.charCodeAt(i) != key.charCodeAt(off + i)) {
lcp = lcp.slice(0, i);
break;
}
}
}
//
if (off + lcp.length == len) {
let cmp = 0;
// -
if (keys.length == 2) {
res.lst = [...keys];
}
// " "
else {
res.src = keys.filter(key => key.length > off + lcp.length);
res.lst = keys.filter(key => key.length <= off + lcp.length);
}
// , ,
res.lst.sort((x, y) => y.length - x.length); // s.length DESC
cmp += res.lst.reduce((rv, key, idx, keys) => rv + (keys.length - idx + 1) * key.length, 0);
// -
if (res.src && res.src.length) {
fill(res, off + lcp.length + 1, hash);
cmp += res.res.cmp;
}
res.cmp = cmp + 1;
return;
}
//
let grp = new Set();
res.pos = {};
for (let i = off + lcp.length; i < len; i++) {
// [i]-
let chr = keys.reduce((rv, key) => {
if (key.length < i) {
return rv;
}
let ch = key.charCodeAt(i);
rv[ch] = rv[ch] || [];
rv[ch].push(key);
return rv;
}, {});
//
let cmb = Object.values(chr)
.map(seg => seg.join('\t'))
.sort()
.join('\n');
if (grp.has(cmb)) {
continue;
}
else {
grp.add(cmb);
}
let fl = true;
let cmp = 0;
for (let [ch, keys] of Object.entries(chr)) {
//
if (keys.length == 1) {
let key = keys[0];
chr[ch] = key;
cmp += key.length;
}
//
else {
fl = false;
chr[ch] = {src : keys};
fill(chr[ch], i + 1, hash);
cmp += chr[ch].res.cmp;
}
}
res.pos[i] = {
chr
, cmp
};
// ""
if (res.cmp === undefined || cmp + 1 < res.cmp) {
res.cmp = cmp + 1;
res.bst = i;
}
// ,
if (fl) {
res.bst = i;
for (let j = off; j < i; j++) {
delete res.pos[j];
}
break;
}
}
};
//
const comp = obj => {
//
delete obj.src;
delete obj.cmp;
if (obj.res) {
let res = obj.res;
if (res.pos !== undefined) {
//
obj.$pos = res.bst;
let $chr = res.pos[res.bst].chr;
Object.entries($chr).forEach(([key, val]) => {
//
comp(val);
// - ""
let keys = Object.keys(val);
if (keys.length == 1 && keys[0] == '$lst') {
$chr[key] = val.$lst;
}
});
// - Map -
obj.$chr = new Map(Object.entries($chr).map(([key, val]) => [Number(key), val]));
}
// ""
if (res.lst !== undefined) {
obj.$lst = res.lst;
delete res.lst;
if (res.res !== undefined) {
comp(res);
Object.assign(obj, res);
}
}
delete obj.res;
}
};
// -
const find = (str, off, map) => {
let curr = map;
do {
//
let $pos = curr.$pos;
if ($pos !== undefined) {
let next = curr.$chr.get(str.charCodeAt(off + $pos));
if (typeof next === 'string') { //
if (str.startsWith(next, off)) {
return next;
}
}
else if (next instanceof Array) { //
for (let key of next) {
if (str.startsWith(key, off)) {
return key;
}
}
}
else if (next !== undefined) { // map,
curr = next;
continue;
}
}
// ,
if (curr.$lst) {
for (let key of curr.$lst) {
if (str.startsWith(key, off)) {
return key;
}
}
}
return;
}
while (true);
};
function ImmutableTrie(keys) {
this.map = {src : keys.sort((x, y) => x < y ? -1 : +1)};
fill(this.map);
comp(this.map);
}
const p = ImmutableTrie.prototype;
p.get = function(line, off) {
return find(line, off || 0, this.map);
};
p.has = function(line, off) {
return this.get(line, off) !== undefined;
};
module.exports = ImmutableTrie;
Wie Sie sehen können, wurde bei der Suche in einem solchen unveränderlichen Trie
Bonus: Jetzt können wir das gewünschte Präfix erhalten, ohne es
.slicein der ursprünglichen Zeile tun zu müssen , auch wenn wir wissen, dass es am Anfang traditionell für den Plan etwas Fremdes hat:
const nodeIT = new ImmutableTrie(...);
nodeIT.get(' -> Parallel Seq Scan on abc', 6); // 'Parallel Seq Scan'Nun, wenn wir bereits genau auf die gleiche Weise entschieden haben, wo der Plan beginnt (aber mit Hilfe der Trie-Attributnamen), definieren wir die Zeilen, die der Anfang des Knotenattributs sind und die Fortsetzung der mehrzeiligen Zeichenfolge sind, und "kleben" sie:
Index Scan using pg_class_relname_nsp_index on pg_class (cost=0.29..2.54 rows=1 width=265) (actual time=0.014..0.014 rows=0 loops=1)
Index Cond: (relname = '\n\n'::name)
Buffers: shared hit=2Nun, in dieser Form ist es viel einfacher, es zu zerlegen.