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