Et même les implémentations dans le code, y compris JavaScript, il y en a beaucoup pour cela - du «canonical» de John Resig et diverses versions optimisées à une série de modules dans NPM .
Pourquoi avons-nous besoin de l'utiliser pour un service de collecte et d'analyse des plans PostgreSQL , et même de «cycle» d'une nouvelle implémentation? ..
Bûches collées
Jetons un coup d'œil à un petit morceau du journal du serveur PostgreSQL:
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=2Nous pouvons utiliser le format défini par la variable log_line_prefix pour identifier et découper la ligne d'en-tête qui commence par une date :
SHOW log_line_prefix;
-- "%m [%p:%v] [%d] %r %a "
Il faut un peu de magie regex
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, '');
Mais alors nous avons une demande avec un plan - et comment comprendre où l'un se termine et l'autre commence? ..
Il semblerait que le plan soit une représentation textuelle d'un arbre , donc il devrait y avoir une «racine»? Autrement dit, la première ligne à partir du bas avec l'indentation minimale (en omettant,
Trigger ...) - la racine souhaitée et le début du plan?
Malheureusement non. Dans notre exemple, une telle chaîne sera la "queue"
'::name)de la chaîne multiligne divisée en parties. Comment être?
Utilisez Trie, Luke!
Mais notez que le plan doit partir d'un des nœuds:
Seq Scan, Index Scan, Sort, Aggregate, ...- ni plus ni moins, mais 133 options différentes, à l'exclusion de CTE, InitPlan SubPlancelles qui ne peuvent pas être root.
En fait, nous ne savons pas lequel des nœuds que nous connaissons se trouve au début de cette ligne (et s'il y en a pas du tout), mais nous voulons le trouver. C'est là que l' arborescence des préfixes nous aidera .
Immuable Trie
Mais notre arbre, que nous voulons construire, a plusieurs fonctionnalités:
- compacité
Nous avons des dizaines / centaines d'éléments possibles de longueur assez limitée, il ne peut donc pas y avoir de situation d'un grand nombre de très longues touches presque coïncidentes qui ne diffèrent que par le dernier caractère. La plus longue de nos clés est probablement'Parallel Index Only Scan Backward'. -
. . -
. , . - -
, «» Garbage Collector'.
La dernière exigence est due au fait que l'analyse des logs sur nos collecteurs se fait sans interruption, en mode streaming. Et moins nous pouvons «jeter», plus nous dirigerons de ressources vers des activités utiles au lieu de nettoyer après nous-mêmes.
Deux fonctions utiles nous aideront à cela:
String.prototype.charCodeAt(index)vous permet de trouver le code de caractère à une position spécifique dans la chaîneString.prototype.startsWith(searchString[, position])vérifie si le début d'une chaîne [à partir d'une position spécifique] correspond à la recherche
Construire une carte
Regardons un exemple de la façon dont vous pouvez construire une carte afin qu'en utilisant ces deux opérations, vous puissiez trouver rapidement les éléments dont vous avez besoin dans l'ensemble d'origine: Hmm ... oui, ils ont le même préfixe In!
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;
}
}
}
Et comme c'est la même chose, en vérifiant ses symboles, nous ne pourrons en aucun cas obtenir de nouvelles informations - ce qui signifie que nous n'avons besoin que de vérifier les symboles qui vont plus loin, jusqu'à la longueur de l'élément le plus court . Ils nous aideront à diviser tous les éléments en plusieurs groupes: dans ce cas, peu importe le symbole que nous prenons pour le fractionnement (3e ou 5e, par exemple) - la composition des groupes sera toujours la même, donc la même combinaison exacte de division en groupes est répétée il n'est pas nécessaire de traiter :
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;
}
Métrique optimale
Il ne reste plus qu'à comprendre - et si les groupes étaient différents sur les 3e et 5e symboles - laquelle de ces branches d'arbre choisir? Pour ce faire, nous introduisons une métrique qui nous donnera la réponse à cette question - le nombre de comparaisons de caractère unique pour trouver chacune des clés.
Ici, nous négligeons le fait que certains des nœuds se retrouvent en réalité dans les plans beaucoup plus souvent que d'autres, et nous les considérons égaux.
, 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 .
En conséquence, pour notre exemple, la carte optimale ressemblera à ceci:
{
'$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!
Il ne reste plus qu'à tout rassembler, ajouter une fonction de recherche, quelques optimisations - et vous pouvez utiliser:
//
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;
Comme vous pouvez le voir, lors de la recherche dans un tel Immuable Trie,
Bonus: maintenant on peut obtenir le préfixe désiré sans avoir à le faire
.slicesur la ligne d'origine, même si on sait qu'au tout début il a, traditionnellement pour le plan, quelque chose d'extraordinaire:
const nodeIT = new ImmutableTrie(...);
nodeIT.get(' -> Parallel Seq Scan on abc', 6); // 'Parallel Seq Scan'Eh bien, lorsque nous avons déjà décidé où le plan commence, exactement de la même manière (mais à l'aide des noms d'attribut Trie), nous définissons les lignes qui sont le début de l'attribut node, et qui sont la suite de la chaîne multiligne et les "collons":
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=2Eh bien, sous cette forme, il est beaucoup plus facile de le démonter.