Dan bahkan implementasi dalam kode, termasuk JavaScript, ada banyak untuk itu - dari "kanonik" oleh John Resig dan berbagai versi yang dioptimalkan hingga serangkaian modul di NPM .
Mengapa kami perlu menggunakannya untuk layanan untuk mengumpulkan dan menganalisis paket PostgreSQL , dan bahkan "bersepeda" beberapa implementasi baru? ..
Log terpaku
Mari kita lihat bagian kecil dari log server 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=2Kita dapat menggunakan format yang ditetapkan oleh variabel log_line_prefix untuk mengidentifikasi dan memangkas baris header yang dimulai dengan tanggal :
SHOW log_line_prefix;
-- "%m [%p:%v] [%d] %r %a "
Dibutuhkan sedikit sihir 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, '');
Tetapi kemudian kita memiliki permintaan bersama dengan sebuah rencana - dan bagaimana memahami di mana satu berakhir dan yang lain dimulai? ..
Tampaknya rencana tersebut adalah representasi tekstual dari sebuah pohon , jadi harus ada satu "akar"? Artinya, baris pertama dari bawah dengan lekukan minimum (menghilangkan,
Trigger ...) - akar yang diinginkan dan awal rencana?
Sayangnya tidak ada. Dalam contoh kita, string seperti itu akan menjadi "ekor"
'::name)dari string multiline dibagi menjadi beberapa bagian. Bagaimana menjadi?
Gunakan Trie, Luke!
Tetapi perhatikan bahwa rencana harus dimulai dari salah satu node:
Seq Scan, Index Scan, Sort, Aggregate, ...- tidak lebih atau kurang, tetapi 133 opsi berbeda, tidak termasuk CTE, InitPlan SubPlanyang tidak bisa menjadi root.
Faktanya, kita tidak tahu node mana yang kita tahu berada di awal baris ini (dan jika memang ada), tapi kita ingin menemukannya. Di sinilah pohon awalan akan membantu kita .
Trie Abadi
Tetapi pohon kami, yang ingin kami bangun, memiliki beberapa fitur:
- kekompakan
Kami memiliki lusinan / ratusan kemungkinan elemen dengan panjang yang cukup terbatas, jadi tidak mungkin ada situasi dengan sejumlah besar kunci yang sangat panjang dan hampir bersamaan yang hanya berbeda pada karakter terakhir. Kunci kami yang terpanjang mungkin'Parallel Index Only Scan Backward'. -
. . -
. , . - -
, «» Garbage Collector'.
Persyaratan terakhir adalah karena fakta bahwa analisis log pada kolektor kami dilakukan tanpa gangguan, dalam mode streaming. Dan semakin sedikit kita dapat "membuang sampah sembarangan", semakin banyak sumber daya yang akan kita arahkan ke aktivitas yang bermanfaat daripada membersihkannya sendiri.
Dua fungsi yang berguna akan membantu kita dalam hal ini:
String.prototype.charCodeAt(index)memungkinkan Anda untuk mengetahui kode karakter pada posisi tertentu dalam stringString.prototype.startsWith(searchString[, position])memeriksa apakah awal string [dari posisi tertentu] cocok dengan pencarian
Membangun peta
Mari kita lihat contoh bagaimana Anda bisa membangun peta untuk dengan cepat menemukan elemen yang Anda butuhkan dari set asli menggunakan dua operasi ini: Hmm ... mereka memiliki awalan "Dalam" yang sama !
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;
}
}
}
Dan karena sama, maka dengan mencentang simbolnya, kita tidak akan bisa mendapatkan informasi baru dengan cara apa pun - yang artinya kita hanya perlu memeriksa simbol yang melangkah lebih jauh, hingga panjang elemen terpendek . Mereka akan membantu kami membagi semua elemen menjadi beberapa grup: Dalam kasus ini, tidak masalah simbol mana yang kami ambil untuk pemisahan (misalnya ke-3 atau ke-5) - komposisi grup akan tetap sama, jadi kombinasi yang sama persis untuk memisahkan grup diulang tidak perlu memproses :
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;
}
Metrik optimal
Tetap hanya untuk memahami - dan jika kelompok berbeda pada simbol ke-3 dan ke-5 - cabang pohon mana yang harus Anda pilih? Untuk melakukan ini, kami memperkenalkan metrik yang akan memberi kami jawaban untuk pertanyaan ini - jumlah perbandingan karakter tunggal untuk menemukan masing-masing kunci.
Di sini kami mengabaikan fakta bahwa beberapa node ditemukan dalam kenyataan lebih sering daripada yang lain, dan kami menganggapnya sama.
, 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 .
Hasilnya, untuk contoh kita, peta yang optimal akan terlihat seperti ini:
{
'$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!
Sekarang yang tersisa hanyalah menyatukan semuanya, menambahkan fungsi pencarian, beberapa pengoptimalan - dan Anda dapat menggunakan:
//
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;
Seperti yang Anda lihat, saat mencari di Trie Abadi,
Bonus: sekarang kita bisa mendapatkan awalan yang diinginkan tanpa harus melakukannya
.slicedi baris asli, bahkan jika kita tahu bahwa pada awalnya ada, secara tradisional untuk rencana, sesuatu yang asing:
const nodeIT = new ImmutableTrie(...);
nodeIT.get(' -> Parallel Seq Scan on abc', 6); // 'Parallel Seq Scan'Nah, ketika kita telah memutuskan di mana rencana dimulai, dengan cara yang persis sama (tetapi dengan bantuan nama atribut Trie), kita mendefinisikan garis yang merupakan awal dari atribut node, dan yang merupakan kelanjutan dari string multiline dan "merekatkan" mereka:
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=2Nah, dalam bentuk ini, jauh lebih mudah membongkarnya.