
E até mesmo implementações no código, incluindo JavaScript, há muitos para isso - desde o "canônico" de John Resig e várias versões otimizadas a uma série de módulos no NPM .
Por que precisamos usá-lo para um serviço de coleta e análise de planos PostgreSQL , e até mesmo “ciclos” de algumas novas implementações? ..
Toras coladas
Vamos dar uma olhada em um pequeno pedaço do log do 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=2
Podemos usar o formato definido pela variável log_line_prefix para identificar e cortar a linha do cabeçalho que começa com uma data :
SHOW log_line_prefix;
-- "%m [%p:%v] [%d] %r %a "
Requer um pouco de magia 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, '');
Mas então temos um pedido junto com um plano - e como entender onde um termina e outro começa? ...
Parece que o plano é uma representação textual de uma árvore , então deveria haver uma "raiz"? Ou seja, a primeira linha da parte inferior com o recuo mínimo (omitindo,
Trigger ...
) - a raiz desejada e o início do plano?
Infelizmente não. Em nosso exemplo, essa string será a "cauda"
'::name)
da string de várias linhas dividida em partes. Como ser?
Use Trie, Luke!
Mas note que o plano deve começar a partir de um dos nós:
Seq Scan, Index Scan, Sort, Aggregate, ...
- nem mais nem menos, mas 133 opções diferentes, excluindo CTE, InitPlan SubPlan
aquelas que não podem ser root.
Na verdade, não sabemos qual dos nós que conhecemos está no início desta linha (e se está), mas queremos encontrá-lo. É aqui que a árvore de prefixos nos ajudará .
Trie imutável
Mas nossa árvore, que queremos construir, tem vários recursos:
- compactação
Temos dezenas / centenas de elementos possíveis de comprimento bastante limitado, então não pode haver uma situação de um grande número de chaves muito longas quase idênticas que diferem apenas no último caractere. A mais longa de nossas chaves é provavelmente'Parallel Index Only Scan Backward'
. -
. . -
. , . - -
, «» Garbage Collector'.
O último requisito se deve ao fato de que a análise dos logs em nossos coletores é realizada sem interrupções, em modo streaming. E quanto menos podemos "jogar lixo", mais recursos direcionaremos para atividades úteis em vez de limparmos nós mesmos.
Duas funções úteis nos ajudarão com isso:
String.prototype.charCodeAt(index)
permite que você descubra o código do caractere em uma posição específica na stringString.prototype.startsWith(searchString[, position])
verifica se o início de uma string [de uma posição específica] corresponde à pesquisa
Construindo um mapa
Vejamos um exemplo de como você pode construir um mapa para encontrar rapidamente os elementos que você precisa do conjunto original usando estas duas operações: Hmm ... eles têm o mesmo prefixo “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;
}
}
}
E como é o mesmo, verificando seus símbolos, não poderemos obter nenhuma informação nova de forma alguma - o que significa que só precisamos verificar os símbolos que vão além, até o comprimento do elemento mais curto . Eles nos ajudarão a dividir todos os elementos em vários grupos: Neste caso, não importa qual símbolo usaremos para a divisão (3º ou 5º, por exemplo) - a composição dos grupos ainda será a mesma, então a mesma combinação exata de divisão em grupos é repetida não há necessidade de processar :
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 ideal
Resta apenas entender - e se os grupos fossem diferentes no 3º e 5º símbolos - qual desses galhos de árvore você deveria escolher? Para fazer isso, apresentamos uma métrica que nos dará a resposta a essa pergunta - o número de comparações de um único caractere para encontrar cada uma das chaves.
Aqui, negligenciamos o fato de que alguns dos nós são encontrados na realidade nos planos com muito mais frequência do que outros, e os consideramos equivalentes.
, 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 nosso exemplo, o mapa ideal será semelhante a este:
{
'$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!
Agora, tudo o que resta é juntar tudo, adicionar uma função de pesquisa, algumas otimizações - e você pode 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 você pode ver, ao pesquisar em tal Trie Imutável,
Bônus: agora podemos obter o prefixo desejado sem ter que fazê-lo
.slice
na linha original, mesmo sabendo que no início ele tem, tradicionalmente para o plano, algo estranho:
const nodeIT = new ImmutableTrie(...);
nodeIT.get(' -> Parallel Seq Scan on abc', 6); // 'Parallel Seq Scan'
Bem, quando já decidimos onde o plano começa, exatamente da mesma maneira (mas com a ajuda de nomes de atributos de Trie), definimos as linhas que são o início do atributo do nó, e que são a continuação da string multilinha e as "colamos":
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=2
Bem, desta forma, é muito mais fácil desmontá-lo.