Thread: [Bigdata-commit] SF.net SVN: bigdata:[3378] branches/QUADS_QUERY_BRANCH/bigdata

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

Revision: 3378
          http://bigdata.svn.sourceforge.net/bigdata/?rev=3378&view=rev
Author:   mrpersonick
Date:     2010-07-30 21:46:03 +0000 (Fri, 30 Jul 2010)

Log Message:
-----------
adding a goto for optional predicates

Modified Paths:
--------------
    branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/relation/rule/IPredicate.java
    branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/relation/rule/Predicate.java
    branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/magic/MagicPredicate.java
    branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/spo/SPOPredicate.java
    branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/spo/SPOStarJoin.java

Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/relation/rule/IPredicate.java
===================================================================

--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/relation/rule/IPredicate.java	2010-07-30 20:41:35 UTC (rev 3377)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/relation/rule/IPredicate.java	2010-07-30 21:46:03 UTC (rev 3378)
@@ -157,6 +157,69 @@
      *         evaluating a JOIN.
      */
     public boolean isOptional();
+    
+    /**
+     * Handling nested optional joins can be reduced to a goto logic.  Tails
+     * that are grouped inside an "optional join" are all marked as optional,
+     * and if any one of them fails then join execution should resume with the
+     * tail immediately following the optional join in the plan order.
+     * <p>
+     * For example, the following query:
+     * <code>
+     * where {
+     *    A .
+     *    OPTIONAL {
+     *      B .
+     *      C .
+     *    }
+     *    D .
+     * }
+     * </code>
+     * <p>
+     * Would yield the following plan:
+     * <code>
+     * 0: A, optional=false
+     * 1: B, optional=true, goto=3
+     * 2: C, optional=true, goto=3
+     * 3: D, optional=false
+     * </code>
+     * <p>
+     * Double nested optionals would just continue on in the first optional 
+     * join. For example, the following query:
+     * <code>
+     * where {
+     *    A .
+     *    OPTIONAL {
+     *      B .
+     *      OPTIONAL { C } .
+     *      D .
+     *    }
+     *    E .
+     * }
+     * </code>
+     * <p>
+     * Would yield the following plan:
+     * <code>
+     * 0: A, optional=false
+     * 1: B, optional=true, goto=4
+     * 2: C, optional=true, goto=3
+     * 3: D, optional=true, goto=4
+     * 4: E, optional=false
+     * </code>
+     * <p>
+     * Alternatively, the above plan could be reordered as follows for more
+     * efficient execution:
+     * <code>
+     * 0: A, optional=false
+     * 1: B, optional=true, goto=4
+     * 2: D, optional=true, goto=4
+     * 3: C, optional=true, goto=4
+     * 4: E, optional=false
+     * </code>
+     * 
+     * @return
+     */
+    public int getOptionalGoto();
 
     /**
      * Returns the object that may be used to selectively override the

Modified: branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/relation/rule/Predicate.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/relation/rule/Predicate.java	2010-07-30 20:41:35 UTC (rev 3377)
+++ branches/QUADS_QUERY_BRANCH/bigdata/src/java/com/bigdata/relation/rule/Predicate.java	2010-07-30 21:46:03 UTC (rev 3378)
@@ -64,7 +64,7 @@
     
     private final IVariableOrConstant[] values;
     
-    private final boolean optional;
+    private final int optionalGoto;
     
     private final IElementFilter<E> constraint;
 
@@ -90,7 +90,7 @@
 
         this.values = src.values.clone();
 
-        this.optional = src.optional;
+        this.optionalGoto = src.optionalGoto;
         
         this.constraint = src.constraint;
 
@@ -161,7 +161,7 @@
 
         this.values = src.values;
 
-        this.optional = src.optional;
+        this.optionalGoto = src.optionalGoto;
         
         this.constraint = src.constraint;
         
@@ -209,7 +209,7 @@
 
         this.values = src.values;
 
-        this.optional = src.optional;
+        this.optionalGoto = src.optionalGoto;
 
         this.constraint = src.constraint;
 
@@ -228,7 +228,7 @@
     public Predicate(String relationName, IVariableOrConstant[] values) {
         
         this(new String[] { relationName }, -1/* partitionId */, values,
-                false/* optional */, null/* constraint */, null/* expander */);
+                -1/* optional=false */, null/* constraint */, null/* expander */);
         
     }
 
