Сравнение с MSSQL таково:
— запрос №3 (только count) MSSQL выполняет около 5 минут (с холодного старта и полчаса потянет)
— сплошное чтение маски (эквивалентное запросу №5) занимает около минуты
— запрос №3 через битовый индекс выполняется ~300 мсек
Вообще, под эту категорию попадают не только boolean, но и числовые маски и символьные поля (Ex: IsProcessed='y').
Да речь идёт о собственном движке с индексами, но в данном случае это не важно.
Алгоритм общечеловеческий и его реализация была опубликована как расширение к PGSQL (отсюда и слон на заставке).
Ну, строго говоря, не пара битов, а в 8 раз.
Иногда за счет выравнивания лишний разряд может потянуть за собой и 4 и 8 байт.
А, например для синхронизации большого к-ва объектов, выгодно работать с общей битовой маской.
На всё в IT можно смотреть как на банальную последовательность нулей и единиц.
Вот конкретно эта маска с другой стороны является индексом (что само по себе и не ново).
Интерес представляет скорее алгоритм поиска, который оказался применим к такой маске и умеет эффективно пропускать бесполезные данные и не пропускать полезные.
«Силовой» алгоритм имеет большое число степеней свободы и его еще надо суметь аккуратно "отжечь". Из-за локальных минимумов делать это надо многократно.
И даже найденное расположение пытаются улучшить перестановками ячеек с целью уменьшить число пересечений, насколько я понял.
В предложенной же конструкции одна степень свободы и глобальный минимум находится перебором всех вариантов. При этом «силовая» функция может быть той же самой. Это не гарантирует оптимальности решения, но это точно будет быстрее.
Добавил вырожденный случай, когда стандартные ячейки просто располагаются
в узлах кривой Гильберта, т.е. в прямоугольной решетке, естественным образом формируя ряды.
>> Может быть так уже и сделано? :)
>> Я не разработчик САПР, а их пользователь. Выше я описывал то,
>> как выглядит процесс с точки зрения разработчика.
>> Как работает сам САПР, какие в него там алгоритмы
>> заложены неизвестно (коммерческая тайна).
Есть такое мнение (andy_p):
«Вообще алгоритмов размещения достаточно много. Насколько мне известно, обычно делают так — размещают грубо ячейки по силовому алгоритму, а затем с помощью какого- либо другого алгоритма убирают получившиеся пересечения. Насчет заметающих кривых — не встречал такого, но, наверное, тоже может иметь место.
Силовой алгоритм — это просто размещение, при котором потенциальная энергия минимальна, если считать, что связь между парами ячеек является пружиной или чем-то типа того с жесткостью, зависящей от количества соединений (ряды при этом не учитываются). А в какой ряд ячейка встанет определяется близостью к этому ряду.»
Положение, которое вы описали, сложилось за десятки лет совместной эволюции технологии и САПР. И конечно, здесь всё явно и неявно пронизано этими рядами ячеек.
Просто отбросить их равносильно прохождению всего пути заново, что может быть и неплохо при определенных обстоятельствах.
Можно ли как-то встроить предложенный подход в существующую технологию?
А что если… :)
Давайте отбросим вертикальные отрезки кривой Гильберта, не будем их заполнять ячейками. Горизонтальные участки сдвинем, чтобы убрать промежутки (это нетривиальное дело).
Но заполнять их станем, как если бы они по-прежнему были на кривой Гильберта ( с учетом tap-ов, если требуется).
В результате сохранятся все прелести существующей технологии и основные преимущества предложенного подхода. В частности скорость.
У вас почему-то сложилось впечатление, что плэйсмент по кривой Гильберта требует бОльших вычислительных затрат, чем нынешняя технология.
Считаю что это не так. Впрочем, опыт критерий истины.
Если вы считаете, что для питания проще использовать решетку, нежели дерево,
значит так и есть.
Большие библиотечные элементы можно делать квадратными а не линейными.
В этом случае они на общих основаниях встроятся в кривую Гильберта (вместо узда 2Х2, 4Х4, ...), дискретность только появится. И/или разрывы, если таких элементов несколько.
Про питание: сейчас, насколько я понял, есть два варианта — условно, прогрессивное и чересстрочное
В данном случае придётся делать что-то вроде H-tree аналогично подводу синхроимпульса.
Повернуть стандартную ячейку или обернуть её через ось, насколько я понимаю, не проблема. Если это будет полезно, появятся и «угловые» ячейки.
Сложный триггер тянет на функциональный блок, который, впрочем можно «с'инлайнить», разбив на элементарные ячейки. Либо на следующем уровне иерархии можно использовать функциональные блоки в качестве элементов для размещения по высокоуровневой кривой Гильберта.
Здесь, похоже, есть где разгуляться пытливым умам.
Я не ставил целью написать гайд по многомерным индексам.
Потому как особого выбора то и нет.
Если у вам MS SQL, то это GRID или OLAP куб.
Почти во всех остальных базах есть R-tree.
Для PG SQL я написал когда-то расширение с Z-order/Hilbert curve.
А в данной статье обосновал (как мне кажется) почему ничего кроме Z-order/Hilbert curve и ждать не стоит. Причем это же не просто пространственный индекс, который не боится постоянных update-ов. При необходимости, это и куб OLAP, для которого не надо готовить специальную аналитическую базу, он работает на-лету.
делает эту «битовую маску» не такой уж и банальной
— запрос №3 (только count) MSSQL выполняет около 5 минут (с холодного старта и полчаса потянет)
— сплошное чтение маски (эквивалентное запросу №5) занимает около минуты
— запрос №3 через битовый индекс выполняется ~300 мсек
Да речь идёт о собственном движке с индексами, но в данном случае это не важно.
Алгоритм общечеловеческий и его реализация была опубликована как расширение к PGSQL (отсюда и слон на заставке).
Иногда за счет выравнивания лишний разряд может потянуть за собой и 4 и 8 байт.
А, например для синхронизации большого к-ва объектов, выгодно работать с общей битовой маской.
Вот конкретно эта маска с другой стороны является индексом (что само по себе и не ново).
Интерес представляет скорее алгоритм поиска, который оказался применим к такой маске и умеет эффективно пропускать бесполезные данные и не пропускать полезные.
архитектура позволяет сделать оба варианта
И даже найденное расположение пытаются улучшить перестановками ячеек с целью уменьшить число пересечений, насколько я понял.
В предложенной же конструкции одна степень свободы и глобальный минимум находится перебором всех вариантов. При этом «силовая» функция может быть той же самой. Это не гарантирует оптимальности решения, но это точно будет быстрее.
в узлах кривой Гильберта, т.е. в прямоугольной решетке, естественным образом формируя ряды.
>> Может быть так уже и сделано? :)
>> Я не разработчик САПР, а их пользователь. Выше я описывал то,
>> как выглядит процесс с точки зрения разработчика.
>> Как работает сам САПР, какие в него там алгоритмы
>> заложены неизвестно (коммерческая тайна).
Есть такое мнение (andy_p):
«Вообще алгоритмов размещения достаточно много. Насколько мне известно, обычно делают так — размещают грубо ячейки по силовому алгоритму, а затем с помощью какого- либо другого алгоритма убирают получившиеся пересечения. Насчет заметающих кривых — не встречал такого, но, наверное, тоже может иметь место.
Силовой алгоритм — это просто размещение, при котором потенциальная энергия минимальна, если считать, что связь между парами ячеек является пружиной или чем-то типа того с жесткостью, зависящей от количества соединений (ряды при этом не учитываются). А в какой ряд ячейка встанет определяется близостью к этому ряду.»
Положение, которое вы описали, сложилось за десятки лет совместной эволюции технологии и САПР. И конечно, здесь всё явно и неявно пронизано этими рядами ячеек.
Просто отбросить их равносильно прохождению всего пути заново, что может быть и неплохо при определенных обстоятельствах.
Можно ли как-то встроить предложенный подход в существующую технологию?
А что если… :)
Давайте отбросим вертикальные отрезки кривой Гильберта, не будем их заполнять ячейками. Горизонтальные участки сдвинем, чтобы убрать промежутки (это нетривиальное дело).
Но заполнять их станем, как если бы они по-прежнему были на кривой Гильберта ( с учетом tap-ов, если требуется).
В результате сохранятся все прелести существующей технологии и основные преимущества предложенного подхода. В частности скорость.
У вас почему-то сложилось впечатление, что плэйсмент по кривой Гильберта требует бОльших вычислительных затрат, чем нынешняя технология.
Считаю что это не так. Впрочем, опыт критерий истины.
значит так и есть.
Большие библиотечные элементы можно делать квадратными а не линейными.
В этом случае они на общих основаниях встроятся в кривую Гильберта (вместо узда 2Х2, 4Х4, ...), дискретность только появится. И/или разрывы, если таких элементов несколько.
Про питание: сейчас, насколько я понял, есть два варианта — условно, прогрессивное и чересстрочное
В данном случае придётся делать что-то вроде H-tree аналогично подводу синхроимпульса.
Повернуть стандартную ячейку или обернуть её через ось, насколько я понимаю, не проблема. Если это будет полезно, появятся и «угловые» ячейки.
Сложный триггер тянет на функциональный блок, который, впрочем можно «с'инлайнить», разбив на элементарные ячейки. Либо на следующем уровне иерархии можно использовать функциональные блоки в качестве элементов для размещения по высокоуровневой кривой Гильберта.
Здесь, похоже, есть где разгуляться пытливым умам.
отсюда :)
Потому как особого выбора то и нет.
Если у вам MS SQL, то это GRID или OLAP куб.
Почти во всех остальных базах есть R-tree.
Для PG SQL я написал когда-то расширение с Z-order/Hilbert curve.
А в данной статье обосновал (как мне кажется) почему ничего кроме Z-order/Hilbert curve и ждать не стоит. Причем это же не просто пространственный индекс, который не боится постоянных update-ов. При необходимости, это и куб OLAP, для которого не надо готовить специальную аналитическую базу, он работает на-лету.
Да, вы правы.