Фаза толкования
На фазе толкования система пытается найти компактную модель, в которой фиксируется отображение (tuple, partition), полученное на фазе разделения. Для выполнения этой задачи мы используем деревья решений (классификаторы в машинном обучении) поскольку они производят доступные для понимания основанные на правилах результаты, которые можно сразу применять для разделения по предикатам диапазонов. Классификатор на основе дерева решений на входе принимает набор пар (value, label), а в качестве результата производит дерево предикатов над значениями, ведущими к листовым вершинам с заданными метками. Для непомеченного значения метку можно обнаружить путем спуска по дереву и применения предикатов в каждом узле до тех пор, пока не будет достигнут помеченный лист.
В Schism значения – это кортежи базы данных, а метки – разделы, назначенные кортежам алгоритмом разделения графов. Реплицируемые кортежи помечаются специальным идентификатором репликации, обозначающим набор разделов, в котором должен храниться данный кортеж (например, набор разделов {1, 3, 4} можно представить меткой R1).
В случае удачи классификатор обнаруживает простой набор правил, в котором в компактной форме фиксируется суть разделения, полученного алогоритмом разделения графов. Для примера с рис. 2 и 3 классификатор на основе дерева решений выводит следующие правила:
(id = 1 ) → partitions = {0, 1}
(2 ≤ id < 4) → partition = 0
(id ≥ 4) → partition = 1
Не всегда возможно получить толкование разделения, и не всякое толкование полезно. Толкование оказывается полезным только при выполнении следующих условий:
-
оно основывается на атрибутах, часто используемых в запросах (например, в нашем примере, атрибут id используется в разделе WHERE половины запросов), – это требуется для того, чтобы можно было направлять транзакции в один узел и избегать дорогостоящей широковещательной рассылки;
-
оно не слишком снижает качество разделения за счет неправильной классифкации кортежей;
-
оно работает для дополнительных запросов (при чрезмерно близкой подгонке может получиться толкование, работающее на обучающем наборе, но использующее атрибуты, не представленные в запросах приложения).
Для достижения этих целей мы:
-
ограничиваем дерево решений таким образом, чтобы оно работало на атрибутах, часто используемых в запросах;
-
измеряем стоимость как число распределенных транзакций и не допускаем толкований, ухудшающих графовое решение и
-
активно используем отсечение и перекрестную проверку, чтобы избежать чремерно близкой подгонки.
В разд. 5.2 реализация процесса толкования описывается более подробно.
