また、JavaScriptを含むコードの実装でさえ、John Resigによる「正規」やさまざまな最適化されたバージョンから、NPMの一連のモジュールまで、その多くがあります。PostgreSQLプランを収集および分析する
ためのサービス、さらにはいくつかの新しい実装を「循環」させるために、なぜそれを使用する必要があったのでしょうか。
接着ログ
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=2log_line_prefix 変数で設定された形式を使用して、日付で始まるヘッダー行を識別してトリミングできます。
SHOW log_line_prefix;
-- "%m [%p:%v] [%d] %r %a "
かなりの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, '');
しかし、計画とともにリクエストがあります。そして、どこで終わり、どこから始まるかを理解する方法は？..
計画は木のテキスト表現であるように見えるので、1つの「ルート」が必要ですか？つまり、最小のインデント（省略、
Trigger ...）を使用した下からの最初の行-目的のルートと計画の開始？
残念だけど違う。この例では、このような文字列は
'::name)、分割された複数行の文字列からの「テール」になります。どうなる？
トライ、ルークを使って！
ただし、計画はノードの1つから開始する必要があることに注意してください
Seq Scan, Index Scan, Sort, Aggregate, ...。-多かれ少なかれでCTE, InitPlan SubPlanはなく、ルートにできないものを除く133の異なるオプション。
実際、この行の先頭にあるノードがどれであるかはわかりませんが（ある場合は）、見つけたいと思います。これは、プレフィックスツリーが役立つ場所です。
不変のトライ
しかし、構築したいツリーにはいくつかの機能があります。
- コンパクト
さ非常に限られた長さの数十/数百の可能な要素があるので、最後の文字だけが異なる非常に長いほぼ同一のキーが多数ある状況はあり得ません。私たちの鍵の中で最も長いものはおそらく'Parallel Index Only Scan Backward'です。 -
. . -
. , . - -
, «» Garbage Collector'.
最後の要件は、コレクターのログの分析がストリーミングモードで中断することなく実行されるという事実によるものです。そして、私たちが「散らかす」ことができることが少なければ少ないほど、私たちが自分自身の後で片付ける代わりに、より多くのリソースを有用な活動に向けることになります。
2つの便利な機能がこれに役立ちます。
String.prototype.charCodeAt(index)文字列の特定の位置にある文字コードを見つけることができますString.prototype.startsWith(searchString[, position])[特定の位置からの]文字列の先頭が検索と一致するかどうかを確認します
マップの作成
次の2つの操作を使用して、元のセットから必要な要素をすばやく見つけるためにマップを作成する方法の例を見てみましょう。 うーん...同じ「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;
}
}
}
また、同じであるため、そのシンボルをチェックすることによって、新しい情報を取得することはできません。つまり、最短の要素の長さまで、さらに進んだシンボルをチェックするだけで済みます。これらは、すべての要素をいくつかのグループに分割するのに役立ちます。 この場合、分割に使用する記号は関係ありません（たとえば、3番目または5番目）。グループの構成は同じであるため、グループへの分割のまったく同じ組み合わせが繰り返されます。処理する必要はありません：
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;
}
最適なメトリック
理解することだけが残っています-そして、グループが3番目と5番目のシンボルで異なっていた場合-これらの木の枝のどれを選ぶべきですか？これを行うために、この質問に対する答えを提供するメトリックを導入します。これは、各キーを見つけるための1文字の比較の数です。
ここでは、一部のノードが実際には他のノードよりもはるかに頻繁に計画に含まれているという事実を無視し、それらは同等であると見なします。
, 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 .
その結果、この例では、最適なマップは次のようになります。
{
'$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！
残っているのは、すべてをまとめ、検索機能を追加し、いくつかの最適化を行うことだけです。次を使用できます。
//
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;
ご覧のとおり、このような不変のトライを検索しても、
ボーナス：これ
.sliceで、元の行でそれを行うことなく、目的のプレフィックスを取得できます。これは、最初に、従来の計画では無関係なものがあることがわかっていてもです。
const nodeIT = new ImmutableTrie(...);
nodeIT.get(' -> Parallel Seq Scan on abc', 6); // 'Parallel Seq Scan'さて、計画の開始場所をまったく同じ方法で（ただし、Trie属性名を使用して）すでに決定したら、ノード属性の始まりであり、複数行の文字列の続きである行を定義し、それらを「接着」します。
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さて、この形式では、それを分解する方がはるかに簡単です。