Immutable Trie: найди то, не знаю что, но быстро, и не мусори

    Про префиксное дерево (Trie) написано немало, в том числе и на Хабре. Вот пример, как оно может выглядеть:


    И даже реализаций в коде, в том числе на JavaScript, для него существует немало — от «каноничной» by 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) от распавшейся на части multiline string. Как быть?

    Use Trie, Luke!


    Но заметим, что план обязан начинаться с одного из узлов: Seq Scan, Index Scan, Sort, Aggregate, ... — ни много, ни мало, а 133 разных варианта, исключая CTE, InitPlan и SubPlan, которые не могут быть корневыми.

    По сути, мы не знаем, какой именно из известных нам узлов находится в начале данной строки (и находится ли вообще), но хотим его найти. Как раз в этом нам и поможет префиксное дерево.

    Immutable Trie


    Но у нашего дерева, которое мы хотим построить, есть несколько особенностей:

    • компактность
      Возможных элементов у нас десятки/сотни вполне ограниченной длины, поэтому не может возникнуть ситуации большого количества очень длинных почти совпадающих ключей, отличающихся только в последнем символе. Самый длинный из наших ключей, наверное — 'Parallel Index Only Scan Backward'.
    • иммутабельность
      То есть элементы добавляются только при инициализации. В дальнейшем процессе его существования они уже не добавляются и не удаляются.
    • пропускная способность
      Мы хотим тратить минимум операций на проверку совпадения каждого элемента. Иначе можно было бы просто последовательно сравнивать каждый элемент с началом строки, пока не найдется нужный.
    • отсутствие сайд-эффектов
      Операции поиска не должны создавать новых объектов в памяти, которые потом пришлось бы «зачищать» Garbage Collector'у.

    Последнее требование обусловлено тем фактом, что анализ логов на наших коллекторах ведется без перерывов, в потоковом режиме. И чем меньше мы сможем «намусорить», тем больше ресурсов направим на полезную активность вместо уборки за собой.

    В этом нам помогут две полезные функции:


    Строим карту


    Давайте посмотрим на примере, как можно построить карту, чтобы с помощью этих двух операций быстро находить нужные элементы из исходного набора:

    Insert
    Index Scan
    Index Scan Backward
    Index Only Scan
    Index Only Scan Backward


    Хм… да у них же есть одинаковый префикс «In»!

    // определение минимальной длины ключа и 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;
        }
      }
    }
    

    А раз он одинаковый, то проверяя его символы, мы никак не сможем получить новой информации — значит, проверять надо только символы, идущие дальше, вплоть до длины самого короткого элемента. Они помогут нам разбить все элементы на несколько групп:

    Insert
    Index Scan
    Index Scan Backward
    Index Only Scan
    Index Only Scan Backward


    В данном случае оказалось неважно, какой символ мы возьмем для разбиения (3-й или 5-й, например) — состав групп окажется все равно одинаковым, поэтому точно такую же комбинацию разбиения на группы повторно обрабатывать незачем:

    // перебираем варианты выбора номера тестируемого символа
    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'
      }
    }
    

    Вжух!


    Теперь осталось только свести все воедино, добавить функцию поиска, немного оптимизаций — и можно использовать:

    // заполнение карты поиска
    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;
    

    Как можно заметить, при поиске в таком Immutable Trie ни одно животное не пострадало не создается никаких новых объектов в памяти, за которыми потом хотел бы прийти GC.

    Из бонусов: теперь мы можем получать искомый префикс без необходимости делать .slice на исходной строке, даже если мы знаем, что в самом начале у нее, традиционно для плана, что-то постороннее:

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

    Ну а когда мы уже определились, где план начинается, ровно таким же способом (но уже с помощью Trie названий атрибутов) мы определяем строки, которые являются началом атрибута узла, а какие — продолжение multiline string и «склеиваем» их:

    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

    Ну а в таком виде его разбирать — уже намного проще.
    Тензор
    Разработчик системы СБИС

    Комментарии 10

      0

      Как разминка для мозгов — нормально.


      Но в реальности такое никто делать не будет, потому что код сложный, логика работы неочевидная, правки потребуют построения нового дерева, да и эффективность сомнительна. Количество одинарных сравнений символа — странная метрика, так как проход по дереву, индексация требуют гораздо больше ресурсов, особенно в случае использования JS. Сравнение двух подстрок длиной в 50 символов, возможно, будет даже быстрее, чем извлечение из них 3 символов и сравнение только этих символов.


      Так что я бы сделал более наивную реализацию: тупо разбивал строку по пробелам на неделимые слова и строил дерево, сравнивая только слова.

        0
        такое никто делать не будет, потому что код сложный, логика работы неочевидная, правки потребуют построения нового дерева, да и эффективность сомнительна
        Я просто покажу разницу в работе GC относительно предыдущей «наивной» реализации со .slice и рекурсией — она стоит и усложнения кода:



        Или вот CPU-нагрузка — уменьшилась в среднем примерно на 10% (14.37 -> 13.02), существенно меньше стало «биение»:




        тупо разбивал строку по пробелам на неделимые слова и строил дерево, сравнивая только слова.
        Разбиение на слова порождает новый объект массива, а этого как раз и не хочется при поиске.
          0

          Я из этого графика не понимаю проблемы. По оси Y Mns — это мега-нано-секунды, или миллисекунды, если переводить на человеческий язык. Но за какой период собирается эта статистика?

      +1

      Только непонятно почему структура данных в итоге названа trie, если в ней от trie ничего не осталось.


      Кстати, если производительность настолько важна — почему бы не нагенерить из такого дерева код заранее?


      function find(str, off) {
          switch (str.charCodeAt(off+2)) {
              case 100:
                  switch (str.charCodeAt(off+6)) {
                      case 79:
                          if (str.startsWith("Index Only Scan Backward", off))
                              return "Index Only Scan Backward";
                          if (str.startsWith("Index Only Scan", off))
                              return "Index Only Scan";
                      break;
                      case 83:
                          if (str.startsWith("Index Scan Backward", off))
                              return "Index Scan";
                          if (str.startsWith("Index Scan", off))
                              return "Index Scan";
                      break;
                  }
              break;
              case 115:
                  if (str.startsWith("Insert", off))
                      return "Insert";
              break;
          }
      }
        0
        почему структура данных в итоге названа trie
        Потому что полностью подходит под определение: «Префиксное дерево — структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами.»

        почему бы не нагенерить из такого дерева код заранее?
        Когда-то очень давно, еще в школе, мы тоже писали на Pascal программу-генератор QuickSort'а IF'ами, но это из серии материалов для другого хаба. :)
        Впрочем, не исключаю, что и до этого дойдем когда-нибудь.
          0

          Вот только trie — это не абстрактная структура данных, а конкретная. Не любое дерево, подходящее под это определение, является trie.

            0
            Структурно, это как раз сжатое префиксное дерево. А уж как именно я его сжимаю, определение не описывает.
              0

              Ну нет. В сжатом префиксном дереве в каждом узле хранится некоторая подстрока, по котором можно построить текущий префикс если идти из корня. А у вас строки только в листах хранятся.


              Кстати, формат именно сжатого бора для задач подобных вашей как раз нежелателен, поскольку ограничивает возможности оптимизации. Например, для следующего гипотетического случая — "aaa, aab, aac, ddd, eee" сжатый бор обязан выделить общий префикс "aa", в то время как оптимальным решением будет начинать проверку сразу с третьего символа не выделяя никаких префиксов.

                0
                Собственно, именно так и отработает алгоритм — сначала выделит длину общего префикса 'aa', начнет проверку с 3-го символа, а потом перепроверит, является ли найденное префиксом.

      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

      Самое читаемое