Skip to content

How beta range index works

Jump to bottom
Toshiya Kobayashi edited this page Dec 23, 2020 · 2 revisions

As of drools 7.47.0.Final, beta range index works only for ExistsNode and NotNode.

IndexingTest.testRangeIndex()

rule R1
when
   $s : String()
   exists Cheese( type > $s )
then
end

ksession.insert("cheddar");
ksession.insert("gorgonzola");
ksession.insert("stilton");
ksession.insert(new Cheese("gorgonzola", 10));

Rule Build:

  1. PatternBuilder.buildConstraintForPattern() picks [$s] as declr.
  2. MVELConstraint [type > $s] is created. indexingDeclaration is [$s]
  3. ExistsNode is created.
    • SingleBetaConstraints.initIndexes()
      • IndexUtil.canHaveRangeIndex() returns true
      • SingleBetaConstraints.indexed = true

Runtime:

  1. SingleBetaConstraints.createBetaMemory()

    • IndexUtil$Factory$IndexSpec.init()
      • MVELConstraint.getFieldIndex()
        • new AbstractHashTable.FieldIndex(extractor, indexingDeclaration, PlainIndexEvaluator.INSTANCE);
    • IndexUtil$Factory.createBetaMemory()
      • IndexUtil$Factory.createLeftMemory()
        • TupleIndexRBTree is created for leftMemory
      • IndexUtil$Factory.createRightMemory()
        • TupleIndexRBTree is created for rightMemory (left = false, AbstractHashTable$FieldIndex is the same as leftMemory)

  2. PhreakExistsNode.doRightInserts()

    • rightTuple : RightTupleImpl(= Cheese "gorgonzola")
    • TupleIndexRBTree.add(rightTuple) for rightMemory
      • getLeftIndexedValue()
        • getIndexedValue() : left = false
        • (Comparable) index.getExtractor().getValue( tuple.getFactHandle().getObject() );
          • Get the value of Cheese.type (= "gorgonzola")
          • this is the key to insert into the tree
      • TupleList list = tree.insert(key);
        • this TupleList is the Node of the tree
      • list.add(tuple);
        • So we can add multiple tuples for the same key

  3. PhreakExistsNode.doLeftInserts()

    • srcLeftTuples : "stilton", "gorgonzola", "cheddar"

    • Loop 1 : leftTuple : NotNodeLeftTuple (= "stilton")

    • RuleNetworkEvaluator.findLeftTupleBlocker()

      • BetaNode.getFirstRightTuple() : This means, rightMemory is the tree. leftTuple is the key. So get the nearest rightTuple which matches the constraint [ type > $s (= leftTuple)]
      • TupleIndexRBTree.getFirst()
        • getRightIndexedValue() : NOTE that this inverses TupleIndexRBTree.left
          • getIndexedValue() : left = true
          • (Comparable) index.getDeclaration().getExtractor().getValue( tuple.getObject( index.getDeclaration() ) ) :
            • Get the object ("stilton") from NotNodeLeftTuple using declaration.getOffset(). This means it picks the expected value [$s]. (So, [$s] is "left")
      • getNext() : key = "stilton", first = true
        • getNextRight() : because this is rightMemory.
          • GREATER_THAN :
          • firstNode = tree.findNearestNode(key, false, Boundary.LOWER);
            • Boundary.LOWER means "If this key is lower than a treeNode, the treeNode matches"
          • TupleRBTree.findNearestNode()
            • compResult > 0 (<- "stilton" is larger than "gorgonzola")
            • acceptNode() returns false
            • n = accepted ^ boundary == Boundary.LOWER ? n.right : n.left;
              • true, so n.right. We want to traverse to upper nodes to find a match.
            • but no more node, so returns null

    • So RuleNetworkEvaluator.findLeftTupleBlocker() doesn't find a blocker.

    • ltm.add(leftTuple);

      • TupleIndexRBTree.add(leftTuple) for leftMemory
        • getLeftIndexedValue()
          • getIndexedValue() : left = true
          • (Comparable) index.getDeclaration().getExtractor().getValue( tuple.getObject( index.getDeclaration() ) ) :
            • Get the object ("stilton") from NotNodeLeftTuple using declaration.getOffset(). This means it picks the expected value [$s]. (So, [$s] is "left")
      • TupleList list = tree.insert(key);
        • So leftMemory tree is also maintained

    • Loop 2 : leftTuple : NotNodeLeftTuple (= "gorgonzola")

    • Similarly, RuleNetworkEvaluator.findLeftTupleBlocker() doesn't hit

    • ltm.add(leftTuple);

    • Loop 3 : leftTuple : NotNodeLeftTuple (= "cheddar")

    • RuleNetworkEvaluator.findLeftTupleBlocker()

      • tree.findNearestNode()
        • acceptNode() returns true
        • nearest = Node key=gorgonzola
        • n = n.left , We want to traverse to lower nodes to find a better match.
        • but no more node, so returns Node for "gorgonzola"
      • firstNode.getFirst() returns RightTupleImpl(= Cheese "gorgonzola")
      • RightTuple nextRight = (RightTuple) it.next(rightTuple);
      • if (constraints.isAllowedCachedLeft(contextEntry,
        • Retreive nextRight from iterator: all tuples should match the constraint
        • In isAllowedCachedLeft(), evaluation is skipped because it's indexed
        • leftTuple.setBlocker(rightTuple);
        • rightTuple.addBlocked(leftTuple);
          • It means the rightTuple(= Cheese "gorgonzola") blocks the leftTuple (= String "cheddar")

    • insertChildLeftTuple()

      • insert leftTuple to trgLeftTuples for the next sink

IndexingTest.testRangeIndexForJoin

rule R1
when
   $pet : Pet()
   Person( age > $pet.age )
then
end

ksession.insert(new Pet(PetType.CAT, 10));
ksession.insert(new Person("Paul", 20));
ksession.fireAllRules();

Rule Build:

  1. PatternBuilder.buildConstraintForPattern() puts [$pet] into declarations and picks [age] as decr.
  2. MVELConstraint [age > $pet.age] is created. indexingDeclaration is [age]
  3. JoinNode is created.
    • SingleBetaConstraints.initIndexes()
      • IndexUtil.canHaveRangeIndex() returns true
      • SingleBetaConstraints.indexed = true

Runtime:

  1. SingleBetaConstraints.createBetaMemory()

    • Same as ExistsNode. Create AbstractHashTable.FieldIndex and used it for both leftMemory TupleIndexRBTree and rightMemory TupleIndexRBTree.

  2. PhreakJoinNode.doRightInserts()

    • rightTuple : RightTupleImpl(= Person age=20)
    • TupleIndexRBTree.add(rightTuple) for rightMemory
      • getLeftIndexedValue()
        • getIndexedValue() : left = false
        • (Comparable) index.getExtractor().getValue( tuple.getFactHandle().getObject() );
          • Get the key (= 20)
      • insert to the rightMemory tree

  3. PhreakJoinNode.doLeftInserts()

    • srcLeftTuples : Pet age=10
    • leftTuple : JoinNodeLeftTuple (= Pet age=10)
    • ltm.add(leftTuple);
      • TupleIndexRBTree.add(leftTuple) for leftMemory
        • getLeftIndexedValue()
          • getIndexedValue() : left = true
          • (Comparable) index.getDeclaration().getExtractor().getValue( tuple.getObject( index.getDeclaration() ) ) :
            • Get the key (= 10) from JoinNodeLeftTuple using declaration.getOffset(). This means it picks the expected value [$pet.age]. (So, [$pet.age] is "left")
        • TupleList list = tree.insert(key);
          • So leftMemory tree is also maintained
    • BetaNode.getFirstRightTuple() : This means, rightMemory is the tree. leftTuple is the key. So get the nearest rightTuple which matches the constraint [ age > $pet.age ]
      • TupleIndexRBTree.getFirst()
        • getRightIndexedValue() : NOTE that this inverses TupleIndexRBTree.left
          • getIndexedValue() : left = true
          • (Comparable) index.getDeclaration().getExtractor().getValue( tuple.getObject( index.getDeclaration() ) ) :
            • Get the key (= 10) from JoinNodeLeftTuple using declaration.getOffset(). This means it picks the expected value [$pet.age]. (So, [$pet.age] is "left")
        • getNext() : key = 10, first = true
          • getNextRight() : because this is rightMemory.
            • GREATER_THAN :
            • firstNode = tree.findNearestNode(key, false, Boundary.LOWER);
              • Boundary.LOWER means "If this key is lower than a treeNode, the treeNode matches"
            • TupleRBTree.findNearestNode()
              • compResult < 0
              • acceptNode() returns true. nearest = Node key=20
              • n = accepted ^ boundary == Boundary.LOWER ? n.right : n.left;
                • false, so n.left. We want to traverse to lower nodes to find a better match.
              • but no more node, so returns Node (Person age=20)
    • isAllowedCachedLeft() skips evaluation because the constraint is indexed
    • insertChildLeftTuple()
      • insert a new leftTuple to trgLeftTuples for the next sink

What is left?

TupleIndexRBTree

    private Comparable getIndexedValue( Tuple tuple, boolean left ) {
        return left ?
               (Comparable) index.getDeclaration().getExtractor().getValue( tuple.getObject( index.getDeclaration() ) ) :
               (Comparable) index.getExtractor().getValue( tuple.getFactHandle().getObject() );
    }
  • left = true : get a value from "indexingDeclaration"
  • left = false : get a value from the fact itself
Clone this wiki locally