EMMA Coverage Report (generated Sun Mar 01 22:06:14 CET 2015)
[all classes][org.h2.command.dml]

COVERAGE SUMMARY FOR SOURCE FILE [Optimizer.java]

nameclass, %method, %block, %line, %
Optimizer.java100% (1/1)100% (13/13)97%  (566/582)97%  (119/123)

COVERAGE BREAKDOWN BY CLASS AND METHOD

nameclass, %method, %block, %line, %
     
class Optimizer100% (1/1)100% (13/13)97%  (566/582)97%  (119/123)
calculateGenetic (): void 100% (1/1)85%  (77/91)84%  (16/19)
canStop (int): boolean 100% (1/1)92%  (24/26)80%  (4/5)
Optimizer (TableFilter [], Expression, Session): void 100% (1/1)100% (12/12)100% (5/5)
calculateBestPlan (): void 100% (1/1)100% (36/36)100% (10/10)
calculateBruteForceAll (): void 100% (1/1)100% (26/26)100% (5/5)
calculateBruteForceSome (): void 100% (1/1)100% (149/149)100% (26/26)
getCost (): double 100% (1/1)100% (3/3)100% (1/1)
getMaxBruteForceFilters (int): int 100% (1/1)100% (28/28)100% (6/6)
getTopFilter (): TableFilter 100% (1/1)100% (3/3)100% (1/1)
optimize (): void 100% (1/1)100% (61/61)100% (10/10)
shuffleAll (TableFilter []): void 100% (1/1)100% (38/38)100% (7/7)
shuffleTwo (TableFilter []): boolean 100% (1/1)100% (75/75)100% (21/21)
testPlan (TableFilter []): boolean 100% (1/1)100% (34/34)100% (7/7)

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 */
6package org.h2.command.dml;
7 
8import java.util.Random;
9import org.h2.engine.Session;
10import org.h2.expression.Expression;
11import org.h2.table.Plan;
12import org.h2.table.PlanItem;
13import org.h2.table.TableFilter;
14import org.h2.util.BitField;
15import org.h2.util.Permutations;
16 
17/**
18 * The optimizer is responsible to find the best execution plan
19 * for a given query.
20 */
21class 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}

[all classes][org.h2.command.dml]
EMMA 2.0.5312 (C) Vladimir Roubtsov