Таки добрался до результатов
https://github.com/thesz/wco-bdd
В общем, промежуточные данные получаются размером O(количество записей), размер конечных данных в BDD, вроде бы, пропорционален количеству конечных данных, что будут обработаны и фильтр пропускает в полтора раза больше данных, чем строго необходимо.
Последнее, наверное, можно как-то улучшить.
Эта штука применима и к строкам, которые весьма тяжело хранить сжато (как это обычно делают WCO алгоритмы).
Засим считаю тему worst-case optimal joins на некоторое время закрытой.
В общем, промежуточные данные получаются размером O(количество записей), размер конечных данных в BDD, вроде бы, пропорционален количеству конечных данных, что будут обработаны и фильтр пропускает в полтора раза больше данных, чем строго необходимо.
Последнее, наверное, можно как-то улучшить.
Эта штука применима и к строкам, которые весьма тяжело хранить сжато (как это обычно делают WCO алгоритмы).
Засим считаю тему worst-case optimal joins на некоторое время закрытой.