001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.table;
007:
008: import java.sql.SQLException;
009:
010: import org.h2.command.Parser;
011: import org.h2.command.dml.Select;
012: import org.h2.constant.SysProperties;
013: import org.h2.engine.Right;
014: import org.h2.engine.Session;
015: import org.h2.expression.ConditionAndOr;
016: import org.h2.expression.Expression;
017: import org.h2.index.Cursor;
018: import org.h2.index.Index;
019: import org.h2.index.IndexCondition;
020: import org.h2.message.Message;
021: import org.h2.result.Row;
022: import org.h2.result.SearchRow;
023: import org.h2.result.SortOrder;
024: import org.h2.util.ObjectArray;
025: import org.h2.util.StringUtils;
026: import org.h2.value.Value;
027:
028: /**
029: * A table filter represents a table that is used in a query. There is one such
030: * object whenever a table (or view) is used in a query. For example the
031: * following query has 2 table filters: SELECT * FROM TEST T1, TEST T2.
032: */
033: public class TableFilter implements ColumnResolver {
034: private static final int BEFORE_FIRST = 0, FOUND = 1,
035: AFTER_LAST = 2, NULL_ROW = 3;
036: private final Table table;
037: private final Select select;
038: private String alias;
039: private Session session;
040: private Index index;
041: private IndexColumn[] indexColumns;
042: private Cursor cursor;
043: private int scanCount;
044: private boolean used; // used in the plan
045:
046: // conditions that can be used for direct index lookup (start or end)
047: private final ObjectArray indexConditions = new ObjectArray();
048:
049: // conditions that can't be used for index lookup,
050: // but for row filter for this table (ID=ID, NAME LIKE '%X%')
051: private Expression filterCondition;
052:
053: // the complete join condition
054: private Expression joinCondition;
055: private SearchRow currentSearchRow;
056: private Row current;
057: private int state;
058:
059: private TableFilter join;
060:
061: private boolean outerJoin;
062: private boolean foundOne;
063: private Expression fullCondition;
064:
065: public TableFilter(Session session, Table table, String alias,
066: boolean rightsChecked, Select select) throws SQLException {
067: this .session = session;
068: this .table = table;
069: this .alias = alias;
070: this .select = select;
071: if (!rightsChecked) {
072: session.getUser().checkRight(table, Right.SELECT);
073: }
074: }
075:
076: public Select getSelect() {
077: return select;
078: }
079:
080: public Table getTable() {
081: return table;
082: }
083:
084: public void lock(Session session, boolean exclusive, boolean force)
085: throws SQLException {
086: table.lock(session, exclusive, force);
087: if (join != null) {
088: join.lock(session, exclusive, force);
089: }
090: }
091:
092: public PlanItem getBestPlanItem(Session session)
093: throws SQLException {
094: PlanItem item;
095: if (indexConditions.size() == 0) {
096: item = new PlanItem();
097: item.setIndex(table.getScanIndex(session));
098: item.cost = item.getIndex().getCost(session, null);
099: } else {
100: int len = table.getColumns().length;
101: int[] masks = new int[len];
102: for (int i = 0; i < indexConditions.size(); i++) {
103: IndexCondition condition = (IndexCondition) indexConditions
104: .get(i);
105: if (condition.isEvaluatable()) {
106: if (condition.isAlwaysFalse()) {
107: masks = null;
108: break;
109: } else {
110: int id = condition.getColumn().getColumnId();
111: masks[id] |= condition.getMask();
112: }
113: }
114: }
115: item = table.getBestPlanItem(session, masks);
116: }
117: if (join != null) {
118: setEvaluatable(join);
119: item.setJoinPlan(join.getBestPlanItem(session));
120: // TODO optimizer: calculate cost of a join: should use separate
121: // expected row number and lookup cost
122: item.cost += item.cost * item.getJoinPlan().cost;
123: }
124: return item;
125: }
126:
127: private void setEvaluatable(TableFilter join) {
128: // this table filter is now evaluatable - in all sub-joins
129: do {
130: Expression e = join.getJoinCondition();
131: if (e != null) {
132: e.setEvaluatable(this , true);
133: }
134: join = join.getJoin();
135: } while (join != null);
136: }
137:
138: public void setPlanItem(PlanItem item) {
139: setIndex(item.getIndex());
140: if (join != null) {
141: if (item.getJoinPlan() != null) {
142: join.setPlanItem(item.getJoinPlan());
143: }
144: }
145: }
146:
147: public void prepare() throws SQLException {
148: // forget all unused index conditions
149: for (int i = 0; i < indexConditions.size(); i++) {
150: IndexCondition condition = (IndexCondition) indexConditions
151: .get(i);
152: if (!condition.isAlwaysFalse()) {
153: Column col = condition.getColumn();
154: if (index.getColumnIndex(col) < 0) {
155: indexConditions.remove(i);
156: i--;
157: }
158: }
159: }
160: if (join != null) {
161: if (SysProperties.CHECK && join == this ) {
162: throw Message.getInternalError("self join");
163: }
164: join.prepare();
165: }
166: if (filterCondition != null) {
167: filterCondition = filterCondition.optimize(session);
168: }
169: if (joinCondition != null) {
170: joinCondition = joinCondition.optimize(session);
171: }
172: }
173:
174: public void startQuery(Session session) throws SQLException {
175: this .session = session;
176: scanCount = 0;
177: if (join != null) {
178: join.startQuery(session);
179: }
180: }
181:
182: public void reset() {
183: if (join != null) {
184: join.reset();
185: }
186: state = BEFORE_FIRST;
187: foundOne = false;
188: }
189:
190: public boolean next() throws SQLException {
191: boolean alwaysFalse = false;
192: if (state == AFTER_LAST) {
193: return false;
194: } else if (state == BEFORE_FIRST) {
195: SearchRow start = null, end = null;
196: for (int i = 0; i < indexConditions.size(); i++) {
197: IndexCondition condition = (IndexCondition) indexConditions
198: .get(i);
199: if (condition.isAlwaysFalse()) {
200: alwaysFalse = true;
201: break;
202: }
203: Column column = condition.getColumn();
204: int type = column.getType();
205: int id = column.getColumnId();
206: Value v = condition.getCurrentValue(session).convertTo(
207: type);
208: boolean isStart = condition.isStart(), isEnd = condition
209: .isEnd();
210: IndexColumn idxCol = indexColumns[id];
211: if (idxCol != null
212: && (idxCol.sortType & SortOrder.DESCENDING) != 0) {
213: // if the index column is sorted the other way, we swap end and start
214: // NULLS_FIRST / NULLS_LAST is not a problem, as nulls never match anyway
215: boolean temp = isStart;
216: isStart = isEnd;
217: isEnd = temp;
218: }
219: if (isStart) {
220: // TODO index: start.setExpression(id, bigger(start.getValue(id), e));
221: if (start == null) {
222: start = table.getTemplateRow();
223: }
224: start.setValue(id, v);
225: }
226: if (isEnd) {
227: // TODO index: end.setExpression(id, smaller(end.getExpression(id), e));
228: if (end == null) {
229: end = table.getTemplateRow();
230: }
231: end.setValue(id, v);
232: }
233: }
234: if (!alwaysFalse) {
235: cursor = index.find(session, start, end);
236: if (join != null) {
237: join.reset();
238: }
239: }
240: } else {
241: // state == FOUND || LAST_ROW
242: // the last row was ok - try next row of the join
243: if (join != null && join.next()) {
244: return true;
245: }
246: }
247: while (true) {
248: // go to the next row
249: if (state == NULL_ROW) {
250: break;
251: }
252: if (alwaysFalse) {
253: state = AFTER_LAST;
254: } else {
255: if ((++scanCount & 4095) == 0) {
256: checkTimeout();
257: }
258: if (cursor.next()) {
259: currentSearchRow = cursor.getSearchRow();
260: current = null;
261: // cursor.get();
262: state = FOUND;
263: } else {
264: state = AFTER_LAST;
265: }
266: }
267: // if no more rows found, try the null row (for outer joins only)
268: if (state == AFTER_LAST) {
269: if (outerJoin && !foundOne) {
270: state = NULL_ROW;
271: current = table.getNullRow();
272: currentSearchRow = current;
273: } else {
274: break;
275: }
276: }
277: if (!isOk(filterCondition)) {
278: continue;
279: }
280: boolean joinConditionOk = isOk(joinCondition);
281: if (state == FOUND) {
282: if (joinConditionOk) {
283: foundOne = true;
284: } else {
285: continue;
286: }
287: }
288: if (join != null) {
289: join.reset();
290: if (!join.next()) {
291: continue;
292: }
293: }
294: // check if it's ok
295: if (state == NULL_ROW || joinConditionOk) {
296: return true;
297: }
298: }
299: state = AFTER_LAST;
300: return false;
301: }
302:
303: private void checkTimeout() throws SQLException {
304: session.checkCancelled();
305: // System.out.println(this.alias+ " " + table.getName() + ": " + scanCount);
306: }
307:
308: private boolean isOk(Expression condition) throws SQLException {
309: if (condition == null) {
310: return true;
311: }
312: return Boolean.TRUE.equals(condition.getBooleanValue(session));
313: }
314:
315: public Row get() throws SQLException {
316: if (current == null && currentSearchRow != null) {
317: if (table.isClustered()) {
318: current = table.getTemplateRow();
319: for (int i = 0; i < currentSearchRow.getColumnCount(); i++) {
320: current.setValue(i, currentSearchRow.getValue(i));
321: }
322: } else {
323: current = cursor.get();
324: }
325: }
326: return current;
327: }
328:
329: public void set(Row current) {
330: // this is currently only used so that check constraints work - to set
331: // the current (new) row
332: this .current = current;
333: this .currentSearchRow = current;
334: }
335:
336: public String getTableAlias() {
337: if (alias != null) {
338: return alias;
339: }
340: return table.getName();
341: }
342:
343: public void addIndexCondition(IndexCondition condition) {
344: indexConditions.add(condition);
345: }
346:
347: public void addFilterCondition(Expression condition, boolean join) {
348: if (join) {
349: if (joinCondition == null) {
350: joinCondition = condition;
351: } else {
352: joinCondition = new ConditionAndOr(ConditionAndOr.AND,
353: joinCondition, condition);
354: }
355: } else {
356: if (filterCondition == null) {
357: filterCondition = condition;
358: } else {
359: filterCondition = new ConditionAndOr(
360: ConditionAndOr.AND, filterCondition, condition);
361: }
362: }
363: }
364:
365: public void addJoin(TableFilter filter, boolean outer, Expression on)
366: throws SQLException {
367: if (on != null) {
368: on.mapColumns(this , 0);
369: }
370: if (join == null) {
371: this .join = filter;
372: filter.outerJoin = outer;
373: if (on != null) {
374: filter.mapAndAddFilter(on);
375: }
376: } else {
377: join.addJoin(filter, outer, on);
378: }
379: }
380:
381: private void mapAndAddFilter(Expression on) throws SQLException {
382: on.mapColumns(this , 0);
383: addFilterCondition(on, true);
384: on.createIndexConditions(session, this );
385: if (join != null) {
386: join.mapAndAddFilter(on);
387: }
388: }
389:
390: public TableFilter getJoin() {
391: return join;
392: }
393:
394: public boolean isJoinOuter() {
395: return outerJoin;
396: }
397:
398: public String getPlanSQL(boolean join) {
399: StringBuffer buff = new StringBuffer();
400: if (join) {
401: if (outerJoin) {
402: buff.append("LEFT OUTER JOIN ");
403: } else {
404: buff.append("INNER JOIN ");
405: }
406: }
407: buff.append(table.getSQL());
408: if (alias != null) {
409: buff.append(' ');
410: buff.append(Parser.quoteIdentifier(alias));
411: }
412: buff.append(" /* ");
413: StringBuffer planBuff = new StringBuffer();
414: planBuff.append(index.getPlanSQL());
415: if (indexConditions.size() > 0) {
416: planBuff.append(": ");
417: for (int i = 0; i < indexConditions.size(); i++) {
418: IndexCondition condition = (IndexCondition) indexConditions
419: .get(i);
420: if (i > 0) {
421: planBuff.append(" AND ");
422: }
423: planBuff.append(condition.getSQL());
424: }
425: }
426: String plan = planBuff.toString();
427: plan = StringUtils.quoteRemarkSQL(plan);
428: buff.append(plan);
429: buff.append(" */");
430: if (joinCondition != null) {
431: buff.append(" ON ");
432: buff.append(StringUtils.unEnclose(joinCondition.getSQL()));
433: }
434: if (filterCondition != null) {
435: buff.append(" /* WHERE ");
436: String condition = StringUtils.unEnclose(filterCondition
437: .getSQL());
438: condition = StringUtils.quoteRemarkSQL(condition);
439: buff.append(condition);
440: buff.append(" */");
441: }
442: return buff.toString();
443: }
444:
445: public void removeUnusableIndexConditions() {
446: for (int i = 0; i < indexConditions.size(); i++) {
447: IndexCondition cond = (IndexCondition) indexConditions
448: .get(i);
449: if (!cond.isEvaluatable()) {
450: indexConditions.remove(i--);
451: }
452: }
453: }
454:
455: public Index getIndex() {
456: return index;
457: }
458:
459: public void setIndex(Index index) {
460: this .index = index;
461: Column[] columns = table.getColumns();
462: indexColumns = new IndexColumn[columns.length];
463: IndexColumn[] idxCols = index.getIndexColumns();
464: if (idxCols != null) {
465: for (int i = 0; i < columns.length; i++) {
466: int idx = index.getColumnIndex(columns[i]);
467: if (idx >= 0) {
468: indexColumns[i] = idxCols[idx];
469: }
470: }
471: }
472: }
473:
474: public void setUsed(boolean used) {
475: this .used = used;
476: }
477:
478: public boolean getUsed() {
479: return used;
480: }
481:
482: public void setSession(Session session) {
483: this .session = session;
484: }
485:
486: public void removeJoin() {
487: this .join = null;
488: }
489:
490: public Expression getJoinCondition() {
491: return joinCondition;
492: }
493:
494: public void removeJoinCondition() {
495: this .joinCondition = null;
496: }
497:
498: public Expression getFilterCondition() {
499: return filterCondition;
500: }
501:
502: public void removeFilterCondition() {
503: this .filterCondition = null;
504: }
505:
506: public void setFullCondition(Expression condition) {
507: this .fullCondition = condition;
508: if (join != null) {
509: join.setFullCondition(condition);
510: }
511: }
512:
513: public void optimizeFullCondition(boolean fromOuterJoin) {
514: if (fullCondition != null) {
515: fullCondition.addFilterConditions(this , fromOuterJoin
516: || outerJoin);
517: if (join != null) {
518: join.optimizeFullCondition(fromOuterJoin || outerJoin);
519: }
520: }
521: }
522:
523: public void setEvaluatable(TableFilter filter, boolean b) {
524: if (filterCondition != null) {
525: filterCondition.setEvaluatable(filter, b);
526: }
527: if (joinCondition != null) {
528: joinCondition.setEvaluatable(filter, b);
529: }
530: if (join != null) {
531: join.setEvaluatable(filter, b);
532: }
533: }
534:
535: public String getSchemaName() {
536: return table.getSchema().getName();
537: }
538:
539: public Column[] getColumns() {
540: return table.getColumns();
541: }
542:
543: public Column[] getSystemColumns() {
544: if (!session.getDatabase().getMode().systemColumns) {
545: return null;
546: }
547: Column[] sys = new Column[3];
548: sys[0] = new Column("oid", Value.INT);
549: sys[0].setTable(table, 0);
550: sys[1] = new Column("ctid", Value.STRING);
551: sys[1].setTable(table, 0);
552: sys[2] = new Column("CTID", Value.STRING);
553: sys[2].setTable(table, 0);
554: return sys;
555: }
556:
557: public Value getValue(Column column) throws SQLException {
558: if (currentSearchRow == null) {
559: return null;
560: }
561: int columnId = column.getColumnId();
562: if (current == null) {
563: Value v = currentSearchRow.getValue(columnId);
564: if (v != null) {
565: return v;
566: }
567: current = cursor.get();
568: }
569: return current.getValue(columnId);
570: }
571:
572: public TableFilter getTableFilter() {
573: return this ;
574: }
575:
576: public void setAlias(String alias) {
577: this.alias = alias;
578: }
579:
580: }
|