Статьи

Планы выполнения SQL в Javascript

Апрель 28, 2018
Различные компании, фреймворки и библиотеки имеют встроенную функциональность, напоминающую реляционные базы данных, для решения различных задач: более тесная языковая интеграция (R, pandas, linq), нишевые приложения для обработки данных (solr, картографическое программное обеспечение), масштабирующие машины или память (hadoop, datomic, memcached) и т. д. Основная сила SQL заключается в том, что он позволяет вам описывать то, что вы хотите, позволяя компьютеру выбирать, как его получить.

Общий процесс , используемый Oracle выглядит следующим образом :
Query -> Анализировать Tree -> Создать набор планов -> Подсчет очков каждый план -> Выберите план -> Исполнение -> Выход

Альтернативный путь заключается в создании плана выполнения с использованием эвристики — более простой подход и очевидный выбор для многих приложений.

Примерный план выполнения может быть довольно сложным:

План выполнения строк
——– ————————————————-
12 СОРТИРОВКА АГРЕГАТА
2 СОРТИРОВАТЬ ГРУППУ ПО
76563 ВСТРОЕННЫХ
ПЕТЛЕЙ 76575 ВСТРОЕННЫХ ПЕТЛЕЙ
19 ТАБЛИЦЫ ДОСТУПА ПОЛНЫМ
CN_PAYRUNS_ALL 76570 ТАБЛИЦА ДОСТУПА К ИНДЕКСУ ROWID
7_65__POST INDEX RANGE SCAN (идентификатор объекта 178321)
76563 Доступ к таблице по индексу
ROWID CN_PAYMENT_WORKSHEETS_ALL 11432983 INDEX RANGE SCAN (идентификатор объекта 186024)

Это эквивалентно некоторому оригинальному запросу, и потенциально существует много других эквивалентных планов. Мне бы хотелось, чтобы API / библиотека (например, фреймы данных R / pandas) структурировали запросы таким образом — тогда можно было бы построить реализацию SQL, которая создала эти планы, или создать новое поколение языков, эквивалентных SQL.

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

schema = {
  tables: {
    people: [
      {
       first_name: 'gary',
       last_name: 'sieling',
       company: 1
      },
      {
       first_name: 'ella',
       last_name: 'sieling',
       company: 2
      }
    ],
   companies: [
     {
       id: 1,
       company_name: 'acme corp'
     },
     {
       id: 2,
       company_name: 'bubble'
     }
   ]
  },
  indexes: {
   company_pk: {
     data: {
      a: {
         rowid: 2
      },
      b: {
         rowid: 1
      }
     }
   }
  }
}

В идеале план выполнения может выглядеть примерно так: каждая функция возвращает Promise (или аналогичный), чтобы результаты могли передаваться обратно:

sort(
  nested_loop_join(
    nested_loop_join(
     s({
       select: ['rowid', 'first_name', 'last_name', 'company'],
       from: schema.table1,
       where: function(row) { return true }
     }),
     s({
       select: ['rowid'],
       from: schema.indexes.company_pk
     }),
     ['rowid', 'rowid'],
     ['a', 'b']
   ),
   s({
     select: true,
     from: schema.table1
   })
 )
)

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

function s(x) {
  var i = 0;
  var where = function() { return true; }
 
  if (x.where) where = x.where;
 
  return function() {
    var next = x.from[i++]
    if (!next) {
      return next;
    }
 
    if (where(next)) {
      if (x.select) {
        var res = {};
        $.each(x.select, function(i, col) {
          res[col] = next[col];
        });
        return res;
      } else {
        return next;
      }
    }
  }
}
 
results = s({from:schema.tables.people})
results()
Object {first_name: "gary", last_name: "sieling", company: 1}
results()
Object {first_name: "ella", last_name: "sieling", company: 2}
results()
undefined
 
 
results = s({from:schema.tables.people, select: ['first_name']})
results()
Object {first_name: "gary"}
results()
Object {first_name: "ella"}
results()
 
results = s({from:schema.tables.people,
  select: ['first_name'], where: function(row) { return row.first_name = 'gary' } })
results()
Object {first_name: "gary"}
results()

Теперь, чтобы сделать что-то более интересное, давайте попробуем реализовать соединение. Это объединение вложенных циклов в приведенном выше плане Oracle — всего два цикла for с предложением where в объединении.

function nested_loop_join(a, b, keys, select) {
  output = []
 
  second = [];
  while(row_b = b()) {
    second[second.length] = row_b;
  }
 
  while(row_a = a()) {
    $.each(second, function(i, row_b) {
      if (row_a[keys[0]] === row_b[keys[1]]) {
        var new_row = {};
 
        $.each(select, function(k, col) {
          // cheat here for simplicity - should handle aliasing
          new_row[col] =
            (row_a[col] ? row_a[col] : row_b[col])
        })
 
        output[output.length] = new_row;
      }
    })
  }
 
  return s({from: output})
}
 
joined = nested_loop_join(
  s({from:schema.tables.companies}),
  s({from:schema.tables.people}),
  ["id", "company"],
   ["last_name", "company_name"])
joined()
Object {last_name: "sieling", company_name: "acme corp"}
joined()
Object {last_name: "sieling", company_name: "bubble"}

До этого момента я избегал реализации индексов из-за сложности — давайте сделаем соединение другого типа, декартово соединение. Это берет все строки первой и второй таблиц независимо от их соответствия, затем применяет фильтр в конце:

function cartesian_join(a, b, keys, select) {
  output = []
 
  second = [];
  while(row_b = b()) {
    second[second.length] = row_b;
  }
 
  var cols = select;
  if (cols) {
    $.each(keys, function(i, c) {
      if ($.inArray(c, select) === -1) {
        cols[cols.length] = c;
      }
    });
  }
 
  while(row_a = a()) {
    $.each(second, function(i, row_b) {
      var new_row = {};
 
      $.each(cols, function(k, col) {
        // cheat here for simplicity - should handle aliasing
        new_row[col] =
          (row_a[col] ? row_a[col] : row_b[col])
      });
 
      output[output.length] = new_row;
    })
  }
 
  return s({from: output, where: function(row) {
    return row[keys[0]] === row[keys[1]];
  }});
}
 
joined()
Object {last_name: "sieling", company_name: "acme corp", id: 1, company: 1}
joined()
undefined
joined()
undefined
joined()
Object {last_name: "sieling", company_name: "bubble", id: 2, company: 2}

Теперь давайте напишем что-нибудь более в стиле SQL — мы не хотим указывать реализацию.

from(
  schema.tables.company,
  schema.tables.person
  ["company", "id"]
  ["last_name", "company"]
)

Эта функция from может взять две таблицы и использовать эвристику, как старый оптимизатор на основе строк, для фильтрации результатов:

function from(table1, table2, keys, cols) {
  if (table1.length <= 5 && table2.length <= 5) {
    return cartesian_join(s({from:table1}), s({from:table2}), keys, cols)
  }
  else {
    return nested_loop_join(s({from:table1}), s({from:table2}), keys, cols)
  }
}
 
joined = nested_loop_join(
  s({from:schema.tables.companies}),
  s({from:schema.tables.people}),
  ["id", "company"],
  ["last_name", "company_name"])
joined()
Object {last_name: "sieling", company_name: "acme corp"}
joined()
Object {last_name: "sieling", company_name: "bubble"}

Чтобы на самом деле построить оптимизатор на основе затрат, вам понадобится возможность отслеживать такие вещи, как размеры выборок таблиц / индексов, гистограммы и т. Д., Но вы можете представить себе написание отдельных реализаций алгоритмов в большой библиотеке.

42
Share: