Menu
▾
▴
[Bigdata-commit] SF.net SVN: bigdata:[3378] branches/QUADS_QUERY_BRANCH/bigdata
|
From: <mrp...@us...> - 2010-07-30 21:46:09
|
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.
|
