1. 20

  2. 3

    Anything using Leapfrog Triejoin gets my upvote: it seems like a great advance not being utilized. Does anyone know of a production deployment of Leapfrog Triejoin?

    1. 6

      It is not Leapfrog Triejoin algorithm itself and not deployed yet, but you may be interested nevertheless. Rust’s first borrow checker was an AST-based one. Now it has progressed to have a non-lexical lifetimes (NLL) borrow checker, which just recently has become the default. The third incarnation, Polonius, is formalized as a set of logical rules. Its implementation will utilize Datafrog, a specialized Datalog engine written in Rust.

      Frank McSherry is the author of Datafrog. He wrote a blog about it. I quote:

      There is a neat algorithm called “leapfrog triejoin”, the intellectual property of LogicBlox, Inc. The algorithm we are going to develop, “treefrog leapjoin”, may seem similar, but it is a purely superficial connection. They are both connected to the study of worst-case optimal joins, and I think TFLJ is something of a dual to LFTJ.

      So there you have it. Once finished, an algorithm closely related to Leapfrog Triejoin will be in every Rust compiler.

      1. 3

        “it seems like a great advance not being utilized”

        “ the intellectual property of LogicBlox, Inc.”

        If true, then that probably explains it.

        1. 4

          Indeed. Looking a bit more, it is claimed by patent US9177026. Rather unfortunate, on the other hand if any software patent is legitimate this one probably is. It is innovative and they did invent it.

          1. 2

            Sounds right. I’ll give them props but stay away at same time.

            1. 3

              There was prior academic art for WCOJ in https://arxiv.org/pdf/1203.1952.pdf (published in PODS about 6 months before the patent). The patent is quite specific and there are several alternate algorithms in the same family, including Frank’s treefrog leapjoin. Overall, it’s annoying but the field is not lost.

              Ironically, Logicblox was sold to Infor who now holds the patent. The original inventor and much of the core team left to form relational.ai, where they’ve also had to develop an alternate algorithm to avoid their own patent and now seem less keen on patents in general.

              1. 1

                they’ve also had to develop an alternate algorithm to avoid their own patent

                Damn. That’s gotta feel great…

      2. 2

        This is awesome! Is it using any exciting PL theory?

        1. 1

          Ooh, ooh, ooh! And they’re writing it in Julia! I can’t wait to get my hands on this.