001: /*
002: * Copyright 2004-2008 H2 Group. Licensed under the H2 License, Version 1.0
003: * (http://h2database.com/html/license.html).
004: * Initial Developer: H2 Group
005: */
006: package org.h2.tools;
007:
008: import java.sql.PreparedStatement;
009: import java.sql.ResultSet;
010: import java.sql.SQLException;
011: import java.util.ArrayList;
012: import java.util.Collections;
013: import java.util.Comparator;
014: import org.h2.util.StringUtils;
015:
016: /**
017: * A tool to help an application execute multi-dimensional range queries.
018: * The algorithm used is database independent, the only requirement
019: * is that the engine supports a range index (for example b-tree).
020: */
021: public class MultiDimension {
022:
023: private static MultiDimension instance = new MultiDimension();
024:
025: private MultiDimension() {
026: }
027:
028: /**
029: * Get the singleton.
030: *
031: * @return the singleton
032: */
033: public static MultiDimension getInstance() {
034: return instance;
035: }
036:
037: /**
038: * Convert the multi-dimensional value into a one-dimensional (scalar) value.
039: * This is done by interleaving the bits of the values.
040: * Each values must be bigger or equal to 0. The maximum value
041: * is dependent on the number of dimensions. For two keys, it is 32 bit,
042: * for 3: 21 bit, 4: 16 bit, 5: 12 bit, 6: 10 bit, 7: 9 bit, 8: 8 bit.
043: *
044: * @param values the multi-dimensional value
045: * @return the scalar value
046: */
047: public long interleave(int[] values) {
048: int dimensions = values.length;
049: int bitsPerValue = 64 / dimensions;
050: // for 2 keys: 0x800000; 3: 0x
051: long max = 1L << bitsPerValue;
052: long x = 0;
053: for (int i = 0; i < dimensions; i++) {
054: long k = values[i];
055: if (k < 0 || k > max) {
056: throw new Error("value out of range; value="
057: + values[i] + " min=0 max=" + max);
058: }
059: for (int b = 0; b < bitsPerValue; b++) {
060: x |= (k & (1L << b)) << (i + (dimensions - 1) * b);
061: }
062: }
063: if (dimensions == 2) {
064: long xx = getMorton2(values[0], values[1]);
065: if (xx != x) {
066: throw new Error("test");
067: }
068: }
069: return x;
070: }
071:
072: /**
073: * Gets one of the original multi-dimensional values from a scalar value.
074: *
075: * @param scalar the scalar value
076: * @param dimensions the number of dimensions
077: * @param dim the dimension of the returned value (starting from 0)
078: * @return the value
079: */
080: public int deinterleave(long scalar, int dimensions, int dim) {
081: int bitsPerValue = 64 / dimensions;
082: int value = 0;
083: for (int i = 0; i < bitsPerValue; i++) {
084: value |= (scalar >> (dim + (dimensions - 1) * i))
085: & (1L << i);
086: }
087: return value;
088: }
089:
090: // public static int get(long z, int d) {
091: // int n = 0;
092: // for (int i = 0; i < 31; i++) {
093: // n |= (z & (1 << (i + i + d))) >> (i + d);
094: // }
095: // return n;
096: // }
097:
098: /**
099: * Generates an optimized multi-dimensional range query.
100: * The query contains parameters. It can only be used with the H2 database.
101: *
102: * @param table the table name
103: * @param columns the list of columns
104: * @param scalarColumn the column name of the computed scalar column
105: * @return the query
106: */
107: public String generatePreparedQuery(String table,
108: String scalarColumn, String[] columns) {
109: StringBuffer buff = new StringBuffer("SELECT D.* FROM ");
110: buff.append(StringUtils.quoteIdentifier(table));
111: buff.append(" D, TABLE(_FROM_ BIGINT=?, _TO_ BIGINT=?) WHERE ");
112: buff.append(StringUtils.quoteIdentifier(scalarColumn));
113: buff.append(" BETWEEN _FROM_ AND _TO_");
114: for (int i = 0; i < columns.length; i++) {
115: buff.append(" AND ");
116: buff.append(StringUtils.quoteIdentifier(columns[i]));
117: buff.append("+1 BETWEEN ?+1 AND ?+1");
118: }
119: return buff.toString();
120: }
121:
122: /**
123: * Executes a prepared query that was generated using generatePreparedQuery.
124: *
125: * @param prep the prepared statement
126: * @param min the lower values
127: * @param max the upper values
128: * @return the result set
129: */
130: public ResultSet getResult(PreparedStatement prep, int[] min,
131: int[] max) throws SQLException {
132: long[][] ranges = getMortonRanges(min, max);
133: int len = ranges.length;
134: Long[] from = new Long[len];
135: Long[] to = new Long[len];
136: for (int i = 0; i < len; i++) {
137: from[i] = new Long(ranges[i][0]);
138: to[i] = new Long(ranges[i][1]);
139: }
140: prep.setObject(1, from);
141: prep.setObject(2, to);
142: len = min.length;
143: for (int i = 0, idx = 3; i < len; i++) {
144: prep.setInt(idx++, min[i]);
145: prep.setInt(idx++, max[i]);
146: }
147: return prep.executeQuery();
148: }
149:
150: /**
151: * Generates an optimized multi-dimensional range query.
152: * This query is database independent, however the performance is
153: * not as good as when using generatePreparedQuery
154: *
155: * @param table the table name
156: * @param columns the list of columns
157: * @param min the lower values
158: * @param max the upper values
159: * @param scalarColumn the column name of the computed scalar column
160: * @return the query
161: */
162: public String generateQuery(String table, String scalarColumn,
163: String[] columns, int[] min, int[] max) {
164: long[][] ranges = getMortonRanges(min, max);
165: StringBuffer buff = new StringBuffer("SELECT * FROM (");
166: for (int i = 0; i < ranges.length; i++) {
167: if (i > 0) {
168: buff.append(" UNION ALL ");
169: }
170: long minScalar = ranges[i][0];
171: long maxScalar = ranges[i][1];
172: buff.append("SELECT * FROM ").append(table).append(
173: " WHERE ");
174: buff.append(scalarColumn).append(" BETWEEN ");
175: buff.append(minScalar).append(" AND ").append(maxScalar);
176: }
177: buff.append(") WHERE ");
178: for (int j = 0; j < columns.length; j++) {
179: if (j > 0) {
180: buff.append(" AND ");
181: }
182: buff.append(columns[j]).append(" BETWEEN ");
183: buff.append(min[j]).append(" AND ").append(max[j]);
184: }
185: return buff.toString();
186: }
187:
188: /**
189: * Gets a list of ranges to be searched for a multi-dimensional range query
190: * where min <= value <= max. In most cases, the ranges will be larger
191: * than required in order to combine smaller ranges into one. Usually, about
192: * double as much points will be included in the resulting range.
193: *
194: * @param min the minimum value
195: * @param max the maximum value
196: * @return the list of ranges
197: */
198: public long[][] getMortonRanges(int[] min, int[] max) {
199: int len = min.length;
200: if (max.length != len) {
201: throw new Error("dimensions mismatch");
202: }
203: for (int i = 0; i < len; i++) {
204: if (min[i] > max[i]) {
205: int temp = min[i];
206: min[i] = max[i];
207: max[i] = temp;
208: }
209: }
210: int total = getSize(min, max, len);
211: ArrayList list = new ArrayList();
212: addMortonRanges(list, min, max, len, 0);
213: optimize(list, total);
214: long[][] ranges = new long[list.size()][2];
215: list.toArray(ranges);
216: return ranges;
217: }
218:
219: private long getMorton2(int x, int y) {
220: long z = 0;
221: for (int i = 0; i < 32; i++) {
222: z |= (x & (1L << i)) << (i);
223: z |= (y & (1L << i)) << (i + 1);
224: }
225: return z;
226: }
227:
228: private int getSize(int[] min, int[] max, int len) {
229: int size = 1;
230: for (int i = 0; i < len; i++) {
231: int diff = max[i] - min[i];
232: size *= (diff + 1);
233: }
234: return size;
235: }
236:
237: private void optimize(ArrayList list, int total) {
238: Collections.sort(list, new Comparator() {
239: public int compare(Object a, Object b) {
240: long[] la = (long[]) a;
241: long[] lb = (long[]) b;
242: return la[0] > lb[0] ? 1 : -1;
243: }
244: });
245: int minGap = 10;
246: for (;; minGap += (minGap / 2)) {
247: for (int i = 0; i < list.size() - 1; i++) {
248: long[] current = (long[]) list.get(i);
249: long[] next = (long[]) list.get(i + 1);
250: if (current[1] + minGap >= next[0]) {
251: current[1] = next[1];
252: list.remove(i + 1);
253: i--;
254: }
255: }
256: int searched = 0;
257: for (int j = 0; j < list.size(); j++) {
258: long[] range = (long[]) list.get(j);
259: searched += range[1] - range[0] + 1;
260: }
261: if (searched > 2 * total || list.size() < 3 /* || minGap > total */) {
262: break;
263: }
264: }
265: }
266:
267: private void addMortonRanges(ArrayList list, int[] min, int[] max,
268: int len, int level) {
269: if (level > 100) {
270: throw new Error("Stop");
271: }
272: int largest = 0, largestDiff = 0;
273: long size = 1;
274: for (int i = 0; i < len; i++) {
275: int diff = max[i] - min[i];
276: if (diff < 0) {
277: throw new Error("Stop");
278: }
279: size *= (diff + 1);
280: if (size < 0) {
281: throw new Error("Stop");
282: }
283: if (diff > largestDiff) {
284: largestDiff = diff;
285: largest = i;
286: }
287: }
288: long low = interleave(min), high = interleave(max);
289: if (high < low) {
290: throw new Error("Stop");
291: }
292: long range = high - low + 1;
293: if (range == size) {
294: long[] item = new long[] { low, high };
295: list.add(item);
296: } else {
297: int middle = findMiddle(min[largest], max[largest]);
298: int temp = max[largest];
299: max[largest] = middle;
300: addMortonRanges(list, min, max, len, level + 1);
301: max[largest] = temp;
302: temp = min[largest];
303: min[largest] = middle + 1;
304: addMortonRanges(list, min, max, len, level + 1);
305: min[largest] = temp;
306: }
307: }
308:
309: private int roundUp(int x, int blockSizePowerOf2) {
310: return (x + blockSizePowerOf2 - 1) & (-blockSizePowerOf2);
311: }
312:
313: private int findMiddle(int a, int b) {
314: int diff = b - a - 1;
315: if (diff == 0) {
316: return a;
317: }
318: if (diff == 1) {
319: return a + 1;
320: }
321: int scale = 0;
322: while ((1 << scale) < diff) {
323: scale++;
324: }
325: scale--;
326: int m = roundUp(a + 2, 1 << scale) - 1;
327: if (m <= a || m >= b) {
328: throw new Error("stop");
329: }
330: return m;
331: }
332:
333: }
|