Реализация толкования
Для реализации фазы толкования, описанной в подразделах 4.3 и 4.4, мы использовали свободно доступную библиотеку машинного обучения Weka . Процесс толкования состоит из следующих шагов:
-
Создание обучающей выборки (training set): Schism извлекает из трассы рабочей нагрузки информацию о запросах и затрагиваемых ими кортежах – для сокращения времени работы используется взятие образцов (sampling) без ухудшения качества результата. Кортежи помечаются метками разделов, произведенных алгоритмом разделения графа. Как описывалось в подразделе 4.3, реплицируемые кортежи помечаются метками виртуальных разделов, соответствующими наборам целевых разделов. Таким образом образуется обучающая выборка, используемая классификатором на основе дерева решений.
-
Выбор атрибутов: Система разбирает операторы SQL, присутствующие в рабочей нагрузке, и для каждого атрибута фиксирует частоту его вхождений в разделы WHERE. Редко используемые кортежи отбрасываются, поскольку они не годятся для марштрутизации запросов. Например, для таблицы TPC-C stock мы получаем два часто используемых атрибута (s_i_id, s_w_id), представляющие идентификаторы вида товара и склада соответственно. Выбранные атрибуты подаются на вход основанного на учете корреляции компонента Weka отбора признаков (feature selection), который выбирает набор атрибутов, коррелирующих с метками разделов. Для TPC-C на этом шаге отвергается атрибут s_i_id, и для последующей классификации оставляется единственный атрибут s_w_id.
Более сложен тот сценарий, в котором доступ к кортежам одной таблицы часто производится на основе соединения с некоторой другой таблицей. В этом случае наша система подготавливает входные данные для классификатора в виде результата соединения двух таблиц. В результирующем разделении будет требоваться совместное расположение соединенных кортежей в одном и том же разделе, и в состав набора производимых предикатов войдут предикаты соединения, а также предикаты диапазонов значений другой таблицы. Результирующее разделение на основе предикатов будет поддерживать только запросы, выполняющие это соединение.
Другие запросы придется отправлять во все разделы. Хотя подобные запросы не очень распространены (их нет ни в одном из приложений нашего тестового набора), такая ситуация поддерживается.
Построение классификатора: Мы обучаем классификатор на основе дерева решений с использованием J48 – реализации на языке Java классификатора C4.5 . Атрибутами классификации являются метки разделов, которые мы хотим узнать на основе атрибутов, отобранных на предыдущем шаге. На выходе классификатора получается набор предикатов, аппроксимирующих разделение на уровне кортежей, которое было произведено алгоритмом разделения графов. Чрезмерно близкой подгонки удается избежать за счет перекрестной проверки и управляемого применения эвристики сокращения дерева решений для устранения правил с малой поддержкой.
Например, для базы данных TPC-C с двумя складами, разбитой на два раздела, мы получили для таблицы stock следующие правила:
s_w_id ≤ 1: partition: 1 (pred. error: 1.49%)
s_w_id > 1: partition: 2 (pred. error: 0.86%)
Для таблицы item классификатор произвел правило:
<empty>: partition: 0 (pred. error: 24.8%)
Это показывает, что все кортежи этой таблицы реплицируются. Высокое значение ошибки предсказания в этом примере появилось из-за взятия образцов: к некоторым кортежам таблицы item обращается всего несколько транзакций, в результате чего потребность в репликации оказалась необоснованной. Однако это не влияет на качество решения.
Общий результат для TPC-C состоит в разделении базы данных по складам и в репликации всей таблицы item. Такую же стратегию предлагали эксперты . Как отмечается в разд. 6, аналогичное разделение находится для TPC-C с большим числом складов и разделов. Хотя для определения разделов в случае TPC-C не требуются несколько атрибутов, в случае надобности классификатор может производить правила соответствующего вида.
