Clever Geek Handbook

不变的特里：找到东西，我不知道，但是很快，不要乱扔垃圾

关于前缀树（Trie）的文章很多，包括在Habré上。这是一个外观的示例：





甚至包括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=2


我们可以使用log_line_prefix变量设置的格式来标识和修剪以日期开头的标题行： 



SHOW log_line_prefix;
-- "%m [%p:%v] [%d] %r %a "


这需要很多正则表达式魔术 
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, '');


但是，接着我们有了一个请求以及一个计划-以及如何理解一个目标从哪里结束而另一个起点呢？..



看来该计划是一棵树的文字表示，所以应该有一个“根”吗？也就是说，从底部开始的第一行具有最小的缩进（省略Trigger ...），是所需的根和计划的开始？



很不幸的是，不行。在我们的示例中，这样的字符串将成为'::name)分割成多行字符串的“尾巴” 。怎样成为？



使用特里，卢克！



但是请注意，该计划必须从以下节点之一开始：Seq Scan, Index Scan, Sort, Aggregate, ...-既不多也不少，但有133种不同的选择，其中包括CTE, InitPlan SubPlan不能为根的选择。



实际上，我们不知道我们知道哪个节点在该行的开头（如果有的话），但是我们想找到它。这是前缀树将帮助我们的地方。



不变的特里



但是我们要构建的树具有几个功能：



  • 紧凑性

    我们有几十个/几百个可能的元素，它们的长度非常有限，因此不会出现大量非常长的几乎相同的键，而这些键仅在最后一个字符上有所不同。我们最长的钥匙大概是'Parallel Index Only Scan Backward'。


  • . .


  • . , .
  • -

    , «» Garbage Collector'.


最后一个要求是由于以下事实：在收集器上以流方式进行日志分析时不会中断。而且，我们越少“乱扔垃圾”，我们就会将更多的资源用于有用的活动，而不是自己清理。



两个有用的功能将帮助我们：





制作地图



让我们看一个示例，该示例说明如何构建地图以使用以下两个操作从原始集中快速找到所需的元素： 嗯……它们具有相同的“ 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个符号上的组不同-您应该选择这些树枝中的哪一个？为此，我们引入了一个度量标准，该度量标准将为我们提供该问题的答案-查找每个键的单个字符比较的次数。



在这里，我们忽略了一个事实，即某些节点在计划中实际存在的机会比其他节点要多，而我们认为它们是相等的。



, 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'
  }
}


zhu！



现在剩下的就是将所有内容组合在一起，添加搜索功能，进行一些优化-您可以使用： 



//   
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;


如您所见，在这种不可变的Trie中进行搜索时，没有动物受到伤害，内存中也没有创建新的对象，GC便希望为其创建新对象。



奖励：现在.slice，即使我们从一开始就知道它具有一贯的传统意义上的计划，也可以不必在原始行上获得所需的前缀： 



const nodeIT = new ImmutableTrie(...);
nodeIT.get('  ->  Parallel Seq Scan on abc', 6); // 'Parallel Seq Scan'


好了，当我们已经以完全相同的方式（但在Trie属性名称的帮助下）确定了计划的起点时，我们定义了几行，这些行是node属性的开始，并且是多行字符串的延续，并将它们“粘”在一起： 



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


好吧，以这种形式，拆卸起来要容易得多。


More articles:


All Articles