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.tools; |
7 | |
8 | import java.sql.PreparedStatement; |
9 | import java.sql.ResultSet; |
10 | import java.sql.SQLException; |
11 | import java.util.ArrayList; |
12 | import java.util.Collections; |
13 | import java.util.Comparator; |
14 | import org.h2.util.New; |
15 | import org.h2.util.StringUtils; |
16 | |
17 | /** |
18 | * A tool to help an application execute multi-dimensional range queries. |
19 | * The algorithm used is database independent, the only requirement |
20 | * is that the engine supports a range index (for example b-tree). |
21 | */ |
22 | public class MultiDimension implements Comparator<long[]> { |
23 | |
24 | private static final MultiDimension INSTANCE = new MultiDimension(); |
25 | |
26 | protected MultiDimension() { |
27 | // don't allow construction by normal code |
28 | // but allow tests |
29 | } |
30 | |
31 | /** |
32 | * Get the singleton. |
33 | * |
34 | * @return the singleton |
35 | */ |
36 | public static MultiDimension getInstance() { |
37 | return INSTANCE; |
38 | } |
39 | |
40 | /** |
41 | * Normalize a value so that it is between the minimum and maximum for the |
42 | * given number of dimensions. |
43 | * |
44 | * @param dimensions the number of dimensions |
45 | * @param value the value (must be in the range min..max) |
46 | * @param min the minimum value |
47 | * @param max the maximum value (must be larger than min) |
48 | * @return the normalized value in the range 0..getMaxValue(dimensions) |
49 | */ |
50 | public int normalize(int dimensions, double value, double min, double max) { |
51 | if (value < min || value > max) { |
52 | throw new IllegalArgumentException(min + "<" + value + "<" + max); |
53 | } |
54 | double x = (value - min) / (max - min); |
55 | return (int) (x * getMaxValue(dimensions)); |
56 | } |
57 | |
58 | /** |
59 | * Get the maximum value for the given dimension count. For two dimensions, |
60 | * each value must contain at most 32 bit, for 3: 21 bit, 4: 16 bit, 5: 12 |
61 | * bit, 6: 10 bit, 7: 9 bit, 8: 8 bit. |
62 | * |
63 | * @param dimensions the number of dimensions |
64 | * @return the maximum value |
65 | */ |
66 | public int getMaxValue(int dimensions) { |
67 | if (dimensions < 2 || dimensions > 32) { |
68 | throw new IllegalArgumentException("" + dimensions); |
69 | } |
70 | int bitsPerValue = getBitsPerValue(dimensions); |
71 | return (int) ((1L << bitsPerValue) - 1); |
72 | } |
73 | |
74 | private static int getBitsPerValue(int dimensions) { |
75 | return Math.min(31, 64 / dimensions); |
76 | } |
77 | |
78 | /** |
79 | * Convert the multi-dimensional value into a one-dimensional (scalar) |
80 | * value. This is done by interleaving the bits of the values. Each values |
81 | * must be between 0 (including) and the maximum value for the given number |
82 | * of dimensions (getMaxValue, excluding). To normalize values to this |
83 | * range, use the normalize function. |
84 | * |
85 | * @param values the multi-dimensional value |
86 | * @return the scalar value |
87 | */ |
88 | public long interleave(int... values) { |
89 | int dimensions = values.length; |
90 | long max = getMaxValue(dimensions); |
91 | int bitsPerValue = getBitsPerValue(dimensions); |
92 | long x = 0; |
93 | for (int i = 0; i < dimensions; i++) { |
94 | long k = values[i]; |
95 | if (k < 0 || k > max) { |
96 | throw new IllegalArgumentException(0 + "<" + k + "<" + max); |
97 | } |
98 | for (int b = 0; b < bitsPerValue; b++) { |
99 | x |= (k & (1L << b)) << (i + (dimensions - 1) * b); |
100 | } |
101 | } |
102 | return x; |
103 | } |
104 | |
105 | /** |
106 | * Convert the two-dimensional value into a one-dimensional (scalar) value. |
107 | * This is done by interleaving the bits of the values. |
108 | * Each values must be between 0 (including) and the maximum value |
109 | * for the given number of dimensions (getMaxValue, excluding). |
110 | * To normalize values to this range, use the normalize function. |
111 | * |
112 | * @param x the value of the first dimension, normalized |
113 | * @param y the value of the second dimension, normalized |
114 | * @return the scalar value |
115 | */ |
116 | public long interleave(int x, int y) { |
117 | if (x < 0) { |
118 | throw new IllegalArgumentException(0 + "<" + x); |
119 | } |
120 | if (y < 0) { |
121 | throw new IllegalArgumentException(0 + "<" + y); |
122 | } |
123 | long z = 0; |
124 | for (int i = 0; i < 32; i++) { |
125 | z |= (x & (1L << i)) << i; |
126 | z |= (y & (1L << i)) << (i + 1); |
127 | } |
128 | return z; |
129 | } |
130 | |
131 | /** |
132 | * Gets one of the original multi-dimensional values from a scalar value. |
133 | * |
134 | * @param dimensions the number of dimensions |
135 | * @param scalar the scalar value |
136 | * @param dim the dimension of the returned value (starting from 0) |
137 | * @return the value |
138 | */ |
139 | public int deinterleave(int dimensions, long scalar, int dim) { |
140 | int bitsPerValue = getBitsPerValue(dimensions); |
141 | int value = 0; |
142 | for (int i = 0; i < bitsPerValue; i++) { |
143 | value |= (scalar >> (dim + (dimensions - 1) * i)) & (1L << i); |
144 | } |
145 | return value; |
146 | } |
147 | |
148 | /** |
149 | * Generates an optimized multi-dimensional range query. The query contains |
150 | * parameters. It can only be used with the H2 database. |
151 | * |
152 | * @param table the table name |
153 | * @param columns the list of columns |
154 | * @param scalarColumn the column name of the computed scalar column |
155 | * @return the query |
156 | */ |
157 | public String generatePreparedQuery(String table, String scalarColumn, |
158 | String[] columns) { |
159 | StringBuilder buff = new StringBuilder("SELECT D.* FROM "); |
160 | buff.append(StringUtils.quoteIdentifier(table)). |
161 | append(" D, TABLE(_FROM_ BIGINT=?, _TO_ BIGINT=?) WHERE "). |
162 | append(StringUtils.quoteIdentifier(scalarColumn)). |
163 | append(" BETWEEN _FROM_ AND _TO_"); |
164 | for (String col : columns) { |
165 | buff.append(" AND ").append(StringUtils.quoteIdentifier(col)). |
166 | append("+1 BETWEEN ?+1 AND ?+1"); |
167 | } |
168 | return buff.toString(); |
169 | } |
170 | |
171 | /** |
172 | * Executes a prepared query that was generated using generatePreparedQuery. |
173 | * |
174 | * @param prep the prepared statement |
175 | * @param min the lower values |
176 | * @param max the upper values |
177 | * @return the result set |
178 | */ |
179 | public ResultSet getResult(PreparedStatement prep, int[] min, int[] max) |
180 | throws SQLException { |
181 | long[][] ranges = getMortonRanges(min, max); |
182 | int len = ranges.length; |
183 | Long[] from = new Long[len]; |
184 | Long[] to = new Long[len]; |
185 | for (int i = 0; i < len; i++) { |
186 | from[i] = Long.valueOf(ranges[i][0]); |
187 | to[i] = Long.valueOf(ranges[i][1]); |
188 | } |
189 | prep.setObject(1, from); |
190 | prep.setObject(2, to); |
191 | len = min.length; |
192 | for (int i = 0, idx = 3; i < len; i++) { |
193 | prep.setInt(idx++, min[i]); |
194 | prep.setInt(idx++, max[i]); |
195 | } |
196 | return prep.executeQuery(); |
197 | } |
198 | |
199 | /** |
200 | * Gets a list of ranges to be searched for a multi-dimensional range query |
201 | * where min <= value <= max. In most cases, the ranges will be larger |
202 | * than required in order to combine smaller ranges into one. Usually, about |
203 | * double as many points will be included in the resulting range. |
204 | * |
205 | * @param min the minimum value |
206 | * @param max the maximum value |
207 | * @return the list of ranges (low, high pairs) |
208 | */ |
209 | private long[][] getMortonRanges(int[] min, int[] max) { |
210 | int len = min.length; |
211 | if (max.length != len) { |
212 | throw new IllegalArgumentException(len + "=" + max.length); |
213 | } |
214 | for (int i = 0; i < len; i++) { |
215 | if (min[i] > max[i]) { |
216 | int temp = min[i]; |
217 | min[i] = max[i]; |
218 | max[i] = temp; |
219 | } |
220 | } |
221 | int total = getSize(min, max, len); |
222 | ArrayList<long[]> list = New.arrayList(); |
223 | addMortonRanges(list, min, max, len, 0); |
224 | combineEntries(list, total); |
225 | long[][] ranges = new long[list.size()][2]; |
226 | list.toArray(ranges); |
227 | return ranges; |
228 | } |
229 | |
230 | private static int getSize(int[] min, int[] max, int len) { |
231 | int size = 1; |
232 | for (int i = 0; i < len; i++) { |
233 | int diff = max[i] - min[i]; |
234 | size *= diff + 1; |
235 | } |
236 | return size; |
237 | } |
238 | |
239 | /** |
240 | * Combine entries if the size of the list is too large. |
241 | * |
242 | * @param list list of pairs(low, high) |
243 | * @param total product of the gap lengths |
244 | */ |
245 | private void combineEntries(ArrayList<long[]> list, int total) { |
246 | Collections.sort(list, this); |
247 | for (int minGap = 10; minGap < total; minGap += minGap / 2) { |
248 | for (int i = 0; i < list.size() - 1; i++) { |
249 | long[] current = list.get(i); |
250 | long[] next = list.get(i + 1); |
251 | if (current[1] + minGap >= next[0]) { |
252 | current[1] = next[1]; |
253 | list.remove(i + 1); |
254 | i--; |
255 | } |
256 | } |
257 | int searched = 0; |
258 | for (long[] range : list) { |
259 | searched += range[1] - range[0] + 1; |
260 | } |
261 | if (searched > 2 * total || list.size() < 100) { |
262 | break; |
263 | } |
264 | } |
265 | } |
266 | |
267 | @Override |
268 | public int compare(long[] a, long[] b) { |
269 | return a[0] > b[0] ? 1 : -1; |
270 | } |
271 | |
272 | private void addMortonRanges(ArrayList<long[]> list, int[] min, int[] max, |
273 | int len, int level) { |
274 | if (level > 100) { |
275 | throw new IllegalArgumentException("" + level); |
276 | } |
277 | int largest = 0, largestDiff = 0; |
278 | long size = 1; |
279 | for (int i = 0; i < len; i++) { |
280 | int diff = max[i] - min[i]; |
281 | if (diff < 0) { |
282 | throw new IllegalArgumentException(""+ diff); |
283 | } |
284 | size *= diff + 1; |
285 | if (size < 0) { |
286 | throw new IllegalArgumentException("" + size); |
287 | } |
288 | if (diff > largestDiff) { |
289 | largestDiff = diff; |
290 | largest = i; |
291 | } |
292 | } |
293 | long low = interleave(min), high = interleave(max); |
294 | if (high < low) { |
295 | throw new IllegalArgumentException(high + "<" + low); |
296 | } |
297 | long range = high - low + 1; |
298 | if (range == size) { |
299 | long[] item = { low, high }; |
300 | list.add(item); |
301 | } else { |
302 | int middle = findMiddle(min[largest], max[largest]); |
303 | int temp = max[largest]; |
304 | max[largest] = middle; |
305 | addMortonRanges(list, min, max, len, level + 1); |
306 | max[largest] = temp; |
307 | temp = min[largest]; |
308 | min[largest] = middle + 1; |
309 | addMortonRanges(list, min, max, len, level + 1); |
310 | min[largest] = temp; |
311 | } |
312 | } |
313 | |
314 | private static int roundUp(int x, int blockSizePowerOf2) { |
315 | return (x + blockSizePowerOf2 - 1) & (-blockSizePowerOf2); |
316 | } |
317 | |
318 | private static int findMiddle(int a, int b) { |
319 | int diff = b - a - 1; |
320 | if (diff == 0) { |
321 | return a; |
322 | } |
323 | if (diff == 1) { |
324 | return a + 1; |
325 | } |
326 | int scale = 0; |
327 | while ((1 << scale) < diff) { |
328 | scale++; |
329 | } |
330 | scale--; |
331 | int m = roundUp(a + 2, 1 << scale) - 1; |
332 | if (m <= a || m >= b) { |
333 | throw new IllegalArgumentException(a + "<" + m + "<" + b); |
334 | } |
335 | return m; |
336 | } |
337 | |
338 | } |