@@ -250,7 +250,7 @@
      *            Allows selective override of the predicate evaluation.
      */
     public Predicate(String[] relationName, int partitionId,
-            IVariableOrConstant[] values, boolean optional,
+            IVariableOrConstant[] values, int optionalGoto,
             IElementFilter<E> constraint, ISolutionExpander<E> expander) {
 
         if (relationName == null)
@@ -286,7 +286,7 @@
 
         this.values = values;
         
-        this.optional = optional;
+        this.optionalGoto = optionalGoto;
         
         this.constraint = constraint;
         
@@ -345,10 +345,16 @@
 
     final public boolean isOptional() {
         
-        return optional;
+        return optionalGoto >= 0;
         
     }
     
+    final public int getOptionalGoto() {
+        
+        return optionalGoto;
+        
+    }
+    
     final public IElementFilter<E> getConstraint() {
 
         return constraint;

Modified: branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/magic/MagicPredicate.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/magic/MagicPredicate.java	2010-07-30 20:41:35 UTC (rev 3377)
+++ branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/magic/MagicPredicate.java	2010-07-30 21:46:03 UTC (rev 3378)
@@ -479,6 +479,12 @@
         
     }
     
+    final public int getOptionalGoto() {
+        
+        return -1;
+        
+    }
+    
     final public IElementFilter getConstraint() {
 
         return constraint;

Modified: branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/spo/SPOPredicate.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/spo/SPOPredicate.java	2010-07-30 20:41:35 UTC (rev 3377)
+++ branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/spo/SPOPredicate.java	2010-07-30 21:46:03 UTC (rev 3378)
@@ -76,7 +76,7 @@
     /** The context position MAY be <code>null</code>. */
     protected final IVariableOrConstant<IV> c;
 
-    protected final boolean optional;
+    protected final int optionalGoto;
     
     protected final IElementFilter<ISPO> constraint;
 
@@ -134,7 +134,7 @@
             final IVariableOrConstant<IV> p, final IVariableOrConstant<IV> o) {
 
         this(new String[] { relationName }, -1/* partitionId */, s, p, o,
-                null/* c */, false/* optional */, null/* constraint */, null/* expander */);
+                null/* c */, -1/* optional */, null/* constraint */, null/* expander */);
 
     }
 
@@ -154,7 +154,7 @@
             final IVariableOrConstant<IV> o, final IVariableOrConstant<IV> c) {
 
         this(new String[] { relationName }, -1/* partitionId */, s, p, o, c,
-                false/* optional */, null/* constraint */, null/* expander */);
+                -1/* optional */, null/* constraint */, null/* expander */);
 
     }
 
@@ -173,7 +173,7 @@
             final IVariableOrConstant<IV> p, final IVariableOrConstant<IV> o) {
 
         this(relationName, -1/* partitionId */, s, p, o,
-                null/* c */, false/* optional */, null/* constraint */, null/* expander */);
+                null/* c */, -1/* optional */, null/* constraint */, null/* expander */);
 
     }
 
@@ -190,10 +190,10 @@
     public SPOPredicate(final String relationName,
             final IVariableOrConstant<IV> s,
             final IVariableOrConstant<IV> p,
-            final IVariableOrConstant<IV> o, final boolean optional) {
+            final IVariableOrConstant<IV> o, final int optionalGoto) {
 
         this(new String[] { relationName }, -1/* partitionId */, s, p, o,
-                null/* c */, optional, null/* constraint */, null/* expander */);
+                null/* c */, optionalGoto, null/* constraint */, null/* expander */);
 
     }
 
@@ -215,7 +215,7 @@
             final ISolutionExpander<ISPO> expander) {
 
         this(new String[] { relationName }, -1/* partitionId */, s, p, o,
-                null/* c */, false/* optional */, null/* constraint */,
+                null/* c */, -1/* optional */, null/* constraint */,
                 expander);
 
     }
@@ -235,11 +235,11 @@
     public SPOPredicate(final String relationName,
             final IVariableOrConstant<IV> s,
             final IVariableOrConstant<IV> p,
-            final IVariableOrConstant<IV> o, final boolean optional,
+            final IVariableOrConstant<IV> o, final int optionalGoto,
             final ISolutionExpander<ISPO> expander) {
 
         this(new String[] { relationName }, -1/* partitionId */, s, p, o,
-                null/* c */, optional, null/* constraint */, expander);
+                null/* c */, optionalGoto, null/* constraint */, expander);
         
     }
     
@@ -264,7 +264,7 @@
             final IVariableOrConstant<IV> p,//
             final IVariableOrConstant<IV> o,//
             final IVariableOrConstant<IV> c,//
