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.command.dml;
007:
008: import java.sql.SQLException;
009: import java.util.BitSet;
010: import java.util.Random;
011:
012: import org.h2.engine.Session;
013: import org.h2.expression.Expression;
014: import org.h2.table.Plan;
015: import org.h2.table.PlanItem;
016: import org.h2.table.TableFilter;
017: import org.h2.util.Permutations;
018:
019: /**
020: * The optimizer is responsible to find the best execution plan
021: * for a given query.
022: */
023: public class Optimizer {
024:
025: private static final int MAX_BRUTE_FORCE_FILTERS = 7;
026: private static final int MAX_BRUTE_FORCE = 2000;
027: private static final int MAX_GENETIC = 2000;
028: private long start;
029: private BitSet switched;
030:
031: // possible plans for filters:
032: // 1 filter 1 plan
033: // 2 filters 2 plans
034: // 3 filters 6 plans
035: // 4 filters 24 plans
036: // 5 filters 120 plans
037: // 6 filters 720 plans
038: // 7 filters 5040 plans
039: // 8 filters 40320 plan
040: // 9 filters 362880 plans
041: // 10 filters 3628800 filters
042: // 1 of 1, 2, 3, 4, 5, 6 filters: 1, 2, 3, 4, 5, 6
043: // 2 of 2, 3, 4, 5, 6 filters: 2, 6, 12, 20, 30
044: // 3 of 3, 4, 5, 6 filters: 6, 24, 75, 120
045: // 4 of 4, 5, 6 filters: 24, 120, 260
046:
047: private TableFilter[] filters;
048: private Expression condition;
049: private Session session;
050:
051: private Plan bestPlan;
052: private TableFilter topFilter;
053: private double cost;
054: private Random random;
055:
056: private int getMaxBruteForceFilters(int filterCount) {
057: int i = 0, j = filterCount, total = filterCount;
058: while (j > 0 && total < MAX_BRUTE_FORCE) {
059: j--;
060: total *= j;
061: i++;
062: }
063: return i;
064: }
065:
066: Optimizer(TableFilter[] filters, Expression condition,
067: Session session) {
068: this .filters = filters;
069: this .condition = condition;
070: this .session = session;
071: }
072:
073: private void calculateBestPlan() throws SQLException {
074: start = System.currentTimeMillis();
075: cost = -1;
076: if (filters.length == 1) {
077: testPlan(filters);
078: } else if (filters.length <= MAX_BRUTE_FORCE_FILTERS) {
079: calculateBruteForceAll();
080: } else {
081: calculateBruteForceSome();
082: random = new Random(0);
083: calculateGenetic();
084: // TODO optimizer: how to use rule based optimizer?
085: }
086: }
087:
088: private boolean canStop(int x) {
089: if ((x & 127) == 0) {
090: long t = System.currentTimeMillis() - start;
091: // don't calculate for simple queries (no rows or so)
092: if (cost >= 0 && 10 * t > cost) {
093: return true;
094: }
095: }
096: return false;
097: }
098:
099: private void calculateBruteForceAll() throws SQLException {
100: TableFilter[] list = new TableFilter[filters.length];
101: Permutations p = new Permutations(filters, list);
102: for (int x = 0; !canStop(x) && p.next(); x++) {
103: testPlan(list);
104: }
105: }
106:
107: private void calculateBruteForceSome() throws SQLException {
108: int bruteForce = getMaxBruteForceFilters(filters.length);
109: TableFilter[] list = new TableFilter[filters.length];
110: Permutations p = new Permutations(filters, list, bruteForce);
111: for (int x = 0; !canStop(x) && p.next(); x++) {
112: // find out what filters are not used yet
113: for (int i = 0; i < filters.length; i++) {
114: filters[i].setUsed(false);
115: }
116: for (int i = 0; i < bruteForce; i++) {
117: list[i].setUsed(true);
118: }
119: // fill the remaining elements with the unused elements (greedy)
120: for (int i = bruteForce; i < filters.length; i++) {
121: double costPart = -1.0;
122: int bestPart = -1;
123: for (int j = 0; j < filters.length; j++) {
124: if (!filters[j].getUsed()) {
125: if (i == filters.length - 1) {
126: bestPart = j;
127: break;
128: }
129: list[i] = filters[j];
130: Plan part = new Plan(list, i + 1, condition);
131: double costNow = part.calculateCost(session);
132: if (costPart < 0 || costNow < costPart) {
133: costPart = costNow;
134: bestPart = j;
135: }
136: }
137: }
138: filters[bestPart].setUsed(true);
139: list[i] = filters[bestPart];
140: }
141: testPlan(list);
142: }
143: }
144:
145: private void calculateGenetic() throws SQLException {
146: TableFilter[] best = new TableFilter[filters.length];
147: TableFilter[] list = new TableFilter[filters.length];
148: for (int x = 0; x < MAX_GENETIC; x++) {
149: if (canStop(x)) {
150: break;
151: }
152: boolean generateRandom = (x & 127) == 0;
153: if (!generateRandom) {
154: System.arraycopy(best, 0, list, 0, filters.length);
155: if (!shuffleTwo(list)) {
156: generateRandom = true;
157: }
158: }
159: if (generateRandom) {
160: switched = new BitSet();
161: System.arraycopy(filters, 0, best, 0, filters.length);
162: shuffleAll(best);
163: System.arraycopy(best, 0, list, 0, filters.length);
164: }
165: if (testPlan(list)) {
166: switched = new BitSet();
167: System.arraycopy(list, 0, best, 0, filters.length);
168: }
169: }
170: }
171:
172: private boolean testPlan(TableFilter[] list) throws SQLException {
173: Plan p = new Plan(list, list.length, condition);
174: double costNow = p.calculateCost(session);
175: if (cost < 0 || costNow < cost) {
176: cost = costNow;
177: bestPlan = p;
178: return true;
179: }
180: return false;
181: }
182:
183: private void shuffleAll(TableFilter[] f) {
184: for (int i = 0; i < f.length - 1; i++) {
185: int j = i + random.nextInt(f.length - i);
186: if (j != i) {
187: TableFilter temp = f[i];
188: f[i] = f[j];
189: f[j] = temp;
190: }
191: }
192: }
193:
194: private boolean shuffleTwo(TableFilter[] f) {
195: int a = 0, b = 0, i = 0;
196: for (; i < 20; i++) {
197: a = random.nextInt(f.length);
198: b = random.nextInt(f.length);
199: if (a == b) {
200: continue;
201: }
202: if (a < b) {
203: int temp = a;
204: a = b;
205: b = temp;
206: }
207: int s = a * f.length + b;
208: if (switched.get(s)) {
209: continue;
210: }
211: switched.set(s);
212: break;
213: }
214: if (i == 20) {
215: return false;
216: }
217: TableFilter temp = f[a];
218: f[a] = f[b];
219: f[b] = temp;
220: return true;
221: }
222:
223: void optimize() throws SQLException {
224: calculateBestPlan();
225: bestPlan.removeUnusableIndexConditions();
226: TableFilter[] f2 = bestPlan.getFilters();
227: topFilter = f2[0];
228: for (int i = 0; i < f2.length - 1; i++) {
229: f2[i].addJoin(f2[i + 1], false, null);
230: }
231: for (int i = 0; i < f2.length; i++) {
232: PlanItem item = bestPlan.getItem(f2[i]);
233: f2[i].setPlanItem(item);
234: }
235: }
236:
237: public TableFilter getTopFilter() {
238: return topFilter;
239: }
240:
241: double getCost() {
242: return cost;
243: }
244:
245: }
|