E incluso implementaciones en el código, incluido JavaScript, hay muchas para ello, desde el "canónico" de John Resig y varias versiones optimizadas hasta una serie de módulos en NPM .
¿Por qué necesitamos usarlo para un servicio para recopilar y analizar planes de PostgreSQL , e incluso "ciclar" alguna implementación nueva? ...
Troncos pegados
Echemos un vistazo a una pequeña parte del registro del servidor 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=2Podemos usar el formato establecido por la variable log_line_prefix para identificar y recortar la línea de encabezado que comienza con una fecha :
SHOW log_line_prefix;
-- "%m [%p:%v] [%d] %r %a "
Se necesita un poco de magia de expresiones regulares
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, '');
Pero luego tenemos una solicitud junto con un plan - ¿y cómo entender dónde termina uno y comienza otro? ...
Parecería que el plan es una representación textual de un árbol , ¿entonces debería haber una "raíz"? Es decir, la primera línea desde abajo con la sangría mínima (omitiendo
Trigger ...): ¿la raíz deseada y el comienzo del plan?
Lamentablemente no. En nuestro ejemplo, dicha cadena será la "cola"
'::name)de la cadena dividida en partes de varias líneas. ¿Cómo ser?
¡Usa a Trie, Luke!
Pero tenga en cuenta que el plan debe partir de uno de los nodos:
Seq Scan, Index Scan, Sort, Aggregate, ...- ni más ni menos, pero 133 opciones diferentes, excluyendo CTE, InitPlan SubPlanaquellas que no pueden ser root.
De hecho, no sabemos cuál de los nodos sabemos que está al principio de esta línea (y si lo está), pero queremos encontrarlo. Aquí es donde nos ayudará el árbol de prefijos .
Trie inmutable
Pero nuestro árbol, que queremos construir, tiene varias características:
- compacidad
Tenemos decenas / cientos de elementos posibles de longitud bastante limitada, por lo que no puede darse la situación de un gran número de claves muy largas casi idénticas que difieran sólo en el último carácter. Probablemente la más larga de nuestras llaves sea'Parallel Index Only Scan Backward'. -
. . -
. , . - -
, «» Garbage Collector'.
El último requisito se debe a que el análisis de los logs de nuestros colectores se realiza sin interrupciones, en modo streaming. Y cuanto menos podamos "tirar", más recursos dirigiremos a una actividad útil en lugar de limpiar lo que ensuciamos.
Dos funciones útiles nos ayudarán con esto:
String.prototype.charCodeAt(index)le permite encontrar el código de carácter en una posición específica en la cadenaString.prototype.startsWith(searchString[, position])comprueba si el comienzo de una cadena [desde una posición específica] coincide con la búsqueda
Construyendo un mapa
Veamos un ejemplo de cómo puedes construir un mapa para encontrar rápidamente los elementos que necesitas del conjunto original usando estas dos operaciones: Hmm ... ¡tienen el mismo prefijo "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;
}
}
}
Y como es el mismo, entonces al verificar sus símbolos, no podremos obtener nueva información de ninguna manera, lo que significa que solo necesitamos verificar los símbolos yendo más allá, hasta la longitud del elemento más corto . Nos ayudarán a dividir todos los elementos en varios grupos: en este caso, no importa qué símbolo tomemos para dividir (el tercero o el quinto, por ejemplo); la composición de los grupos seguirá siendo la misma, por lo que se repite exactamente la misma combinación de división en grupos no es necesario procesar :
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étrica óptima
Solo queda entender, y si los grupos fueran diferentes en el tercer y quinto símbolo, ¿cuál de estas ramas de árbol debería elegir? Para hacer esto, presentamos una métrica que nos dará la respuesta a esta pregunta: el número de comparaciones de un solo carácter para encontrar cada una de las claves.
Aquí descuidamos el hecho de que algunos de los nodos se encuentran en realidad en los planos con mucha más frecuencia que otros, y los consideramos iguales.
, 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 .
Como resultado, para nuestro ejemplo, el mapa óptimo se verá así:
{
'$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!
Ahora todo lo que queda es reunir todo, agregar una función de búsqueda, algunas optimizaciones, y puede usar:
//
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;
Como puede ver, al buscar en un Trie tan inmutable,
De las bonificaciones: ahora podemos obtener el prefijo requerido sin tener que hacerlo
.sliceen la línea original, incluso si sabemos que al principio tiene, tradicionalmente para el plan, algo extraño:
const nodeIT = new ImmutableTrie(...);
nodeIT.get(' -> Parallel Seq Scan on abc', 6); // 'Parallel Seq Scan'Pues bien, cuando ya hemos decidido dónde empieza el plan, exactamente de la misma forma (pero con la ayuda de los nombres de los atributos de Trie), definimos las líneas que son el inicio del atributo de nodo, y que son la continuación de la cadena multilínea y las "pegamos":
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=2Bueno, de esta forma, es mucho más fácil desmontarlo.