-            final boolean optional, //
+            final int optionalGoto, //
             final IElementFilter<ISPO> constraint,//
             final ISolutionExpander<ISPO> expander//
             ) {
@@ -303,7 +303,7 @@
         this.o = o;
         this.c = c; // MAY be null.
 
-        this.optional = optional;
+        this.optionalGoto = optionalGoto;
         
         this.constraint = constraint; /// MAY be null.
         
@@ -341,7 +341,7 @@
         
         this.relationName = relationName; // override.
      
-        this.optional = src.optional;
+        this.optionalGoto = src.optionalGoto;
         
         this.constraint = src.constraint;
         
@@ -384,7 +384,7 @@
         this.o = src.o;
         this.c = src.c;
         
-        this.optional = src.optional;
+        this.optionalGoto = src.optionalGoto;
         
         this.constraint = src.constraint;
         
@@ -406,7 +406,7 @@
         this.o = src.o;
         this.c = src.c;
         
-        this.optional = src.optional;
+        this.optionalGoto = src.optionalGoto;
         
         this.constraint = src.constraint;
         
@@ -439,7 +439,7 @@
                 p,//
                 o,//
                 c, // override.
-                optional, //
+                optionalGoto, //
                 constraint,//
                 expander//
         );
@@ -465,7 +465,7 @@
                 p,//
                 o,//
                 c, // 
-                optional, //
+                optionalGoto, //
                 tmp,// override.
                 expander//
         );
@@ -795,7 +795,7 @@
         }
         
         return new SPOPredicate(relationName, partitionId, s, p, o, c,
-                optional, constraint, expander);
+                optionalGoto, constraint, expander);
         
     }
 
@@ -861,7 +861,7 @@
         
         sb.append(")");
 
-        if (optional || constraint != null || expander != null
+        if (isOptional() || constraint != null || expander != null
                 || partitionId != -1) {
             
             /*
@@ -872,9 +872,9 @@
             
             sb.append("[");
             
-            if(optional) {
+            if(isOptional()) {
                 if(!first) sb.append(", ");
-                sb.append("optional");
+                sb.append("optionalGoto="+optionalGoto);
                 first = false;
             }
 
@@ -906,10 +906,16 @@
 
     final public boolean isOptional() {
         
-        return optional;
+        return optionalGoto >= -1;
         
     }
     
+    final public int getOptionalGoto() {
+        
+        return optionalGoto;
+        
+    }
+    
     final public IElementFilter<ISPO> getConstraint() {
 
         return constraint;
@@ -984,7 +990,7 @@
             final IVariableOrConstant<IV> c) {
 
         return new SPOPredicate(relationName, partitionId, s, p, o, c,
-                optional, constraint, expander);
+                optionalGoto, constraint, expander);
         
     }
 }

Modified: branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/spo/SPOStarJoin.java
===================================================================
--- branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/spo/SPOStarJoin.java	2010-07-30 20:41:35 UTC (rev 3377)
+++ branches/QUADS_QUERY_BRANCH/bigdata-rdf/src/java/com/bigdata/rdf/spo/SPOStarJoin.java	2010-07-30 21:46:03 UTC (rev 3378)
@@ -71,7 +71,7 @@
     public SPOStarJoin(final SPOPredicate pred) {
         
         this(pred.relationName, pred.partitionId, pred.s(), Var.var(), 
-                Var.var(), pred.c(), pred.isOptional(), 
+                Var.var(), pred.c(), pred.getOptionalGoto(), 
                 pred.getConstraint(), pred.getSolutionExpander());
         
     }
@@ -89,7 +89,7 @@
 
         this(new String[] { relationName }, -1/* partitionId */, s, 
                 Var.var(), Var.var(),
-                null/* c */, false/* optional */, null/* constraint */, 
+                null/* c */, -1/* optional */, null/* constraint */, 
                 null/* expander */);
 
     }
@@ -116,12 +116,12 @@
             final IVariableOrConstant<IV> p,//
             final IVariableOrConstant<IV> o,//
             final IVariableOrConstant<IV> c,//
-            final boolean optional, //
+            final int optionalGoto, //
             final IElementFilter<ISPO> constraint,//
             final ISolutionExpander<ISPO> expander//
             ) {
         
-        super(relationName, partitionId, s, p, o, c, optional, constraint, 
+        super(relationName, partitionId, s, p, o, c, optionalGoto, constraint, 
                 expander);
     
         this.starConstraints = new LinkedList<IStarConstraint<ISPO>>();
@@ -188,7 +188,7 @@
         SPOPredicate pred = super.asBound(bindingSet);
         
         SPOStarJoin starJoin = new SPOStarJoin(pred.relationName, 
-                pred.partitionId, pred.s, pred.p, pred.o, pred.c, pred.optional, 
+                pred.partitionId, pred.s, pred.p, pred.o, pred.c, pred.optionalGoto, 
                 pred.constraint, pred.expander);
         
         for (IStarConstraint starConstraint : starConstraints) {


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.




Thread: [Bigdata-commit] SF.net SVN: bigdata:[3378] branches/QUADS_QUERY_BRANCH/bigdata

Fast, scalable, robust graph database platform

bigdata-commit