001: /*
002: * Copyright Aduna (http://www.aduna-software.com/) (c) 2008.
003: *
004: * Licensed under the Aduna BSD-style license.
005: */
006: package org.openrdf.sail.rdbms.optimizers;
007:
008: import static org.openrdf.sail.rdbms.algebra.ColumnVar.createCtx;
009: import static org.openrdf.sail.rdbms.algebra.ColumnVar.createObj;
010: import static org.openrdf.sail.rdbms.algebra.ColumnVar.createPred;
011: import static org.openrdf.sail.rdbms.algebra.ColumnVar.createSubj;
012: import static org.openrdf.sail.rdbms.algebra.base.SqlExprSupport.coalesce;
013: import static org.openrdf.sail.rdbms.algebra.base.SqlExprSupport.eq;
014: import static org.openrdf.sail.rdbms.algebra.base.SqlExprSupport.isNull;
015: import static org.openrdf.sail.rdbms.algebra.base.SqlExprSupport.or;
016:
017: import java.sql.SQLException;
018: import java.util.ArrayList;
019: import java.util.HashMap;
020: import java.util.HashSet;
021: import java.util.List;
022: import java.util.Map;
023: import java.util.Set;
024:
025: import org.openrdf.model.BNode;
026: import org.openrdf.model.Literal;
027: import org.openrdf.model.Resource;
028: import org.openrdf.model.URI;
029: import org.openrdf.model.Value;
030: import org.openrdf.query.BindingSet;
031: import org.openrdf.query.Dataset;
032: import org.openrdf.query.algebra.And;
033: import org.openrdf.query.algebra.Distinct;
034: import org.openrdf.query.algebra.Filter;
035: import org.openrdf.query.algebra.Join;
036: import org.openrdf.query.algebra.LeftJoin;
037: import org.openrdf.query.algebra.Order;
038: import org.openrdf.query.algebra.OrderElem;
039: import org.openrdf.query.algebra.Projection;
040: import org.openrdf.query.algebra.ProjectionElem;
041: import org.openrdf.query.algebra.ProjectionElemList;
042: import org.openrdf.query.algebra.Slice;
043: import org.openrdf.query.algebra.StatementPattern;
044: import org.openrdf.query.algebra.TupleExpr;
045: import org.openrdf.query.algebra.Union;
046: import org.openrdf.query.algebra.ValueExpr;
047: import org.openrdf.query.algebra.Var;
048: import org.openrdf.query.algebra.StatementPattern.Scope;
049: import org.openrdf.query.algebra.evaluation.QueryOptimizer;
050: import org.openrdf.sail.rdbms.RdbmsValueFactory;
051: import org.openrdf.sail.rdbms.algebra.BNodeColumn;
052: import org.openrdf.sail.rdbms.algebra.ColumnVar;
053: import org.openrdf.sail.rdbms.algebra.DatatypeColumn;
054: import org.openrdf.sail.rdbms.algebra.IdColumn;
055: import org.openrdf.sail.rdbms.algebra.JoinItem;
056: import org.openrdf.sail.rdbms.algebra.LabelColumn;
057: import org.openrdf.sail.rdbms.algebra.LanguageColumn;
058: import org.openrdf.sail.rdbms.algebra.LongLabelColumn;
059: import org.openrdf.sail.rdbms.algebra.LongURIColumn;
060: import org.openrdf.sail.rdbms.algebra.NumberValue;
061: import org.openrdf.sail.rdbms.algebra.RefIdColumn;
062: import org.openrdf.sail.rdbms.algebra.SelectProjection;
063: import org.openrdf.sail.rdbms.algebra.SelectQuery;
064: import org.openrdf.sail.rdbms.algebra.SqlEq;
065: import org.openrdf.sail.rdbms.algebra.SqlOr;
066: import org.openrdf.sail.rdbms.algebra.URIColumn;
067: import org.openrdf.sail.rdbms.algebra.UnionItem;
068: import org.openrdf.sail.rdbms.algebra.base.RdbmsQueryModelVisitorBase;
069: import org.openrdf.sail.rdbms.algebra.base.SqlExpr;
070: import org.openrdf.sail.rdbms.algebra.factories.SqlExprFactory;
071: import org.openrdf.sail.rdbms.exceptions.RdbmsException;
072: import org.openrdf.sail.rdbms.exceptions.RdbmsRuntimeException;
073: import org.openrdf.sail.rdbms.exceptions.UnsupportedRdbmsOperatorException;
074: import org.openrdf.sail.rdbms.managers.TransTableManager;
075: import org.openrdf.sail.rdbms.model.RdbmsResource;
076: import org.openrdf.sail.rdbms.schema.IdSequence;
077:
078: /**
079: * Rewrites the core algebra model with a relation optimised model, using SQL.
080: *
081: * @author James Leigh
082: *
083: */
084: public class SelectQueryOptimizer extends
085: RdbmsQueryModelVisitorBase<RuntimeException> implements
086: QueryOptimizer {
087: private static final String ALIAS = "t";
088: private SqlExprFactory sql;
089: private int aliasCount = 0;
090: private BindingSet bindings;
091: private Dataset dataset;
092: private RdbmsValueFactory vf;
093: private TransTableManager tables;
094: private IdSequence ids;
095:
096: public void setSqlExprFactory(SqlExprFactory sql) {
097: this .sql = sql;
098: }
099:
100: public void setValueFactory(RdbmsValueFactory vf) {
101: this .vf = vf;
102: }
103:
104: public void setTransTableManager(TransTableManager statements) {
105: this .tables = statements;
106: }
107:
108: public void setIdSequence(IdSequence ids) {
109: this .ids = ids;
110: }
111:
112: public void optimize(TupleExpr tupleExpr, Dataset dataset,
113: BindingSet bindings) {
114: this .dataset = dataset;
115: this .bindings = bindings;
116: tupleExpr.visit(this );
117: }
118:
119: @Override
120: public void meet(Distinct node) throws RuntimeException {
121: super .meet(node);
122: if (node.getArg() instanceof SelectQuery) {
123: SelectQuery query = (SelectQuery) node.getArg();
124: query.setDistinct(true);
125: node.replaceWith(query);
126: }
127: }
128:
129: @Override
130: public void meet(Union node) throws RuntimeException {
131: super .meet(node);
132: TupleExpr l = node.getLeftArg();
133: TupleExpr r = node.getRightArg();
134: if (!(l instanceof SelectQuery && r instanceof SelectQuery))
135: return;
136: SelectQuery left = (SelectQuery) l;
137: SelectQuery right = (SelectQuery) r;
138: if (left.isComplex() || right.isComplex())
139: return;
140: UnionItem union = new UnionItem("u" + aliasCount++);
141: union.addUnion(left.getFrom().clone());
142: union.addUnion(right.getFrom().clone());
143: SelectQuery query = new SelectQuery();
144: query.setFrom(union);
145: mergeSelectClause(query, left);
146: mergeSelectClause(query, right);
147: node.replaceWith(query);
148: }
149:
150: @Override
151: public void meet(Join node) throws RuntimeException {
152: super .meet(node);
153: TupleExpr l = node.getLeftArg();
154: TupleExpr r = node.getRightArg();
155: if (!(l instanceof SelectQuery && r instanceof SelectQuery))
156: return;
157: SelectQuery left = (SelectQuery) l;
158: SelectQuery right = (SelectQuery) r;
159: if (left.isComplex() || right.isComplex())
160: return;
161: left = left.clone();
162: right = right.clone();
163: filterOn(left, right);
164: mergeSelectClause(left, right);
165: left.addJoin(right);
166: node.replaceWith(left);
167: }
168:
169: @Override
170: public void meet(LeftJoin node) throws RuntimeException {
171: super .meet(node);
172: TupleExpr l = node.getLeftArg();
173: TupleExpr r = node.getRightArg();
174: if (!(l instanceof SelectQuery && r instanceof SelectQuery))
175: return;
176: SelectQuery left = (SelectQuery) l;
177: SelectQuery right = (SelectQuery) r;
178: if (left.isComplex() || right.isComplex())
179: return;
180: left = left.clone();
181: right = right.clone();
182: filterOn(left, right);
183: mergeSelectClause(left, right);
184: left.addLeftJoin(right);
185: List<SqlExpr> filters = new ArrayList<SqlExpr>();
186: if (node.getCondition() != null) {
187: for (ValueExpr expr : flatten(node.getCondition())) {
188: try {
189: filters.add(sql.createBooleanExpr(expr));
190: } catch (UnsupportedRdbmsOperatorException e) {
191: return;
192: }
193: }
194: }
195: for (SqlExpr filter : filters) {
196: right.addFilter(filter);
197: }
198: node.replaceWith(left);
199: }
200:
201: @Override
202: public void meet(StatementPattern sp) {
203: super .meet(sp);
204: Var subjVar = sp.getSubjectVar();
205: Var predVar = sp.getPredicateVar();
206: Var objVar = sp.getObjectVar();
207: Var ctxVar = sp.getContextVar();
208:
209: Value subjValue = getVarValue(subjVar, bindings);
210: Value predValue = getVarValue(predVar, bindings);
211: Value objValue = getVarValue(objVar, bindings);
212: Value ctxValue = getVarValue(ctxVar, bindings);
213:
214: if (subjValue instanceof Literal
215: || predValue instanceof Literal
216: || predValue instanceof BNode
217: || ctxValue instanceof Literal) {
218: // subj and ctx must be a Resource and pred must be a URI
219: return;
220: }
221:
222: Resource[] contexts = getContexts(sp, ctxValue);
223: if (contexts == null)
224: return;
225:
226: String alias = getTableAlias(predValue) + aliasCount++;
227: Number predId = getInternalId(predValue);
228: String tableName;
229: boolean present;
230: try {
231: tableName = tables.getTableName(predId);
232: present = tables.isPredColumnPresent(predId);
233: } catch (SQLException e) {
234: throw new RdbmsRuntimeException(e);
235: }
236: JoinItem from = new JoinItem(alias, tableName, predId);
237:
238: ColumnVar s = createSubj(alias, subjVar, (Resource) subjValue);
239: ColumnVar p = createPred(alias, predVar, (URI) predValue,
240: !present);
241: ColumnVar o = createObj(alias, objVar, objValue);
242: ColumnVar c = createCtx(alias, ctxVar, (Resource) ctxValue);
243:
244: s.setTypes(tables.getSubjTypes(predId));
245: o.setTypes(tables.getObjTypes(predId));
246:
247: SelectQuery query = new SelectQuery();
248: query.setFrom(from);
249: Map<String, ColumnVar> vars = new HashMap<String, ColumnVar>(4);
250: for (ColumnVar var : new ColumnVar[] { s, p, o, c }) {
251: from.addVar(var);
252: Value value = var.getValue();
253: if (vars.containsKey(var.getName())) {
254: IdColumn existing = new IdColumn(vars
255: .get(var.getName()));
256: from.addFilter(new SqlEq(new IdColumn(var), existing));
257: } else if (value != null && !var.isImplied()) {
258: try {
259: NumberValue vc = new NumberValue(vf
260: .getInternalId(value));
261: from.addFilter(new SqlEq(new RefIdColumn(var), vc));
262: } catch (RdbmsException e) {
263: throw new RdbmsRuntimeException(e);
264: }
265: } else {
266: vars.put(var.getName(), var);
267: }
268: if (!var.isHidden() && value == null) {
269: SelectProjection proj = new SelectProjection();
270: proj.setVar(var);
271: proj.setId(new RefIdColumn(var));
272: proj.setStringValue(coalesce(new URIColumn(var),
273: new BNodeColumn(var), new LabelColumn(var),
274: new LongLabelColumn(var),
275: new LongURIColumn(var)));
276: proj.setDatatype(new DatatypeColumn(var));
277: proj.setLanguage(new LanguageColumn(var));
278: query.addSqlSelectVar(proj);
279: }
280: }
281: if (contexts.length > 0) {
282: RdbmsResource[] ids = vf.asRdbmsResource(contexts);
283: RefIdColumn var = new RefIdColumn(c);
284: SqlExpr in = null;
285: for (RdbmsResource id : ids) {
286: NumberValue longValue;
287: try {
288: longValue = new NumberValue(vf.getInternalId(id));
289: } catch (RdbmsException e) {
290: throw new RdbmsRuntimeException(e);
291: }
292: SqlEq eq = new SqlEq(var.clone(), longValue);
293: if (in == null) {
294: in = eq;
295: } else {
296: in = new SqlOr(in, eq);
297: }
298: }
299: from.addFilter(in);
300: }
301: sp.replaceWith(query);
302: }
303:
304: @Override
305: public void meet(Filter node) throws RuntimeException {
306: super .meet(node);
307: if (node.getArg() instanceof SelectQuery) {
308: SelectQuery query = (SelectQuery) node.getArg();
309: ValueExpr condition = null;
310: for (ValueExpr expr : flatten(node.getCondition())) {
311: try {
312: query.addFilter(sql.createBooleanExpr(expr));
313: } catch (UnsupportedRdbmsOperatorException e) {
314: if (condition == null) {
315: condition = expr;
316: } else {
317: condition = new And(condition, expr);
318: }
319: }
320: }
321: if (condition == null) {
322: node.replaceWith(node.getArg());
323: } else {
324: node.setCondition(condition);
325: }
326: }
327: }
328:
329: @Override
330: public void meet(Projection node) throws RuntimeException {
331: super .meet(node);
332: if (node.getArg() instanceof SelectQuery) {
333: SelectQuery query = (SelectQuery) node.getArg();
334: Map<String, String> bindingNames = new HashMap<String, String>();
335: List<SelectProjection> selection = new ArrayList<SelectProjection>();
336: ProjectionElemList list = node.getProjectionElemList();
337: for (ProjectionElem e : list.getElements()) {
338: String source = e.getSourceName();
339: String target = e.getTargetName();
340: bindingNames.put(source, target);
341: SelectProjection s = query.getSelectProjection(source);
342: if (s != null) {
343: selection.add(s);
344: }
345: }
346: query.setBindingNames(bindingNames);
347: query.setSqlSelectVar(selection);
348: node.replaceWith(query);
349: }
350: }
351:
352: @Override
353: public void meet(Slice node) throws RuntimeException {
354: super .meet(node);
355: if (node.getArg() instanceof SelectQuery) {
356: SelectQuery query = (SelectQuery) node.getArg();
357: if (node.getOffset() > 0) {
358: query.setOffset(node.getOffset());
359: }
360: if (node.getLimit() >= 0) {
361: query.setLimit(node.getLimit());
362: }
363: node.replaceWith(query);
364: }
365: }
366:
367: @Override
368: public void meet(Order node) throws RuntimeException {
369: super .meet(node);
370: if (!(node.getArg() instanceof SelectQuery))
371: return;
372: SelectQuery query = (SelectQuery) node.getArg();
373: try {
374: for (OrderElem e : node.getElements()) {
375: ValueExpr expr = e.getExpr();
376: boolean asc = e.isAscending();
377: query.addOrder(sql.createBNodeExpr(expr), asc);
378: query.addOrder(sql.createUriExpr(expr), asc);
379: query.addOrder(sql.createNumericExpr(expr), asc);
380: query.addOrder(sql.createDatatypeExpr(expr), asc);
381: query.addOrder(sql.createTimeExpr(expr), asc);
382: query.addOrder(sql.createLanguageExpr(expr), asc);
383: query.addOrder(sql.createLabelExpr(expr), asc);
384: }
385: node.replaceWith(query);
386: } catch (UnsupportedRdbmsOperatorException e) {
387: // unsupported
388: }
389: }
390:
391: private void filterOn(SelectQuery left, SelectQuery right) {
392: Map<String, ColumnVar> lvars = left.getVarMap();
393: Map<String, ColumnVar> rvars = right.getVarMap();
394: Set<String> names = new HashSet<String>(rvars.keySet());
395: names.retainAll(lvars.keySet());
396: for (String name : names) {
397: ColumnVar l = lvars.get(name);
398: ColumnVar r = rvars.get(name);
399: if (!l.isImplied() && !r.isImplied()) {
400: IdColumn rid = new IdColumn(r);
401: SqlExpr filter = eq(rid, new IdColumn(l));
402: if (r.isNullable()) {
403: filter = or(isNull(rid), filter);
404: }
405: right.addFilter(filter);
406: }
407: }
408: }
409:
410: private Number getInternalId(Value predValue) {
411: try {
412: return vf.getInternalId(predValue);
413: } catch (RdbmsException e) {
414: throw new RdbmsRuntimeException(e);
415: }
416: }
417:
418: private Resource[] getContexts(StatementPattern sp, Value ctxValue) {
419: if (dataset == null) {
420: if (ctxValue != null)
421: return new Resource[] { (Resource) ctxValue };
422: return new Resource[0];
423: }
424: Set<URI> graphs = getGraphs(sp);
425: if (graphs.isEmpty())
426: return null; // Search zero contexts
427: if (ctxValue == null)
428: return graphs.toArray(new Resource[graphs.size()]);
429:
430: if (graphs.contains(ctxValue))
431: return new Resource[] { (Resource) ctxValue };
432: // pattern specifies a context that is not part of the dataset
433: return null;
434: }
435:
436: private Set<URI> getGraphs(StatementPattern sp) {
437: if (sp.getScope() == Scope.DEFAULT_CONTEXTS)
438: return dataset.getDefaultGraphs();
439: return dataset.getNamedGraphs();
440: }
441:
442: private String getTableAlias(Value predValue) {
443: if (predValue != null) {
444: String localName = ((URI) predValue).getLocalName();
445: if (localName.length() >= 1) {
446: String alias = localName.substring(0, 1);
447: if (isLetters(alias)) {
448: return alias;
449: }
450: }
451: }
452: return ALIAS;
453: }
454:
455: private Value getVarValue(Var var, BindingSet bindings) {
456: if (var == null) {
457: return null;
458: } else if (var.hasValue()) {
459: return var.getValue();
460: } else {
461: return bindings.getValue(var.getName());
462: }
463: }
464:
465: private boolean isLetters(String alias) {
466: for (int i = 0, n = alias.length(); i < n; i++) {
467: if (!Character.isLetter(alias.charAt(i)))
468: return false;
469: }
470: return true;
471: }
472:
473: private void mergeSelectClause(SelectQuery left, SelectQuery right) {
474: for (SelectProjection proj : right.getSqlSelectVar()) {
475: if (!left.hasSqlSelectVar(proj)) {
476: proj = proj.clone();
477: ColumnVar var = proj.getVar();
478: String name = var.getName();
479: ColumnVar existing = left.getVar(name);
480: if (existing != null) {
481: proj.setVar(existing);
482: }
483: left.addSqlSelectVar(proj);
484: }
485: }
486: }
487:
488: private List<ValueExpr> flatten(ValueExpr condition) {
489: return flatten(condition, new ArrayList<ValueExpr>());
490: }
491:
492: private List<ValueExpr> flatten(ValueExpr condition,
493: List<ValueExpr> conditions) {
494: if (condition instanceof And) {
495: And and = (And) condition;
496: flatten(and.getLeftArg(), conditions);
497: flatten(and.getRightArg(), conditions);
498: } else {
499: conditions.add(condition);
500: }
501: return conditions;
502: }
503: }
|