Про ZDD и выполнение запросов.
Как в columnstore работает запрос типа SELECT. Вычисляются столбцы, которые надо выбрать, и выбираются. Строится цепочка - выбрать вот этот столбец, пересечь вот с этим, такие-то номера строк подать на выход для чтения результата.
Сами столбцы лежат в экстентах - файлах, что содержат до 64Мбайт данных. То есть, для 8-байтных целых туда может поместиться до 8 миллионов элементов.
Экстенты, само собой, побиты на блоки, но это не очень интересно.
У экстентов есть информация о диапазоне значений внутри. Поэтому мы можем, допустим, не читать целые экстенты, если внутри них заведомо нет нужных значений - WHERE col = 10, а экстент столбца содержит числа от 100 до 1000.
То, как columnstore работает на выполнение, тоже не очень интересно. Там используется hash join, но как - я не совсем понимаю, пусть у меня и changeset в 293 файла.
Однако можно предложить и другую модель - вложенные циклы. Мы идём по табличкам запроса, считая проход по ним циклом, каждая табличка создаёт вложенный цикл: SELECT * FROM a,b,c... создаст три вложенных цикла foreach a_tuple in a.elements { foreach b_tuple in b.elements { foreach c_tuple in c.elements { ... }}}. По идее, мы можем выбрать наиболее оптимальный проход в целом, как это делает SQLite.
Однако, SQLite не имеет информации, имеющейся у columnstore: SQLite не имеет диапазонов значений у диапазонов строк. Нет у неё эстентов. А у MCS есть.
Поэтому мы можем подразбить наши циклы: для каждой таблицы идём по экстентам для диапазонов строк, а потом идём по строкам внутри экстентов. Вместо трёх циклов выше будет шесть. Циклы по строкам мы можем переместить вниз, после циклов по экстентам.
И вот здесь начинается интересное.
Мы можем идти по экстентам таблицы в любом порядке, включая порядок по "узости" диапазонов значений. Если мы так и поступим, то наш план будет приближением плана, полученного SQLite - выберем самый узкий столбец и вперёд. Но мы можем пойти и дальше - мы можем менять порядок таблиц в процессе выполнения. Пусть в самом начале выгодно выбрать экстент a_c_1 столбца C таблицы A. По всем остальным экстентам остальных таблиц мы идём, как обычно. Но после того, как мы обработали экстент a_c_1 и остальные экстенты, статистика может измениться и наиболее выгодным может быть выбор экстента c_z_100 столбца Z таблицы C.
В пределе, мы можем перебирать не полный набор экстентов таблиц, только часть, и пересматривать статистику. И вот тут на помощь приходят ZDD.
ZDD, Zero-suppressed Decision Diagram, это способ хранения множества подмножеств. Если у нас есть некоторое конечное множество элементов, то ZDD позволяет экономно представить некоторый набор подмножеств этого множества. Узлы в ZDD содержат элемент, ссылку на узел с подмножествами, к которым надо добавить элемент, и ссылку на узел с подмножествами, в котором элемент отсутствует. Ссылки могут ссылаться на специальные узлы 1 и 0, означающие "множество из одного элемента - пустого множества" и "пустое множество". Семантика узла Z(e,x,y) - объединение {{e}Ut|t<-x} и y. Узлы, что содержат ссылку на 0 в позиции "ссылка на узел подмножества, к которому добавлять элемент", тождественно равны узлу, в котором элемент отсутствует: Z(_,0,x) === x.
Приведу пример представления декартова произведения множеств {{a},{b}} и {{x},{y},{z}}:
Z1=Z(a, 1, 0) - содержит {{a}}
Z2=Z(b, 1, Z1) - содержит {{b}.{a}}
Z3=Z(x, Z2, 0) - содержит {{x,b},{x,a}}
Z4=Z(y, Z2, Z3) - содержит {{y,b},{y,a},{x,b},{x,a}}
Z5=Z(z, Z2, Z4) - содержит {{z,b},{z,a},{y,b},{y,a},{x,b},{x,a}}
Корнем является узел Z5.
Количество узлов ZDD декартова произведения нескольких множеств будет равно сумме мощностей этих множеств. Вообще, ZDD очень экономна, даже ROBDD обгоняет с большим запасом.
Так вот, проведя вычисления над какими-то экстентами, неважно, над какими, главное, чтобы мы проходили по всем таблицам, мы можем вычесть (в смысле вычитания множеств) пройденное нами множество множеств экстентов из нашей ZDD полного декартова произведения. После чего перевычислить статистику и повторить действия.
Например, если узким был a, а выгодно это для x и y, мы можем вычесть {{x,a},{y,a}} из нашего полного декартова произведения, и получить {{z,a},{z,b},{x,b},{y,b}}.
Теперь осталось это как-то наживить и показать работоспособность. ;)
PS
https://justinjaffray.com/a-gentle-ish-introduction-to-worst-case-optimal-joins/ - поиск треугольников в графе может порождать O(n2) промежуточных данных для O(n1,5) результатов. Любой план SQLite лучше не справится. Цель всего эксерсиса выше - приблизиться к "оптимальному в худшем случае" плану выполнения.
Сами столбцы лежат в экстентах - файлах, что содержат до 64Мбайт данных. То есть, для 8-байтных целых туда может поместиться до 8 миллионов элементов.
Экстенты, само собой, побиты на блоки, но это не очень интересно.
У экстентов есть информация о диапазоне значений внутри. Поэтому мы можем, допустим, не читать целые экстенты, если внутри них заведомо нет нужных значений - WHERE col = 10, а экстент столбца содержит числа от 100 до 1000.
То, как columnstore работает на выполнение, тоже не очень интересно. Там используется hash join, но как - я не совсем понимаю, пусть у меня и changeset в 293 файла.
Однако можно предложить и другую модель - вложенные циклы. Мы идём по табличкам запроса, считая проход по ним циклом, каждая табличка создаёт вложенный цикл: SELECT * FROM a,b,c... создаст три вложенных цикла foreach a_tuple in a.elements { foreach b_tuple in b.elements { foreach c_tuple in c.elements { ... }}}. По идее, мы можем выбрать наиболее оптимальный проход в целом, как это делает SQLite.
Однако, SQLite не имеет информации, имеющейся у columnstore: SQLite не имеет диапазонов значений у диапазонов строк. Нет у неё эстентов. А у MCS есть.
Поэтому мы можем подразбить наши циклы: для каждой таблицы идём по экстентам для диапазонов строк, а потом идём по строкам внутри экстентов. Вместо трёх циклов выше будет шесть. Циклы по строкам мы можем переместить вниз, после циклов по экстентам.
И вот здесь начинается интересное.
Мы можем идти по экстентам таблицы в любом порядке, включая порядок по "узости" диапазонов значений. Если мы так и поступим, то наш план будет приближением плана, полученного SQLite - выберем самый узкий столбец и вперёд. Но мы можем пойти и дальше - мы можем менять порядок таблиц в процессе выполнения. Пусть в самом начале выгодно выбрать экстент a_c_1 столбца C таблицы A. По всем остальным экстентам остальных таблиц мы идём, как обычно. Но после того, как мы обработали экстент a_c_1 и остальные экстенты, статистика может измениться и наиболее выгодным может быть выбор экстента c_z_100 столбца Z таблицы C.
В пределе, мы можем перебирать не полный набор экстентов таблиц, только часть, и пересматривать статистику. И вот тут на помощь приходят ZDD.
ZDD, Zero-suppressed Decision Diagram, это способ хранения множества подмножеств. Если у нас есть некоторое конечное множество элементов, то ZDD позволяет экономно представить некоторый набор подмножеств этого множества. Узлы в ZDD содержат элемент, ссылку на узел с подмножествами, к которым надо добавить элемент, и ссылку на узел с подмножествами, в котором элемент отсутствует. Ссылки могут ссылаться на специальные узлы 1 и 0, означающие "множество из одного элемента - пустого множества" и "пустое множество". Семантика узла Z(e,x,y) - объединение {{e}Ut|t<-x} и y. Узлы, что содержат ссылку на 0 в позиции "ссылка на узел подмножества, к которому добавлять элемент", тождественно равны узлу, в котором элемент отсутствует: Z(_,0,x) === x.
Приведу пример представления декартова произведения множеств {{a},{b}} и {{x},{y},{z}}:
Z1=Z(a, 1, 0) - содержит {{a}}
Z2=Z(b, 1, Z1) - содержит {{b}.{a}}
Z3=Z(x, Z2, 0) - содержит {{x,b},{x,a}}
Z4=Z(y, Z2, Z3) - содержит {{y,b},{y,a},{x,b},{x,a}}
Z5=Z(z, Z2, Z4) - содержит {{z,b},{z,a},{y,b},{y,a},{x,b},{x,a}}
Корнем является узел Z5.
Количество узлов ZDD декартова произведения нескольких множеств будет равно сумме мощностей этих множеств. Вообще, ZDD очень экономна, даже ROBDD обгоняет с большим запасом.
Так вот, проведя вычисления над какими-то экстентами, неважно, над какими, главное, чтобы мы проходили по всем таблицам, мы можем вычесть (в смысле вычитания множеств) пройденное нами множество множеств экстентов из нашей ZDD полного декартова произведения. После чего перевычислить статистику и повторить действия.
Например, если узким был a, а выгодно это для x и y, мы можем вычесть {{x,a},{y,a}} из нашего полного декартова произведения, и получить {{z,a},{z,b},{x,b},{y,b}}.
Теперь осталось это как-то наживить и показать работоспособность. ;)
PS
https://justinjaffray.com/a-gentle-ish-introduction-to-worst-case-optimal-joins/ - поиск треугольников в графе может порождать O(n2) промежуточных данных для O(n1,5) результатов. Любой план SQLite лучше не справится. Цель всего эксерсиса выше - приблизиться к "оптимальному в худшем случае" плану выполнения.