Index


1   /* =============================================================
2    * SmallSQL : a free Java DBMS library for the Java(tm) platform
3    * =============================================================
4    *
5    * (C) Copyright 2004-2006, by Volker Berlin.
6    *
7    * Project Info:  http://www.smallsql.de/
8    *
9    * This library is free software; you can redistribute it and/or modify it 
10   * under the terms of the GNU Lesser General Public License as published by 
11   * the Free Software Foundation; either version 2.1 of the License, or 
12   * (at your option) any later version.
13   *
14   * This library is distributed in the hope that it will be useful, but 
15   * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 
16   * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 
17   * License for more details.
18   *
19   * You should have received a copy of the GNU Lesser General Public
20   * License along with this library; if not, write to the Free Software
21   * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, 
22   * USA.  
23   *
24   * [Java is a trademark or registered trademark of Sun Microsystems, Inc. 
25   * in the United States and other countries.]
26   *
27   * ---------------
28   * Index.java
29   * ---------------
30   * Author: Volker Berlin
31   * 
32   */
33  package smallsql.database;
34  
35  import java.sql.SQLException  ;
36  import java.util.ArrayList  ;
37  
38  
39  /**
40   * To index data there need to solv the follow problems
41   * - change the values that need to save in the index to a value with sort order that is compatible
42   *   with the index algorithmus.
43   * - multiple column index need to support. There should no identical save with combinations of values.
44   * - The data type for column should be const.
45   * - the data need to save fast.
46   * - the size of the index should be small (also with a small count of values)
47   * - It should use for unique index and nor unique. The unique index can save only one rowOffset.
48   *   The non unique can save multiple rowOffsets in a LongTreeList.
49   * - Problem ORDER BY with Joins? There are more as one rowOffset per row.
50   * 
51   * 
52   * Algorithmus:
53   * - convert the values that the binary order is equals to the value order. We need to handle
54   *   sign, floating numbers, case insensitive, different binary length (MutableNumeric).
55   * - create a 256 byte large mask for the first byte.
56   * - create a 256 byte large status mask
57   * - create a 256 large Object array
58   * 
59   * 
60   * @author Volker Berlin
61   *
62   */
63  class Index{
64  
65      final IndexNode rootPage;
66      
67      /**
68       * Create an Index in the memory. An Index is like a sorted list.
69       * @param unique true if there are no duplicated values allow.
70       */
71      Index(boolean unique){
72          rootPage = new IndexNode(unique, (char)-1);
73      }
74      
75      
76      Index(IndexNode rootPage){
77          this.rootPage = rootPage;
78      }
79      
80      
81      IndexScrollStatus createScrollStatus(Expressions expressions){
82          return new IndexScrollStatus(rootPage, expressions);
83      }
84      
85      /**
86       * Returns a Long (unigue) or a LongTreeList with rowOffsets. If the value in expressions
87       * does not exist then it return a null.
88       * @param expressions The value that are search in the Index.
89       */
90      final Object   findRows( Expressions expressions, ArrayList   nodeList ) throws Exception  {
91          IndexNode page = rootPage;
92          int count = expressions.size();
93          for(int i=0; i<count; i++){
94              page = findRows( page, expressions.get(i), nodeList);       
95              if(page == null)
96                  return null;
97              if(i+1 == count)
98                  return page.getValue();
99              else
100                 page = (IndexNode)page.getValue();          
101         }
102         throw new Error  ();
103     }
104     
105     
106     /**
107      * Returns a Long (unigue) or a LongTreeList with rowOffsets. If the value in expressions
108      * does not exist then it return a null.
109      * @param expressions The value that are search in the Index.
110      */
111     final Object   findRows( Expression[] expressions, ArrayList   nodeList ) throws Exception  {
112         IndexNode page = rootPage;
113         int count = expressions.length;
114         for(int i=0; i<count; i++){
115             page = findRows( page, expressions[i], nodeList);       
116             if(page == null)
117                 return null;
118             if(i+1 == count)
119                 return page.getValue();
120             else
121                 page = (IndexNode)page.getValue();          
122         }
123         throw new Error  ();
124     }
125     
126     
127     /** Return the last IndexNode for the expression */
128     final private IndexNode findRows(IndexNode page, Expression expr, ArrayList   nodeList) throws Exception  {
129             if(expr.isNull()){
130                 page = findNull(page);
131             }else{
132                 switch(expr.getDataType()){
133                     case SQLTokenizer.REAL:
134                         page = find( page, floatToBinarySortOrder( expr.getFloat()), 2, nodeList );
135                         break;
136                     case SQLTokenizer.DOUBLE:
137                     case SQLTokenizer.FLOAT:
138                         page = find( page, doubleToBinarySortOrder( expr.getDouble()), 4, nodeList );
139                         break;
140                     case SQLTokenizer.TINYINT:
141                         page = find( page, expr.getInt(), 1, nodeList );
142                         break;
143                     case SQLTokenizer.SMALLINT:
144                         page = find( page, shortToBinarySortOrder( expr.getInt()), 1, nodeList );
145                         break;
146                     case SQLTokenizer.INT:
147                         page = find( page, intToBinarySortOrder( expr.getInt()), 2, nodeList );
148                         break;
149                     case SQLTokenizer.BIGINT:
150                     case SQLTokenizer.DATE:
151                     case SQLTokenizer.TIME:
152                     case SQLTokenizer.TIMESTAMP:
153                     case SQLTokenizer.SMALLDATETIME:
154                     case SQLTokenizer.MONEY:
155                     case SQLTokenizer.SMALLMONEY:
156                         page = find( page, longToBinarySortOrder( expr.getLong()), 4, nodeList );
157                         break;
158                     case SQLTokenizer.VARCHAR:
159                     case SQLTokenizer.NVARCHAR:
160                     case SQLTokenizer.LONGVARCHAR:
161                     case SQLTokenizer.LONGNVARCHAR:
162                     case SQLTokenizer.CLOB:
163                         page = find( page, stringToBinarySortOrder( expr.getString(), false ), nodeList );
164                         break;
165                     case SQLTokenizer.NCHAR:
166                     case SQLTokenizer.CHAR:
167                         page = find( page, stringToBinarySortOrder( expr.getString(), true ), nodeList );
168                         break;
169                     case SQLTokenizer.VARBINARY:
170                     case SQLTokenizer.BINARY:
171                     case SQLTokenizer.LONGVARBINARY:
172                     case SQLTokenizer.BLOB:
173                     case SQLTokenizer.UNIQUEIDENTIFIER:
174                         page = find( page, bytesToBinarySortOrder( expr.getBytes()), nodeList );
175                         break;
176                     case SQLTokenizer.BIT:
177                     case SQLTokenizer.BOOLEAN:
178                         page = find( page, expr.getBoolean() ? 2 : 1, 1, nodeList );
179                         break;
180                     case SQLTokenizer.NUMERIC:
181                     case SQLTokenizer.DECIMAL:                      
182                         page = find( page, numericToBinarySortOrder( expr.getNumeric() ), nodeList );
183                         break;
184                     default: 
185                         //TODO weitere Datentypen
186                         throw new Error  (String.valueOf(expr.getDataType()));
187                 }
188             }
189             return page;
190     }
191 
192     
193     /**
194      * Add a value to the index.
195      * @param rowOffset Is the value that is save in the index. It is typical a row number or a rowOffset.
196      * @param expressions This is the list of ORDER BY columns and descript the position in the index.
197      */
198     final void addValues( long rowOffset, Expressions expressions ) throws Exception  {
199         IndexNode page = this.rootPage;
200         int count = expressions.size();
201         for(int i=0; i<count; i++){
202             Expression expr = expressions.get(i);
203             boolean isLastValues = (i == count-1);
204             if(expr.isNull()){
205                 page = addNull(page, rowOffset, isLastValues);
206             }else{
207                 switch(expr.getDataType()){
208                     case SQLTokenizer.REAL:
209                         page = add( page, rowOffset, floatToBinarySortOrder( expr.getFloat()), isLastValues, 2 );
210                         break;
211                     case SQLTokenizer.DOUBLE:
212                     case SQLTokenizer.FLOAT:
213                         page = add( page, rowOffset, doubleToBinarySortOrder( expr.getDouble()), isLastValues, 4 );
214                         break;
215                     case SQLTokenizer.TINYINT:
216                         page = add( page, rowOffset, expr.getInt(), isLastValues, 1 );
217                         break;
218                     case SQLTokenizer.SMALLINT:
219                         page = add( page, rowOffset, shortToBinarySortOrder( expr.getInt()), isLastValues, 1 );
220                         break;
221                     case SQLTokenizer.INT:
222                         page = add( page, rowOffset, intToBinarySortOrder( expr.getInt()), isLastValues, 2 );
223                         break;
224                     case SQLTokenizer.BIGINT:
225                     case SQLTokenizer.DATE:
226                     case SQLTokenizer.TIME:
227                     case SQLTokenizer.TIMESTAMP:
228                     case SQLTokenizer.SMALLDATETIME:
229                     case SQLTokenizer.MONEY:
230                     case SQLTokenizer.SMALLMONEY:
231                         page = add( page, rowOffset, longToBinarySortOrder( expr.getLong()), isLastValues, 4 );
232                         break;
233                     case SQLTokenizer.VARCHAR:
234                     case SQLTokenizer.NVARCHAR:
235                     case SQLTokenizer.LONGVARCHAR:
236                     case SQLTokenizer.LONGNVARCHAR:
237                         page = add( page, rowOffset, stringToBinarySortOrder( expr.getString(), false ), isLastValues );
238                         break;
239                     case SQLTokenizer.NCHAR:
240                     case SQLTokenizer.CHAR:
241                         page = add( page, rowOffset, stringToBinarySortOrder( expr.getString(), true ), isLastValues );
242                         break;
243                     case SQLTokenizer.VARBINARY:
244                     case SQLTokenizer.BINARY:
245                     case SQLTokenizer.LONGVARBINARY:
246                     case SQLTokenizer.BLOB:
247                     case SQLTokenizer.UNIQUEIDENTIFIER:
248                         page = add( page, rowOffset, bytesToBinarySortOrder( expr.getBytes()), isLastValues );
249                         break;
250                     case SQLTokenizer.BIT:
251                     case SQLTokenizer.BOOLEAN:
252                         page = add( page, rowOffset, expr.getBoolean() ? 2 : 1, isLastValues, 1 );
253                         break;
254                     case SQLTokenizer.NUMERIC:
255                     case SQLTokenizer.DECIMAL:
256                         page = add( page, rowOffset, numericToBinarySortOrder( expr.getNumeric()), isLastValues );
257                         break;
258                     default: 
259                         //TODO weitere Datentypen
260                         throw new Error  (String.valueOf(expr.getDataType()));
261                 }
262             }
263         }       
264     }
265     
266     
267     final void removeValue( long rowOffset, Expressions expressions ) throws Exception  {
268         ArrayList   nodeList = new ArrayList  ();
269         Object   obj = findRows(expressions, nodeList);
270         if(!rootPage.getUnique()){
271             LongTreeList list = (LongTreeList)obj;
272             list.remove(rowOffset);
273             if(list.getSize() > 0) return;
274         }
275         IndexNode node = (IndexNode)nodeList.get(nodeList.size()-1);
276         node.clearValue();
277         for(int i = nodeList.size()-2; i >= 0; i--){
278             if(!node.isEmpty())
279                 break;
280             IndexNode parent = (IndexNode)nodeList.get(i);
281             parent.removeNode( node.getDigit() );
282             node = parent;
283         }
284     }
285     
286     
287     final private IndexNode findNull(IndexNode page){
288         return page.getChildNode( (char)0 );
289     }
290     
291 
292     final private IndexNode addNull(IndexNode page, long rowOffset, boolean isLastValue) throws SQLException  {
293         if(isLastValue){
294             page.addNode( (char)0, rowOffset );
295             return null;
296         }else
297             return page.addRoot((char)0);
298     }
299 
300     
301     final private IndexNode find(IndexNode node, long key, int digitCount, ArrayList   nodeList){
302         for(int i=digitCount-1; i>=0; i--){
303             char digit = (char)(key >> (i<<4));
304             node = node.getChildNode(digit);
305             
306             if(node == null) return null;
307             if(nodeList != null) nodeList.add(node);
308 
309             if(equals(node.getRemainderValue(), key, i)){
310                 return node;
311             }
312         }
313         return node;
314     }
315     
316     
317     /**
318      * The key has a binary sort order. This means the most significate byte is in the high byte.
319      * @param digitCount The count of 16Bit digits.
320      */
321     final private IndexNode add(IndexNode node, long rowOffset, long key, boolean isLastValue, int digitCount) throws SQLException  {
322         for(int i=digitCount-1; i>=0; i--){
323             char digit = (char)(key >> (i<<4));
324             if(i == 0){
325                 if(isLastValue){
326                     node.addNode( digit, rowOffset );
327                     return null;
328                 }
329                 return node.addRoot(digit);
330             }
331             node = node.addNode(digit);
332             if(node.isEmpty()){
333                 if(isLastValue){
334                     node.addRemainderKey( rowOffset, key, i );
335                     return null;
336                 }
337                 return node.addRootValue( key, i);
338             }else
339             if(equals(node.getRemainderValue(), key, i)){
340                 if(isLastValue){
341                     node.saveValue( rowOffset);
342                     return null;
343                 }
344                 return node.addRoot();
345             }       
346         }
347         throw new Error  ();
348     }
349     
350     
351     final private IndexNode find(IndexNode node, char[] key, ArrayList   nodeList){
352         int length = key.length;
353         int i=-1;
354         while(true){
355             // the first digit include 0-null; 1-empty; 2 another value
356             char digit = (i<0) ? (length == 0 ? (char)1 : 2)
357                               : (key[i]);
358             node = node.getChildNode(digit);
359 
360             if(node == null) return null;
361             if(nodeList != null) nodeList.add(node);
362             if(++i == length){
363                 return node;
364             }
365 
366             if(equals(node.getRemainderValue(), key, i)){
367                 return node;
368             }
369         }
370     }
371     
372     
373     /**
374      * Add a byte array to the Index.
375      */
376     final private IndexNode add(IndexNode node, long rowOffset, char[] key, boolean isLast) throws SQLException  {
377         int length = key.length;
378         int i=-1;
379         while(true){
380             // the first digit include 0-null; 1-empty; 2 another value
381             char digit = (i<0) ? (length == 0 ? (char)1 : 2)
382                               : (key[i]);
383             if(++i == length){
384                 if(isLast){
385                     node.addNode( digit, rowOffset );
386                     return null;
387                 }
388                 return node.addRoot(digit);
389             }
390             node = node.addNode(digit);
391             if(node.isEmpty()){
392                 if(isLast){
393                     node.addRemainderKey( rowOffset, key, i );
394                     return null;
395                 }
396                 return node.addRootValue( key, i );
397             }else
398             if(equals(node.getRemainderValue(), key, i)){
399                 if(isLast){
400                     node.saveValue(rowOffset);
401                     return null;
402                 }
403                 return node.addRoot();
404             }
405         }
406     }
407     
408     
409     /**
410      * Remove all enties
411      */
412     final void clear(){
413         rootPage.clear();
414     }
415     /*================================================================
416      * Normalize functions
417      * convert the value to a binary with identical sort order 
418      * like the orginal values. 
419      ================================================================*/
420     
421     
422     final static private int floatToBinarySortOrder(float value){
423         int intValue = Float.floatToIntBits(value);
424         return (intValue<0) ?
425             ~intValue :
426             intValue ^ 0x80000000;          
427     }
428     
429     final static private long doubleToBinarySortOrder(double value){
430         long intValue = Double.doubleToLongBits(value);
431         return (intValue<0) ?
432             ~intValue :
433             intValue ^ 0x8000000000000000L;         
434     }
435     
436     final static private int shortToBinarySortOrder(int value){
437         return value ^ 0x8000;
438     }
439     
440     final static private int intToBinarySortOrder(int value){
441         return value ^ 0x80000000;
442     }
443     
444     final static private long longToBinarySortOrder(long value){
445         return value ^ 0x8000000000000000L;
446     }
447     
448     
449     final static private char[] stringToBinarySortOrder(String   value, boolean needTrim){
450         int length = value.length();
451         if(needTrim){
452             while(length > 0 && value.charAt(length-1) == ' ') length--;
453         }
454         char[] puffer = new char[length];
455         for(int i=0; i<length; i++){
456             puffer[i] = Character.toLowerCase(Character.toUpperCase( value.charAt(i) ));
457         }
458         return puffer;
459     }
460     
461     
462     final static private char[] bytesToBinarySortOrder(byte[] value){
463         int length = value.length;
464         char[] puffer = new char[length];
465         for(int i=0; i<length; i++){
466             puffer[i] = (char)(value[i] & 0xFF);
467         }
468         return puffer;
469     }
470     
471     
472     final static private char[] numericToBinarySortOrder(MutableNumeric numeric){
473         int[] value = numeric.getInternalValue();
474         int count = 1;
475         int i;
476         for(i=0; i<value.length; i++){
477             if(value[i] != 0){
478                 count = 2*(value.length - i)+1;
479                 break;
480             }
481         }
482         char[] puffer = new char[count];
483         puffer[0] = (char)count;
484         for(int c=1; c<count;){
485             puffer[c++] = (char)(value[i] >> 16);
486             puffer[c++] = (char)value[i++];
487         }
488         return puffer;
489     }
490     
491     
492     /*================================================================
493      * 
494      * Functions  for reading the index.
495      *
496      ================================================================*/
497     
498     
499     
500     private final boolean equals(char[] src1, char[] src2, int offset2){
501         if(src1 == null) return false;
502         int length = src1.length;
503         if(length != src2.length - offset2) return false;
504         for(int i=0; i<length; i++){
505             if(src1[i] != src2[i+offset2]) return false;
506         }
507         return true;
508     }
509     
510 
511     private final boolean equals(char[] src1, long src2, int charCount){
512         if(src1 == null) return false;
513         int length = src1.length;
514         if(length != charCount) return false;
515         for(int i=0, d = charCount-1; i<length; i++){
516             if(src1[i] != (char)((src2 >> (d-- << 4)))) return false;
517         }
518         return true;
519     }
520 }
521
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags