Uploaded image for project: 'Calcite'
  1. Calcite
  2. CALCITE-1290

When converting to CNF, fail if the expression size exceeds a threshold

    Details

    • Type: Bug
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 1.9.0
    • Component/s: None
    • Labels:
      None

      Description

      When converting to conjunctive normal form (CNF), fail if the expression exceeds a threshold. CNF can explode exponentially in the size of the input expression, but rarely does so in practice. Add a maxNodeCount parameter to RexUtil.toCnf and throw or return null if it is exceeded.

      I don't believe it is possible to predict the size of the CNF from the input expression (especially if there are duplicate terms) but I might be wrong.

        Issue Links

          Activity

          Hide
          julianhyde Julian Hyde added a comment -

          The bound could be in terms of number of leaves (counting a leaf twice if it occurs in two expressions) or in terms of nodes (leaves plus interior nodes). I don't mind which... either would be effective, and one might be easier to compute efficiently as the CNF is being built.

          Show
          julianhyde Julian Hyde added a comment - The bound could be in terms of number of leaves (counting a leaf twice if it occurs in two expressions) or in terms of nodes (leaves plus interior nodes). I don't mind which... either would be effective, and one might be easier to compute efficiently as the CNF is being built.
          Hide
          jcamachorodriguez Jesus Camacho Rodriguez added a comment -

          I created a PR in https://github.com/apache/calcite/pull/273 , including tests for the new function. Julian Hyde, could you take a look? Thanks

          Show
          jcamachorodriguez Jesus Camacho Rodriguez added a comment - I created a PR in https://github.com/apache/calcite/pull/273 , including tests for the new function. Julian Hyde , could you take a look? Thanks
          Hide
          julianhyde Julian Hyde added a comment -

          Looks good. I changed a logic a bit so that any negative number means no threshold (previously, Integer.MAX_VALUE meant no threshold). Will commit when my tests have passed.

          Show
          julianhyde Julian Hyde added a comment - Looks good. I changed a logic a bit so that any negative number means no threshold (previously, Integer.MAX_VALUE meant no threshold). Will commit when my tests have passed.
          Hide
          jcamachorodriguez Jesus Camacho Rodriguez added a comment -

          That makes sense, thanks!

          Show
          jcamachorodriguez Jesus Camacho Rodriguez added a comment - That makes sense, thanks!
          Show
          julianhyde Julian Hyde added a comment - Fixed in http://git-wip-us.apache.org/repos/asf/calcite/commit/77315c06 .
          Hide
          jcamachorodriguez Jesus Camacho Rodriguez added a comment -

          Resolved in release 1.9.0 (2016-09-22)

          Show
          jcamachorodriguez Jesus Camacho Rodriguez added a comment - Resolved in release 1.9.0 (2016-09-22)

            People

            • Assignee:
              jcamachorodriguez Jesus Camacho Rodriguez
              Reporter:
              julianhyde Julian Hyde
            • Votes:
              0 Vote for this issue
              Watchers:
              3 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development