File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\command\dml\Optimizer.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.Random;
10 import org.h2.engine.Session;
11 import org.h2.expression.Expression;
12 import org.h2.table.Plan;
13 import org.h2.table.PlanItem;
14 import org.h2.table.TableFilter;
15 import org.h2.util.BitField;
16 import org.h2.util.Permutations;
17
18 /**
19 * The optimizer is responsible to find the best execution plan
20 * for a given query.
21 */
22 class Optimizer {
23
24 private static final int MAX_BRUTE_FORCE_FILTERS = 7;
25 private static final int MAX_BRUTE_FORCE = 2000;
26 private static final int MAX_GENETIC = 500;
27 private long start;
28 private BitField switched;
29
30 // possible plans for filters, if using brute force:
31 // 1 filter 1 plan
32 // 2 filters 2 plans
33 // 3 filters 6 plans
34 // 4 filters 24 plans
35 // 5 filters 120 plans
36 // 6 filters 720 plans
37 // 7 filters 5040 plans
38 // 8 filters 40320 plan
39 // 9 filters 362880 plans
40 // 10 filters 3628800 filters
41
42 private final TableFilter[] filters;
43 private final Expression condition;
44 private final Session session;
45
46 private Plan bestPlan;
47 private TableFilter topFilter;
48 private double cost;
49 private Random random;
50
51 Optimizer(TableFilter[] filters, Expression condition, Session session) {
52 this.filters = filters;
53 this.condition = condition;
54 this.session = session;
55 }
56
57 /**
58 * How many filter to calculate using brute force. The remaining filters are
59 * selected using a greedy algorithm which has a runtime of (1 + 2 + ... +
60 * n) = (n * (n-1) / 2) for n filters. The brute force algorithm has a
61 * runtime of n * (n-1) * ... * (n-m) when calculating m brute force of n
62 * total. The combined runtime is (brute force) * (greedy).
63 *
64 * @param filterCount the number of filters total
65 * @return the number of filters to calculate using brute force
66 */
67 private static int getMaxBruteForceFilters(int filterCount) {
68 int i = 0, j = filterCount, total = filterCount;
69 while (j > 0 && total * (j * (j - 1) / 2) < MAX_BRUTE_FORCE) {
70 j--;
71 total *= j;
72 i++;
73 }
74 return i;
75 }
76
77 private void calculateBestPlan() {
78 start = System.currentTimeMillis();
79 cost = -1;
80 if (filters.length == 1) {
81 testPlan(filters);
82 } else if (filters.length <= MAX_BRUTE_FORCE_FILTERS) {
83 calculateBruteForceAll();
84 } else {
85 calculateBruteForceSome();
86 random = new Random(0);
87 calculateGenetic();
88 }
89 }
90
91 private boolean canStop(int x) {
92 if ((x & 127) == 0) {
93 long t = System.currentTimeMillis() - start;
94 // don't calculate for simple queries (no rows or so)
95 if (cost >= 0 && 10 * t > cost) {
96 return true;
97 }
98 }
99 return false;
100 }
101
102 private void calculateBruteForceAll() {
103 TableFilter[] list = new TableFilter[filters.length];
104 Permutations<TableFilter> p = Permutations.create(filters, list);
105 for (int x = 0; !canStop(x) && p.next(); x++) {
106 testPlan(list);
107 }
108 }
109
110 private void calculateBruteForceSome() {
111 int bruteForce = getMaxBruteForceFilters(filters.length);
112 TableFilter[] list = new TableFilter[filters.length];
113 Permutations<TableFilter> p = Permutations.create(filters, list, bruteForce);
114 for (int x = 0; !canStop(x) && p.next(); x++) {
115 // find out what filters are not used yet
116 for (TableFilter f : filters) {
117 f.setUsed(false);
118 }
119 for (int i = 0; i < bruteForce; i++) {
120 list[i].setUsed(true);
121 }
122 // fill the remaining elements with the unused elements (greedy)
123 for (int i = bruteForce; i < filters.length; i++) {
124 double costPart = -1.0;
125 int bestPart = -1;
126 for (int j = 0; j < filters.length; j++) {
127 if (!filters[j].isUsed()) {
128 if (i == filters.length - 1) {
129 bestPart = j;
130 break;
131 }
132 list[i] = filters[j];
133 Plan part = new Plan(list, i+1, condition);
134 double costNow = part.calculateCost(session);
135 if (costPart < 0 || costNow < costPart) {
136 costPart = costNow;
137 bestPart = j;
138 }
139 }
140 }
141 filters[bestPart].setUsed(true);
142 list[i] = filters[bestPart];
143 }
144 testPlan(list);
145 }
146 }
147
148 private void calculateGenetic() {
149 TableFilter[] best = new TableFilter[filters.length];
150 TableFilter[] list = new TableFilter[filters.length];
151 for (int x = 0; x < MAX_GENETIC; x++) {
152 if (canStop(x)) {
153 break;
154 }
155 boolean generateRandom = (x & 127) == 0;
156 if (!generateRandom) {
157 System.arraycopy(best, 0, list, 0, filters.length);
158 if (!shuffleTwo(list)) {
159 generateRandom = true;
160 }
161 }
162 if (generateRandom) {
163 switched = new BitField();
164 System.arraycopy(filters, 0, best, 0, filters.length);
165 shuffleAll(best);
166 System.arraycopy(best, 0, list, 0, filters.length);
167 }
168 if (testPlan(list)) {
169 switched = new BitField();
170 System.arraycopy(list, 0, best, 0, filters.length);
171 }
172 }
173 }
174
175 private boolean testPlan(TableFilter[] list) {
176 Plan p = new Plan(list, list.length, condition);
177 double costNow = p.calculateCost(session);
178 if (cost < 0 || costNow < cost) {
179 cost = costNow;
180 bestPlan = p;
181 return true;
182 }
183 return false;
184 }
185
186 private void shuffleAll(TableFilter[] f) {
187 for (int i = 0; i < f.length - 1; i++) {
188 int j = i + random.nextInt(f.length - i);
189 if (j != i) {
190 TableFilter temp = f[i];
191 f[i] = f[j];
192 f[j] = temp;
193 }
194 }
195 }
196
197 private boolean shuffleTwo(TableFilter[] f) {
198 int a = 0, b = 0, i = 0;
199 for (; i < 20; i++) {
200 a = random.nextInt(f.length);
201 b = random.nextInt(f.length);
202 if (a == b) {
203 continue;
204 }
205 if (a < b) {
206 int temp = a;
207 a = b;
208 b = temp;
209 }
210 int s = a * f.length + b;
211 if (switched.get(s)) {
212 continue;
213 }
214 switched.set(s);
215 break;
216 }
217 if (i == 20) {
218 return false;
219 }
220 TableFilter temp = f[a];
221 f[a] = f[b];
222 f[b] = temp;
223 return true;
224 }
225
226 /**
227 * Calculate the best query plan to use.
228 */
229 void optimize() {
230 calculateBestPlan();
231 bestPlan.removeUnusableIndexConditions();
232 TableFilter[] f2 = bestPlan.getFilters();
233 topFilter = f2[0];
234 for (int i = 0; i < f2.length - 1; i++) {
235 f2[i].addJoin(f2[i + 1], false, false, null);
236 }
237 for (TableFilter f : f2) {
238 PlanItem item = bestPlan.getItem(f);
239 f.setPlanItem(item);
240 }
241 }
242
243 public TableFilter getTopFilter() {
244 return topFilter;
245 }
246
247 double getCost() {
248 return cost;
249 }
250
251 }
252