File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\command\dml\Select.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.command.dml;
8
9 import java.util.ArrayList;
10 import java.util.Arrays;
11 import java.util.HashMap;
12 import java.util.HashSet;
13 import org.h2.api.Trigger;
14 import org.h2.command.CommandInterface;
15 import org.h2.constant.ErrorCode;
16 import org.h2.constant.SysProperties;
17 import org.h2.engine.Constants;
18 import org.h2.engine.Database;
19 import org.h2.engine.Session;
20 import org.h2.expression.Comparison;
21 import org.h2.expression.ConditionAndOr;
22 import org.h2.expression.Expression;
23 import org.h2.expression.ExpressionColumn;
24 import org.h2.expression.ExpressionVisitor;
25 import org.h2.expression.Parameter;
26 import org.h2.expression.Wildcard;
27 import org.h2.index.Cursor;
28 import org.h2.index.Index;
29 import org.h2.index.IndexType;
30 import org.h2.message.DbException;
31 import org.h2.result.LocalResult;
32 import org.h2.result.ResultInterface;
33 import org.h2.result.ResultTarget;
34 import org.h2.result.Row;
35 import org.h2.result.SearchRow;
36 import org.h2.result.SortOrder;
37 import org.h2.table.Column;
38 import org.h2.table.ColumnResolver;
39 import org.h2.table.IndexColumn;
40 import org.h2.table.Table;
41 import org.h2.table.TableFilter;
42 import org.h2.util.New;
43 import org.h2.util.StatementBuilder;
44 import org.h2.util.StringUtils;
45 import org.h2.util.ValueHashMap;
46 import org.h2.value.Value;
47 import org.h2.value.ValueArray;
48 import org.h2.value.ValueNull;
49
50 /**
51 * This class represents a simple SELECT statement.
52 *
53 * For each select statement,
54 * visibleColumnCount &lt;= distinctColumnCount &lt;= expressionCount.
55 * The expression list count could include ORDER BY and GROUP BY expressions
56 * that are not in the select list.
57 *
58 * The call sequence is init(), mapColumns() if it's a subquery, prepare().
59 *
60 * @author Thomas Mueller
61 * @author Joel Turkel (Group sorted query)
62 */
63 public class Select extends Query {
64 private TableFilter topTableFilter;
65 private final ArrayList<TableFilter> filters = New.arrayList();
66 private final ArrayList<TableFilter> topFilters = New.arrayList();
67 private ArrayList<Expression> expressions;
68 private Expression[] expressionArray;
69 private Expression having;
70 private Expression condition;
71 private int visibleColumnCount, distinctColumnCount;
72 private ArrayList<SelectOrderBy> orderList;
73 private ArrayList<Expression> group;
74 private int[] groupIndex;
75 private boolean[] groupByExpression;
76 private HashMap<Expression, Object> currentGroup;
77 private int havingIndex;
78 private boolean isGroupQuery, isGroupSortedQuery;
79 private boolean isForUpdate, isForUpdateMvcc;
80 private double cost;
81 private boolean isQuickAggregateQuery, isDistinctQuery;
82 private boolean isPrepared, checkInit;
83 private boolean sortUsingIndex;
84 private SortOrder sort;
85 private int currentGroupRowId;
86
87 public Select(Session session) {
88 super(session);
89 }
90
91 /**
92 * Add a table to the query.
93 *
94 * @param filter the table to add
95 * @param isTop if the table can be the first table in the query plan
96 */
97 public void addTableFilter(TableFilter filter, boolean isTop) {
98 // Oracle doesn't check on duplicate aliases
99 // String alias = filter.getAlias();
100 // if(filterNames.contains(alias)) {
101 // throw Message.getSQLException(
102 // ErrorCode.DUPLICATE_TABLE_ALIAS, alias);
103 // }
104 // filterNames.add(alias);
105 filters.add(filter);
106 if (isTop) {
107 topFilters.add(filter);
108 }
109 }
110
111 public ArrayList<TableFilter> getTopFilters() {
112 return topFilters;
113 }
114
115 public void setExpressions(ArrayList<Expression> expressions) {
116 this.expressions = expressions;
117 }
118
119 /**
120 * Called if this query contains aggregate functions.
121 */
122 public void setGroupQuery() {
123 isGroupQuery = true;
124 }
125
126 public void setGroupBy(ArrayList<Expression> group) {
127 this.group = group;
128 }
129
130 public HashMap<Expression, Object> getCurrentGroup() {
131 return currentGroup;
132 }
133
134 public int getCurrentGroupRowId() {
135 return currentGroupRowId;
136 }
137
138 public void setOrder(ArrayList<SelectOrderBy> order) {
139 orderList = order;
140 }
141
142 /**
143 * Add a condition to the list of conditions.
144 *
145 * @param cond the condition to add
146 */
147 public void addCondition(Expression cond) {
148 if (condition == null) {
149 condition = cond;
150 } else {
151 condition = new ConditionAndOr(ConditionAndOr.AND, cond, condition);
152 }
153 }
154
155 private void queryGroupSorted(int columnCount, ResultTarget result) {
156 int rowNumber = 0;
157 setCurrentRowNumber(0);
158 Value[] previousKeyValues = null;
159 while (topTableFilter.next()) {
160 setCurrentRowNumber(rowNumber + 1);
161 if (condition == null || Boolean.TRUE.equals(condition.getBooleanValue(session))) {
162 rowNumber++;
163 Value[] keyValues = new Value[groupIndex.length];
164 // update group
165 for (int i = 0; i < groupIndex.length; i++) {
166 int idx = groupIndex[i];
167 Expression expr = expressions.get(idx);
168 keyValues[i] = expr.getValue(session);
169 }
170
171 if (previousKeyValues == null) {
172 previousKeyValues = keyValues;
173 currentGroup = New.hashMap();
174 } else if (!Arrays.equals(previousKeyValues, keyValues)) {
175 addGroupSortedRow(previousKeyValues, columnCount, result);
176 previousKeyValues = keyValues;
177 currentGroup = New.hashMap();
178 }
179 currentGroupRowId++;
180
181 for (int i = 0; i < columnCount; i++) {
182 if (groupByExpression == null || !groupByExpression[i]) {
183 Expression expr = expressions.get(i);
184 expr.updateAggregate(session);
185 }
186 }
187 }
188 }
189 if (previousKeyValues != null) {
190 addGroupSortedRow(previousKeyValues, columnCount, result);
191 }
192 }
193
194 private void addGroupSortedRow(Value[] keyValues, int columnCount, ResultTarget result) {
195 Value[] row = new Value[columnCount];
196 for (int j = 0; groupIndex != null && j < groupIndex.length; j++) {
197 row[groupIndex[j]] = keyValues[j];
198 }
199 for (int j = 0; j < columnCount; j++) {
200 if (groupByExpression != null && groupByExpression[j]) {
201 continue;
202 }
203 Expression expr = expressions.get(j);
204 row[j] = expr.getValue(session);
205 }
206 if (isHavingNullOrFalse(row)) {
207 return;
208 }
209 row = keepOnlyDistinct(row, columnCount);
210 result.addRow(row);
211 }
212
213 private Value[] keepOnlyDistinct(Value[] row, int columnCount) {
214 if (columnCount == distinctColumnCount) {
215 return row;
216 }
217 // remove columns so that 'distinct' can filter duplicate rows
218 Value[] r2 = new Value[distinctColumnCount];
219 System.arraycopy(row, 0, r2, 0, distinctColumnCount);
220 return r2;
221 }
222
223 private boolean isHavingNullOrFalse(Value[] row) {
224 if (havingIndex >= 0) {
225 Value v = row[havingIndex];
226 if (v == ValueNull.INSTANCE) {
227 return true;
228 }
229 if (!Boolean.TRUE.equals(v.getBoolean())) {
230 return true;
231 }
232 }
233 return false;
234 }
235
236 private Index getGroupSortedIndex() {
237 if (groupIndex == null || groupByExpression == null) {
238 return null;
239 }
240 ArrayList<Index> indexes = topTableFilter.getTable().getIndexes();
241 if (indexes != null) {
242 for (int i = 0, size = indexes.size(); i < size; i++) {
243 Index index = indexes.get(i);
244 if (index.getIndexType().isScan()) {
245 continue;
246 }
247 if (isGroupSortedIndex(topTableFilter, index)) {
248 return index;
249 }
250 }
251 }
252 return null;
253 }
254
255 private boolean isGroupSortedIndex(TableFilter tableFilter, Index index) {
256 // check that all the GROUP BY expressions are part of the index
257 Column[] indexColumns = index.getColumns();
258 // also check that the first columns in the index are grouped
259 boolean[] grouped = new boolean[indexColumns.length];
260 outerLoop:
261 for (int i = 0, size = expressions.size(); i < size; i++) {
262 if (!groupByExpression[i]) {
263 continue;
264 }
265 Expression expr = expressions.get(i).getNonAliasExpression();
266 if (!(expr instanceof ExpressionColumn)) {
267 return false;
268 }
269 ExpressionColumn exprCol = (ExpressionColumn) expr;
270 for (int j = 0; j < indexColumns.length; ++j) {
271 if (tableFilter == exprCol.getTableFilter()) {
272 if (indexColumns[j].equals(exprCol.getColumn())) {
273 grouped[j] = true;
274 continue outerLoop;
275 }
276 }
277 }
278 // We didn't find a matching index column
279 // for one group by expression
280 return false;
281 }
282 // check that the first columns in the index are grouped
283 // good: index(a, b, c); group by b, a
284 // bad: index(a, b, c); group by a, c
285 for (int i = 1; i < grouped.length; i++) {
286 if (!grouped[i - 1] && grouped[i]) {
287 return false;
288 }
289 }
290 return true;
291 }
292
293 private int getGroupByExpressionCount() {
294 if (groupByExpression == null) {
295 return 0;
296 }
297 int count = 0;
298 for (boolean b : groupByExpression) {
299 if (b) {
300 ++count;
301 }
302 }
303 return count;
304 }
305
306 private void queryGroup(int columnCount, LocalResult result) {
307 ValueHashMap<HashMap<Expression, Object>> groups = ValueHashMap.newInstance();
308 int rowNumber = 0;
309 setCurrentRowNumber(0);
310 ValueArray defaultGroup = ValueArray.get(new Value[0]);
311 while (topTableFilter.next()) {
312 setCurrentRowNumber(rowNumber + 1);
313 if (condition == null || Boolean.TRUE.equals(condition.getBooleanValue(session))) {
314 Value key;
315 rowNumber++;
316 if (groupIndex == null) {
317 key = defaultGroup;
318 } else {
319 Value[] keyValues = new Value[groupIndex.length];
320 // update group
321 for (int i = 0; i < groupIndex.length; i++) {
322 int idx = groupIndex[i];
323 Expression expr = expressions.get(idx);
324 keyValues[i] = expr.getValue(session);
325 }
326 key = ValueArray.get(keyValues);
327 }
328 HashMap<Expression, Object> values = groups.get(key);
329 if (values == null) {
330 values = new HashMap<Expression, Object>();
331 groups.put(key, values);
332 }
333 currentGroup = values;
334 currentGroupRowId++;
335 int len = columnCount;
336 for (int i = 0; i < len; i++) {
337 if (groupByExpression == null || !groupByExpression[i]) {
338 Expression expr = expressions.get(i);
339 expr.updateAggregate(session);
340 }
341 }
342 if (sampleSize > 0 && rowNumber >= sampleSize) {
343 break;
344 }
345 }
346 }
347 if (groupIndex == null && groups.size() == 0) {
348 groups.put(defaultGroup, new HashMap<Expression, Object>());
349 }
350 ArrayList<Value> keys = groups.keys();
351 for (Value v : keys) {
352 ValueArray key = (ValueArray) v;
353 currentGroup = groups.get(key);
354 Value[] keyValues = key.getList();
355 Value[] row = new Value[columnCount];
356 for (int j = 0; groupIndex != null && j < groupIndex.length; j++) {
357 row[groupIndex[j]] = keyValues[j];
358 }
359 for (int j = 0; j < columnCount; j++) {
360 if (groupByExpression != null && groupByExpression[j]) {
361 continue;
362 }
363 Expression expr = expressions.get(j);
364 row[j] = expr.getValue(session);
365 }
366 if (isHavingNullOrFalse(row)) {
367 continue;
368 }
369 row = keepOnlyDistinct(row, columnCount);
370 result.addRow(row);
371 }
372 }
373
374 /**
375 * Get the index that matches the ORDER BY list, if one exists. This is to
376 * avoid running a separate ORDER BY if an index can be used. This is
377 * specially important for large result sets, if only the first few rows are
378 * important (LIMIT is used)
379 *
380 * @return the index if one is found
381 */
382 private Index getSortIndex() {
383 if (sort == null) {
384 return null;
385 }
386 ArrayList<Column> sortColumns = New.arrayList();
387 for (int idx : sort.getIndexes()) {
388 if (idx < 0 || idx >= expressions.size()) {
389 throw DbException.getInvalidValueException("ORDER BY", idx + 1);
390 }
391 Expression expr = expressions.get(idx);
392 expr = expr.getNonAliasExpression();
393 if (expr.isConstant()) {
394 continue;
395 }
396 if (!(expr instanceof ExpressionColumn)) {
397 return null;
398 }
399 ExpressionColumn exprCol = (ExpressionColumn) expr;
400 if (exprCol.getTableFilter() != topTableFilter) {
401 return null;
402 }
403 sortColumns.add(exprCol.getColumn());
404 }
405 Column[] sortCols = sortColumns.toArray(new Column[sortColumns.size()]);
406 int[] sortTypes = sort.getSortTypes();
407 if (sortCols.length == 0) {
408 // sort just on constants - can use scan index
409 return topTableFilter.getTable().getScanIndex(session);
410 }
411 ArrayList<Index> list = topTableFilter.getTable().getIndexes();
412 if (list != null) {
413 for (int i = 0, size = list.size(); i < size; i++) {
414 Index index = list.get(i);
415 if (index.getCreateSQL() == null) {
416 // can't use the scan index
417 continue;
418 }
419 if (index.getIndexType().isHash()) {
420 continue;
421 }
422 IndexColumn[] indexCols = index.getIndexColumns();
423 if (indexCols.length < sortCols.length) {
424 continue;
425 }
426 boolean ok = true;
427 for (int j = 0; j < sortCols.length; j++) {
428 // the index and the sort order must start
429 // with the exact same columns
430 IndexColumn idxCol = indexCols[j];
431 Column sortCol = sortCols[j];
432 if (idxCol.column != sortCol) {
433 ok = false;
434 break;
435 }
436 if (idxCol.sortType != sortTypes[j]) {
437 // NULL FIRST for ascending and NULLS LAST
438 // for descending would actually match the default
439 ok = false;
440 break;
441 }
442 }
443 if (ok) {
444 return index;
445 }
446 }
447 }
448 if (sortCols.length == 1 && sortCols[0].getColumnId() == -1) {
449 // special case: order by _ROWID_
450 Index index = topTableFilter.getTable().getScanIndex(session);
451 if (index.isRowIdIndex()) {
452 return index;
453 }
454 }
455 return null;
456 }
457
458 private void queryDistinct(ResultTarget result, long limitRows) {
459 // limitRows must be long, otherwise we get an int overflow
460 // if limitRows is at or near Integer.MAX_VALUE
461 // limitRows is never 0 here
462 if (limitRows > 0 && offsetExpr != null) {
463 int offset = offsetExpr.getValue(session).getInt();
464 if (offset > 0) {
465 limitRows += offset;
466 }
467 }
468 int rowNumber = 0;
469 setCurrentRowNumber(0);
470 Index index = topTableFilter.getIndex();
471 SearchRow first = null;
472 int columnIndex = index.getColumns()[0].getColumnId();
473 while (true) {
474 setCurrentRowNumber(rowNumber + 1);
475 Cursor cursor = index.findNext(session, first, null);
476 if (!cursor.next()) {
477 break;
478 }
479 SearchRow found = cursor.getSearchRow();
480 Value value = found.getValue(columnIndex);
481 if (first == null) {
482 first = topTableFilter.getTable().getTemplateSimpleRow(true);
483 }
484 first.setValue(columnIndex, value);
485 Value[] row = { value };
486 result.addRow(row);
487 rowNumber++;
488 if ((sort == null || sortUsingIndex) && limitRows > 0 && rowNumber >= limitRows) {
489 break;
490 }
491 if (sampleSize > 0 && rowNumber >= sampleSize) {
492 break;
493 }
494 }
495 }
496
497 private void queryFlat(int columnCount, ResultTarget result, long limitRows) {
498 // limitRows must be long, otherwise we get an int overflow
499 // if limitRows is at or near Integer.MAX_VALUE
500 // limitRows is never 0 here
501 if (limitRows > 0 && offsetExpr != null) {
502 int offset = offsetExpr.getValue(session).getInt();
503 if (offset > 0) {
504 limitRows += offset;
505 }
506 }
507 int rowNumber = 0;
508 setCurrentRowNumber(0);
509 ArrayList<Row> forUpdateRows = null;
510 if (isForUpdateMvcc) {
511 forUpdateRows = New.arrayList();
512 }
513 while (topTableFilter.next()) {
514 setCurrentRowNumber(rowNumber + 1);
515 if (condition == null || Boolean.TRUE.equals(condition.getBooleanValue(session))) {
516 Value[] row = new Value[columnCount];
517 for (int i = 0; i < columnCount; i++) {
518 Expression expr = expressions.get(i);
519 row[i] = expr.getValue(session);
520 }
521 if (isForUpdateMvcc) {
522 topTableFilter.lockRowAdd(forUpdateRows);
523 }
524 result.addRow(row);
525 rowNumber++;
526 if ((sort == null || sortUsingIndex) && limitRows > 0 && result.getRowCount() >= limitRows) {
527 break;
528 }
529 if (sampleSize > 0 && rowNumber >= sampleSize) {
530 break;
531 }
532 }
533 }
534 if (isForUpdateMvcc) {
535 topTableFilter.lockRows(forUpdateRows);
536 }
537 }
538
539 private void queryQuick(int columnCount, ResultTarget result) {
540 Value[] row = new Value[columnCount];
541 for (int i = 0; i < columnCount; i++) {
542 Expression expr = expressions.get(i);
543 row[i] = expr.getValue(session);
544 }
545 result.addRow(row);
546 }
547
548 public ResultInterface queryMeta() {
549 LocalResult result = new LocalResult(session, expressionArray, visibleColumnCount);
550 result.done();
551 return result;
552 }
553
554 protected LocalResult queryWithoutCache(int maxRows, ResultTarget target) {
555 int limitRows = maxRows == 0 ? -1 : maxRows;
556 if (limitExpr != null) {
557 Value v = limitExpr.getValue(session);
558 int l = v == ValueNull.INSTANCE ? -1 : v.getInt();
559 if (limitRows < 0) {
560 limitRows = l;
561 } else if (l >= 0) {
562 limitRows = Math.min(l, limitRows);
563 }
564 }
565 int columnCount = expressions.size();
566 LocalResult result = null;
567 if (target == null || !session.getDatabase().getSettings().optimizeInsertFromSelect) {
568 result = createLocalResult(result);
569 }
570 if (sort != null && (!sortUsingIndex || distinct)) {
571 result = createLocalResult(result);
572 result.setSortOrder(sort);
573 }
574 if (distinct && !isDistinctQuery) {
575 result = createLocalResult(result);
576 result.setDistinct();
577 }
578 if (randomAccessResult) {
579 result = createLocalResult(result);
580 result.setRandomAccess();
581 }
582 if (isGroupQuery && !isGroupSortedQuery) {
583 result = createLocalResult(result);
584 }
585 if (limitRows >= 0 || offsetExpr != null) {
586 result = createLocalResult(result);
587 }
588 topTableFilter.startQuery(session);
589 topTableFilter.reset();
590 boolean exclusive = isForUpdate && !isForUpdateMvcc;
591 if (isForUpdateMvcc) {
592 if (isGroupQuery) {
593 throw DbException.getUnsupportedException("FOR UPDATE && GROUP");
594 } else if (distinct) {
595 throw DbException.getUnsupportedException("FOR UPDATE && DISTINCT");
596 } else if (isQuickAggregateQuery) {
597 throw DbException.getUnsupportedException("FOR UPDATE && AGGREGATE");
598 } else if (topTableFilter.getJoin() != null) {
599 throw DbException.getUnsupportedException("FOR UPDATE && JOIN");
600 } else if (topTableFilter.getJoin() != null) {
601 throw DbException.getUnsupportedException("FOR UPDATE && JOIN");
602 }
603 }
604 topTableFilter.lock(session, exclusive, exclusive);
605 ResultTarget to = result != null ? result : target;
606 if (limitRows != 0) {
607 if (isQuickAggregateQuery) {
608 queryQuick(columnCount, to);
609 } else if (isGroupQuery) {
610 if (isGroupSortedQuery) {
611 queryGroupSorted(columnCount, to);
612 } else {
613 queryGroup(columnCount, result);
614 }
615 } else if (isDistinctQuery) {
616 queryDistinct(to, limitRows);
617 } else {
618 queryFlat(columnCount, to, limitRows);
619 }
620 }
621 if (offsetExpr != null) {
622 result.setOffset(offsetExpr.getValue(session).getInt());
623 }
624 if (limitRows >= 0) {
625 result.setLimit(limitRows);
626 }
627 if (result != null) {
628 result.done();
629 if (target != null) {
630 while (result.next()) {
631 target.addRow(result.currentRow());
632 }
633 result.close();
634 return null;
635 }
636 return result;
637 }
638 return null;
639 }
640
641 private LocalResult createLocalResult(LocalResult old) {
642 return old != null ? old : new LocalResult(session, expressionArray, visibleColumnCount);
643 }
644
645 private void expandColumnList() {
646 Database db = session.getDatabase();
647
648 // the expressions may change within the loop
649 for (int i = 0; i < expressions.size(); i++) {
650 Expression expr = expressions.get(i);
651 if (!expr.isWildcard()) {
652 continue;
653 }
654 String schemaName = expr.getSchemaName();
655 String tableAlias = expr.getTableAlias();
656 if (tableAlias == null) {
657 int temp = i;
658 expressions.remove(i);
659 for (TableFilter filter : filters) {
660 Wildcard c2 = new Wildcard(filter.getTable().getSchema().getName(), filter.getTableAlias());
661 expressions.add(i++, c2);
662 }
663 i = temp - 1;
664 } else {
665 TableFilter filter = null;
666 for (TableFilter f : filters) {
667 if (db.equalsIdentifiers(tableAlias, f.getTableAlias())) {
668 if (schemaName == null || db.equalsIdentifiers(schemaName, f.getSchemaName())) {
669 filter = f;
670 break;
671 }
672 }
673 }
674 if (filter == null) {
675 throw DbException.get(ErrorCode.TABLE_OR_VIEW_NOT_FOUND_1, tableAlias);
676 }
677 Table t = filter.getTable();
678 String alias = filter.getTableAlias();
679 expressions.remove(i);
680 Column[] columns = t.getColumns();
681 for (Column c : columns) {
682 if (filter.isNaturalJoinColumn(c)) {
683 continue;
684 }
685 ExpressionColumn ec = new ExpressionColumn(session.getDatabase(), null, alias, c.getName());
686 expressions.add(i++, ec);
687 }
688 i--;
689 }
690 }
691 }
692
693 public void init() {
694 if (SysProperties.CHECK && checkInit) {
695 DbException.throwInternalError();
696 }
697 expandColumnList();
698 visibleColumnCount = expressions.size();
699 ArrayList<String> expressionSQL;
700 if (orderList != null || group != null) {
701 expressionSQL = New.arrayList();
702 for (int i = 0; i < visibleColumnCount; i++) {
703 Expression expr = expressions.get(i);
704 expr = expr.getNonAliasExpression();
705 String sql = expr.getSQL();
706 expressionSQL.add(sql);
707 }
708 } else {
709 expressionSQL = null;
710 }
711 if (orderList != null) {
712 initOrder(session, expressions, expressionSQL, orderList, visibleColumnCount, distinct, filters);
713 }
714 distinctColumnCount = expressions.size();
715 if (having != null) {
716 expressions.add(having);
717 havingIndex = expressions.size() - 1;
718 having = null;
719 } else {
720 havingIndex = -1;
721 }
722
723 Database db = session.getDatabase();
724
725 // first the select list (visible columns),
726 // then 'ORDER BY' expressions,
727 // then 'HAVING' expressions,
728 // and 'GROUP BY' expressions at the end
729 if (group != null) {
730 int size = group.size();
731 int expSize = expressionSQL.size();
732 groupIndex = new int[size];
733 for (int i = 0; i < size; i++) {
734 Expression expr = group.get(i);
735 String sql = expr.getSQL();
736 int found = -1;
737 for (int j = 0; j < expSize; j++) {
738 String s2 = expressionSQL.get(j);
739 if (db.equalsIdentifiers(s2, sql)) {
740 found = j;
741 break;
742 }
743 }
744 if (found < 0) {
745 // special case: GROUP BY a column alias
746 for (int j = 0; j < expSize; j++) {
747 Expression e = expressions.get(j);
748 if (db.equalsIdentifiers(sql, e.getAlias())) {
749 found = j;
750 break;
751 }
752 }
753 }
754 if (found < 0) {
755 int index = expressions.size();
756 groupIndex[i] = index;
757 expressions.add(expr);
758 } else {
759 groupIndex[i] = found;
760 }
761 }
762 groupByExpression = new boolean[expressions.size()];
763 for (int gi : groupIndex) {
764 groupByExpression[gi] = true;
765 }
766 group = null;
767 }
768 // map columns in select list and condition
769 for (TableFilter f : filters) {
770 for (Expression expr : expressions) {
771 expr.mapColumns(f, 0);
772 }
773 if (condition != null) {
774 condition.mapColumns(f, 0);
775 }
776 }
777 if (havingIndex >= 0) {
778 Expression expr = expressions.get(havingIndex);
779 SelectListColumnResolver res = new SelectListColumnResolver(this);
780 expr.mapColumns(res, 0);
781 }
782 checkInit = true;
783 }
784
785 public void prepare() {
786 if (isPrepared) {
787 // sometimes a subquery is prepared twice (CREATE TABLE AS SELECT)
788 return;
789 }
790 if (SysProperties.CHECK && !checkInit) {
791 DbException.throwInternalError("not initialized");
792 }
793 if (orderList != null) {
794 sort = prepareOrder(orderList, expressions.size());
795 orderList = null;
796 }
797 for (int i = 0; i < expressions.size(); i++) {
798 Expression e = expressions.get(i);
799 expressions.set(i, e.optimize(session));
800 }
801 if (condition != null) {
802 condition = condition.optimize(session);
803 for (TableFilter f : filters) {
804 // outer joins: must not add index conditions such as
805 // "c is null" - example:
806 // create table parent(p int primary key) as select 1;
807 // create table child(c int primary key, pc int);
808 // insert into child values(2, 1);
809 // select p, c from parent
810 // left outer join child on p = pc where c is null;
811 if (!f.isJoinOuter() && !f.isJoinOuterIndirect()) {
812 condition.createIndexConditions(session, f);
813 }
814 }
815 }
816 if (isGroupQuery && groupIndex == null && havingIndex < 0 && filters.size() == 1) {
817 if (condition == null) {
818 Table t = filters.get(0).getTable();
819 ExpressionVisitor optimizable = ExpressionVisitor.getOptimizableVisitor(t);
820 isQuickAggregateQuery = isEverything(optimizable);
821 }
822 }
823 cost = preparePlan();
824 if (distinct && session.getDatabase().getSettings().optimizeDistinct &&
825 !isGroupQuery && filters.size() == 1 &&
826 expressions.size() == 1 && condition == null) {
827 Expression expr = expressions.get(0);
828 expr = expr.getNonAliasExpression();
829 if (expr instanceof ExpressionColumn) {
830 Column column = ((ExpressionColumn) expr).getColumn();
831 int selectivity = column.getSelectivity();
832 Index columnIndex = topTableFilter.getTable().getIndexForColumn(column);
833 if (columnIndex != null && selectivity != Constants.SELECTIVITY_DEFAULT && selectivity < 20) {
834 // the first column must be ascending
835 boolean ascending = columnIndex.getIndexColumns()[0].sortType == SortOrder.ASCENDING;
836 Index current = topTableFilter.getIndex();
837 // if another index is faster
838 if (columnIndex.canFindNext() && ascending &&
839 (current == null || current.getIndexType().isScan() || columnIndex == current)) {
840 IndexType type = columnIndex.getIndexType();
841 // hash indexes don't work, and unique single column indexes don't work
842 if (!type.isHash() && (!type.isUnique() || columnIndex.getColumns().length > 1)) {
843 topTableFilter.setIndex(columnIndex);
844 isDistinctQuery = true;
845 }
846 }
847 }
848 }
849 }
850 if (sort != null && !isQuickAggregateQuery && !isGroupQuery) {
851 Index index = getSortIndex();
852 if (index != null) {
853 Index current = topTableFilter.getIndex();
854 if (current.getIndexType().isScan() || current == index) {
855 topTableFilter.setIndex(index);
856 if (!topTableFilter.hasInComparisons()) {
857 // in(select ...) and in(1,2,3) my return the key in another order
858 sortUsingIndex = true;
859 }
860 } else if (index.getIndexColumns().length >= current.getIndexColumns().length) {
861 IndexColumn[] sortColumns = index.getIndexColumns();
862 IndexColumn[] currentColumns = current.getIndexColumns();
863 boolean swapIndex = false;
864 for (int i = 0; i < currentColumns.length; i++) {
865 if (sortColumns[i].column != currentColumns[i].column) {
866 swapIndex = false;
867 break;
868 }
869 if (sortColumns[i].sortType != currentColumns[i].sortType) {
870 swapIndex = true;
871 }
872 }
873 if (swapIndex) {
874 topTableFilter.setIndex(index);
875 sortUsingIndex = true;
876 }
877 }
878 }
879 }
880 if (!isQuickAggregateQuery && isGroupQuery && getGroupByExpressionCount() > 0) {
881 Index index = getGroupSortedIndex();
882 Index current = topTableFilter.getIndex();
883 if (index != null && (current.getIndexType().isScan() || current == index)) {
884 topTableFilter.setIndex(index);
885 isGroupSortedQuery = true;
886 }
887 }
888 expressionArray = new Expression[expressions.size()];
889 expressions.toArray(expressionArray);
890 isPrepared = true;
891 }
892
893 public double getCost() {
894 return cost;
895 }
896
897 public HashSet<Table> getTables() {
898 HashSet<Table> set = New.hashSet();
899 for (TableFilter filter : filters) {
900 set.add(filter.getTable());
901 }
902 return set;
903 }
904
905 public void fireBeforeSelectTriggers() {
906 for (int i = 0, size = filters.size(); i < size; i++) {
907 TableFilter filter = filters.get(i);
908 filter.getTable().fire(session, Trigger.SELECT, true);
909 }
910 }
911
912 private double preparePlan() {
913 TableFilter[] topArray = topFilters.toArray(new TableFilter[topFilters.size()]);
914 for (TableFilter t : topArray) {
915 t.setFullCondition(condition);
916 }
917
918 Optimizer optimizer = new Optimizer(topArray, condition, session);
919 optimizer.optimize();
920 topTableFilter = optimizer.getTopFilter();
921 double planCost = optimizer.getCost();
922
923 setEvaluatableRecursive(topTableFilter);
924
925 topTableFilter.prepare();
926 return planCost;
927 }
928
929 private void setEvaluatableRecursive(TableFilter f) {
930 for (; f != null; f = f.getJoin()) {
931 f.setEvaluatable(f, true);
932 if (condition != null) {
933 condition.setEvaluatable(f, true);
934 }
935 TableFilter n = f.getNestedJoin();
936 if (n != null) {
937 setEvaluatableRecursive(n);
938 }
939 Expression on = f.getJoinCondition();
940 if (on != null) {
941 if (!on.isEverything(ExpressionVisitor.EVALUATABLE_VISITOR)) {
942 if (session.getDatabase().getSettings().nestedJoins) {
943 // need to check that all added are bound to a table
944 on = on.optimize(session);
945 if (!f.isJoinOuter() && !f.isJoinOuterIndirect()) {
946 f.removeJoinCondition();
947 addCondition(on);
948 }
949 } else {
950 if (f.isJoinOuter()) {
951 // this will check if all columns exist - it may or may not throw an exception
952 on = on.optimize(session);
953 // it is not supported even if the columns exist
954 throw DbException.get(ErrorCode.UNSUPPORTED_OUTER_JOIN_CONDITION_1, on.getSQL());
955 }
956 f.removeJoinCondition();
957 // need to check that all added are bound to a table
958 on = on.optimize(session);
959 addCondition(on);
960 }
961 }
962 }
963 on = f.getFilterCondition();
964 if (on != null) {
965 if (!on.isEverything(ExpressionVisitor.EVALUATABLE_VISITOR)) {
966 f.removeFilterCondition();
967 addCondition(on);
968 }
969 }
970 // this is only important for subqueries, so they know
971 // the result columns are evaluatable
972 for (Expression e : expressions) {
973 e.setEvaluatable(f, true);
974 }
975 }
976 }
977
978 public String getPlanSQL() {
979 // can not use the field sqlStatement because the parameter
980 // indexes may be incorrect: ? may be in fact ?2 for a subquery
981 // but indexes may be set manually as well
982 Expression[] exprList = expressions.toArray(new Expression[expressions.size()]);
983 StatementBuilder buff = new StatementBuilder("SELECT");
984 if (distinct) {
985 buff.append(" DISTINCT");
986 }
987 for (int i = 0; i < visibleColumnCount; i++) {
988 buff.appendExceptFirst(",");
989 buff.append('\n');
990 buff.append(StringUtils.indent(exprList[i].getSQL(), 4, false));
991 }
992 buff.append("\nFROM ");
993 TableFilter filter = topTableFilter;
994 if (filter != null) {
995 buff.resetCount();
996 int i = 0;
997 do {
998 buff.appendExceptFirst("\n");
999 buff.append(filter.getPlanSQL(i++ > 0));
1000 filter = filter.getJoin();
1001 } while (filter != null);
1002 } else {
1003 buff.resetCount();
1004 int i = 0;
1005 for (TableFilter f : topFilters) {
1006 do {
1007 buff.appendExceptFirst("\n");
1008 buff.append(f.getPlanSQL(i++ > 0));
1009 f = f.getJoin();
1010 } while (f != null);
1011 }
1012 }
1013 if (condition != null) {
1014 buff.append("\nWHERE ").append(StringUtils.unEnclose(condition.getSQL()));
1015 }
1016 if (groupIndex != null) {
1017 buff.append("\nGROUP BY ");
1018 buff.resetCount();
1019 for (int gi : groupIndex) {
1020 Expression g = exprList[gi];
1021 g = g.getNonAliasExpression();
1022 buff.appendExceptFirst(", ");
1023 buff.append(StringUtils.unEnclose(g.getSQL()));
1024 }
1025 }
1026 if (group != null) {
1027 buff.append("\nGROUP BY ");
1028 buff.resetCount();
1029 for (Expression g : group) {
1030 buff.appendExceptFirst(", ");
1031 buff.append(StringUtils.unEnclose(g.getSQL()));
1032 }
1033 }
1034 if (having != null) {
1035 // could be set in addGlobalCondition
1036 // in this case the query is not run directly, just getPlanSQL is
1037 // called
1038 Expression h = having;
1039 buff.append("\nHAVING ").append(StringUtils.unEnclose(h.getSQL()));
1040 } else if (havingIndex >= 0) {
1041 Expression h = exprList[havingIndex];
1042 buff.append("\nHAVING ").append(StringUtils.unEnclose(h.getSQL()));
1043 }
1044 if (sort != null) {
1045 buff.append("\nORDER BY ").append(sort.getSQL(exprList, visibleColumnCount));
1046 }
1047 if (orderList != null) {
1048 buff.append("\nORDER BY ");
1049 buff.resetCount();
1050 for (SelectOrderBy o : orderList) {
1051 buff.appendExceptFirst(", ");
1052 buff.append(StringUtils.unEnclose(o.getSQL()));
1053 }
1054 }
1055 if (limitExpr != null) {
1056 buff.append("\nLIMIT ").append(StringUtils.unEnclose(limitExpr.getSQL()));
1057 if (offsetExpr != null) {
1058 buff.append(" OFFSET ").append(StringUtils.unEnclose(offsetExpr.getSQL()));
1059 }
1060 }
1061 if (sampleSize != 0) {
1062 buff.append("\nSAMPLE_SIZE ").append(sampleSize);
1063 }
1064 if (isForUpdate) {
1065 buff.append("\nFOR UPDATE");
1066 }
1067 if (isQuickAggregateQuery) {
1068 buff.append("\n/* direct lookup */");
1069 }
1070 if (isDistinctQuery) {
1071 buff.append("\n/* distinct */");
1072 }
1073 if (sortUsingIndex) {
1074 buff.append("\n/* index sorted */");
1075 }
1076 if (isGroupQuery) {
1077 if (isGroupSortedQuery) {
1078 buff.append("\n/* group sorted */");
1079 }
1080 }
1081 // buff.append("\n/* cost: " + cost + " */");
1082 return buff.toString();
1083 }
1084
1085 public void setHaving(Expression having) {
1086 this.having = having;
1087 }
1088
1089 public int getColumnCount() {
1090 return visibleColumnCount;
1091 }
1092
1093 public TableFilter getTopTableFilter() {
1094 return topTableFilter;
1095 }
1096
1097 public ArrayList<Expression> getExpressions() {
1098 return expressions;
1099 }
1100
1101 public void setForUpdate(boolean b) {
1102 this.isForUpdate = b;
1103 if (session.getDatabase().getSettings().selectForUpdateMvcc && session.getDatabase().isMultiVersion()) {
1104 isForUpdateMvcc = b;
1105 }
1106 }
1107
1108 public void mapColumns(ColumnResolver resolver, int level) {
1109 for (Expression e : expressions) {
1110 e.mapColumns(resolver, level);
1111 }
1112 if (condition != null) {
1113 condition.mapColumns(resolver, level);
1114 }
1115 }
1116
1117 public void setEvaluatable(TableFilter tableFilter, boolean b) {
1118 for (Expression e : expressions) {
1119 e.setEvaluatable(tableFilter, b);
1120 }
1121 if (condition != null) {
1122 condition.setEvaluatable(tableFilter, b);
1123 }
1124 }
1125
1126 /**
1127 * Check if this is an aggregate query with direct lookup, for example a
1128 * query of the type SELECT COUNT(*) FROM TEST or
1129 * SELECT MAX(ID) FROM TEST.
1130 *
1131 * @return true if a direct lookup is possible
1132 */
1133 public boolean isQuickAggregateQuery() {
1134 return isQuickAggregateQuery;
1135 }
1136
1137 public void addGlobalCondition(Parameter param, int columnId, int comparisonType) {
1138 addParameter(param);
1139 Expression comp;
1140 Expression col = expressions.get(columnId);
1141 col = col.getNonAliasExpression();
1142 if (col.isEverything(ExpressionVisitor.QUERY_COMPARABLE_VISITOR)) {
1143 comp = new Comparison(session, comparisonType, col, param);
1144 } else {
1145 // this condition will always evaluate to true, but need to
1146 // add the parameter, so it can be set later
1147 comp = new Comparison(session, Comparison.EQUAL_NULL_SAFE, param, param);
1148 }
1149 comp = comp.optimize(session);
1150 boolean addToCondition = true;
1151 if (isGroupQuery) {
1152 addToCondition = false;
1153 for (int i = 0; groupIndex != null && i < groupIndex.length; i++) {
1154 if (groupIndex[i] == columnId) {
1155 addToCondition = true;
1156 break;
1157 }
1158 }
1159 if (!addToCondition) {
1160 if (havingIndex >= 0) {
1161 having = expressions.get(havingIndex);
1162 }
1163 if (having == null) {
1164 having = comp;
1165 } else {
1166 having = new ConditionAndOr(ConditionAndOr.AND, having, comp);
1167 }
1168 }
1169 }
1170 if (addToCondition) {
1171 if (condition == null) {
1172 condition = comp;
1173 } else {
1174 condition = new ConditionAndOr(ConditionAndOr.AND, condition, comp);
1175 }
1176 }
1177 }
1178
1179 public void updateAggregate(Session s) {
1180 for (Expression e : expressions) {
1181 e.updateAggregate(s);
1182 }
1183 if (condition != null) {
1184 condition.updateAggregate(s);
1185 }
1186 if (having != null) {
1187 having.updateAggregate(s);
1188 }
1189 }
1190
1191 public boolean isEverything(ExpressionVisitor visitor) {
1192 switch(visitor.getType()) {
1193 case ExpressionVisitor.DETERMINISTIC: {
1194 if (isForUpdate) {
1195 return false;
1196 }
1197 for (int i = 0, size = filters.size(); i < size; i++) {
1198 TableFilter f = filters.get(i);
1199 if (!f.getTable().isDeterministic()) {
1200 return false;
1201 }
1202 }
1203 break;
1204 }
1205 case ExpressionVisitor.SET_MAX_DATA_MODIFICATION_ID: {
1206 for (int i = 0, size = filters.size(); i < size; i++) {
1207 TableFilter f = filters.get(i);
1208 long m = f.getTable().getMaxDataModificationId();
1209 visitor.addDataModificationId(m);
1210 }
1211 break;
1212 }
1213 case ExpressionVisitor.EVALUATABLE: {
1214 if (!session.getDatabase().getSettings().optimizeEvaluatableSubqueries) {
1215 return false;
1216 }
1217 break;
1218 }
1219 case ExpressionVisitor.GET_DEPENDENCIES: {
1220 for (int i = 0, size = filters.size(); i < size; i++) {
1221 TableFilter f = filters.get(i);
1222 Table table = f.getTable();
1223 visitor.addDependency(table);
1224 table.addDependencies(visitor.getDependencies());
1225 }
1226 break;
1227 }
1228 default:
1229 }
1230 ExpressionVisitor v2 = visitor.incrementQueryLevel(1);
1231 boolean result = true;
1232 for (int i = 0, size = expressions.size(); i < size; i++) {
1233 Expression e = expressions.get(i);
1234 if (!e.isEverything(v2)) {
1235 result = false;
1236 break;
1237 }
1238 }
1239 if (result && condition != null && !condition.isEverything(v2)) {
1240 result = false;
1241 }
1242 if (result && having != null && !having.isEverything(v2)) {
1243 result = false;
1244 }
1245 return result;
1246 }
1247
1248 public boolean isReadOnly() {
1249 return isEverything(ExpressionVisitor.READONLY_VISITOR);
1250 }
1251
1252
1253 public boolean isCacheable() {
1254 return !isForUpdate;
1255 }
1256
1257 public int getType() {
1258 return CommandInterface.SELECT;
1259 }
1260
1261 public boolean allowGlobalConditions() {
1262 if (offsetExpr == null && (limitExpr == null || sort == null)) {
1263 return true;
1264 }
1265 return false;
1266 }
1267
1268 }
1269