logoalt Hacker News

AlotOfReading • today at 6:04 PM • 0 replies • view on HN

I noticed some prior art when I wrote a similar library in C++ earlier this year, but unfortunately it's pretty much all deeply theoretical. The magic search term is "monadic unions of conjunctive queries", which is the class of queries this kind of system can express.

I'm still surprised there aren't more implementations out there, because it's a very useful class in application programming. For example, gameplay tags in unreal engine are queries in this class [0], and Intel ships a library using them for binary message parsing. It can also be done almost completely in SIMD, which is the route my shitty library takes. If you add recursion on top, you get queries that can express regular languages / monadic datalog.

My library quickly bottlenecked on memory bandwidth though. It doesn't seem like you're ordering joins by selectivity or a bitmap index to avoid reading unnecessary memory, so is this a direction you plan to explore more in the future?

[0] https://dev.epicgames.com/documentation/unreal-engine/using-...