|
1
5 package org.h2.command.dml;
6
7 import java.sql.SQLException  ;
8 import java.util.BitSet ;
9 import java.util.Random ;
10
11 import org.h2.engine.Session;
12 import org.h2.expression.Expression;
13 import org.h2.table.Plan;
14 import org.h2.table.PlanItem;
15 import org.h2.table.TableFilter;
16 import org.h2.util.Permutations;
17
18 public class Optimizer {
19
20 private static final int MAX_BRUTE_FORCE_FILTERS=7;
21 private static final int MAX_BRUTE_FORCE=2000;
22 private static final int MAX_GENETIC=2000;
23 private long start;
24 private BitSet switched;
25
26
42 private TableFilter[] filters;
43 private Expression condition;
44 private Session session;
45
46 private Plan bestPlan;
47 private TableFilter topFilter;
48 private double cost;
49 private Random random;
50
51 private int getMaxBruteForceFilters(int filterCount) {
52 int i = 0, j = filterCount, total = filterCount;
53 while(j>0 && total < MAX_BRUTE_FORCE) {
54 j--;
55 total *= j;
56 i++;
57 }
58 return i;
59 }
60
61 Optimizer(TableFilter[] filters, Expression condition, Session session) {
62 this.filters = filters;
63 this.condition = condition;
64 this.session = session;
65 }
66
67 private void calculateBestPlan() throws SQLException {
68 start = System.currentTimeMillis();
69 cost = -1;
70 if(filters.length==1) {
71 testPlan(filters);
72 } else if (filters.length <= MAX_BRUTE_FORCE_FILTERS) {
73 calculateBruteForceAll();
74 } else {
75 calculateBruteForceSome();
76 random = new Random (0);
77 calculateGenetic();
78 }
80 }
81
82 private boolean canStop(int x) {
83 if((x & 127) == 0) {
84 long t = System.currentTimeMillis() - start;
85 if(cost >= 0 && 10*t > cost) {
87 return true;
88 }
89 }
90 return false;
91 }
92
93 private void calculateBruteForceAll() throws SQLException {
94 TableFilter[] ftry = new TableFilter[filters.length];
95 Permutations perm = new Permutations(filters, ftry);
96 for(int x=0; !canStop(x) && perm.next(); x++) {
97 testPlan(ftry);
98 }
99 }
100
101 private void calculateBruteForceSome() throws SQLException {
102 int bruteForce = getMaxBruteForceFilters(filters.length);
103 TableFilter[] ftry = new TableFilter[filters.length];
104 Permutations perm = new Permutations(filters, ftry, bruteForce);
105 for(int x=0; !canStop(x) && perm.next(); x++) {
106 for(int i=0; i<filters.length; i++) {
108 filters[i].setUsed(false);
109 }
110 for(int i=0; i<bruteForce; i++) {
111 ftry[i].setUsed(true);
112 }
113 for(int i=bruteForce; i<filters.length; i++) {
115 double costPart = -1.0;
116 int bestPart = -1;
117 for(int j=0; j<filters.length; j++) {
118 if(!filters[j].getUsed()) {
119 if(i==filters.length-1) {
120 bestPart = j;
121 break;
122 }
123 ftry[i] = filters[j];
124 Plan part = new Plan(ftry, i+1, condition);
125 double costNow = part.calculateCost(session);
126 if (costPart < 0 || costNow < costPart) {
127 costPart = costNow;
128 bestPart = j;
129 }
130 }
131 }
132 filters[bestPart].setUsed(true);
133 ftry[i] = filters[bestPart];
134 }
135 testPlan(ftry);
136 }
137 }
138
139 private void calculateGenetic() throws SQLException {
140 TableFilter[] fbest = new TableFilter[filters.length];
141 TableFilter[] ftry = new TableFilter[filters.length];
142 for(int x=0; x<MAX_GENETIC; x++) {
143 if(canStop(x)) {
144 break;
145 }
146 boolean generateRandom = (x & 127) == 0;
147 if(!generateRandom) {
148 System.arraycopy(fbest, 0, ftry, 0, filters.length);
149 if(!shuffleTwo(ftry)) {
150 generateRandom = true;
151 }
152 }
153 if(generateRandom) {
154 switched = new BitSet ();
155 System.arraycopy(filters, 0, fbest, 0, filters.length);
156 shuffleAll(fbest);
157 System.arraycopy(fbest, 0, ftry, 0, filters.length);
158 }
159 if(testPlan(ftry)) {
160 switched = new BitSet ();
161 System.arraycopy(ftry, 0, fbest, 0, filters.length);
162 }
163 }
164 }
165
166 private boolean testPlan(TableFilter[] ftry) throws SQLException {
167 Plan p = new Plan(ftry, ftry.length, condition);
168 double costNow = p.calculateCost(session);
169 if (cost < 0 || costNow < cost) {
170 cost = costNow;
171 bestPlan = p;
172 return true;
173 }
174 return false;
175 }
176
177 private void shuffleAll(TableFilter[] f) {
178 for(int i=0; i<f.length-1; i++) {
179 int j = i + random.nextInt(f.length - i);
180 if(j != i) {
181 TableFilter temp = f[i];
182 f[i] = f[j];
183 f[j] = temp;
184 }
185 }
186 }
187
188 private boolean shuffleTwo(TableFilter[] f) {
189 int a = 0, b = 0, i = 0;
190 for(; i<20; i++) {
191 a = random.nextInt(f.length);
192 b = random.nextInt(f.length);
193 if(a==b) {
194 continue;
195 }
196 if(a<b) {
197 int temp = a;
198 a = b;
199 b = temp;
200 }
201 int s = a * f.length + b;
202 if(switched.get(s)) {
203 continue;
204 }
205 switched.set(s);
206 break;
207 }
208 if(i==20) {
209 return false;
210 }
211 TableFilter temp = f[a];
212 f[a] = f[b];
213 f[b] = temp;
214 return true;
215 }
216
217 void optimize() throws SQLException {
218 calculateBestPlan();
219 bestPlan.removeUnusableIndexConditions();
220 TableFilter[] f2 = bestPlan.getFilters();
221 topFilter = f2[0];
222 for (int i = 0; i < f2.length - 1; i++) {
223 f2[i].addJoin(f2[i + 1], false, null);
224 }
225 for (int i = 0; i < f2.length; i++) {
226 PlanItem item = bestPlan.getItem(f2[i]);
227 f2[i].setPlanItem(item);
228 }
229 }
230
231 public TableFilter getTopFilter() {
232 return topFilter;
233 }
234
235 double getCost() {
236 return cost;
237 }
238
239 }
240 |
Popular Tags |
Java API By Example, From Geeks To Geeks.