crackers.mx

一个内存数据库的源代码这是服务器端还有客户端

@' The contents of this file are subject to the MonetDB Public License
@' Version 1.1 (the "License"); you may not use this file except in
@' compliance with the License. You may obtain a copy of the License at
@' http://monetdb.cwi.nl/Legal/MonetDBLicense-1.1.html
@'
@' Software distributed under the License is distributed on an "AS IS"
@' basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the
@' License for the specific language governing rights and limitations
@' under the License.
@'
@' The Original Code is the MonetDB Database System.
@'
@' The Initial Developer of the Original Code is CWI.
@' Portions created by CWI are Copyright (C) 1997-2007 CWI.
@' All Rights Reserved.

@f crackers
@a Martin Kersten, Stratos Idreos, Stefan Manegold
@d March 2006
@* Cracker index


StM: This text is obsolete as of April 26, 2006, and needs to be updated!


A cracker index is a volatile datastructure which acts as
a non-dense index into a BAT. The index is incrementally built
based on the fragments needed by queries.
Each select operation results in a partial re-clustering of the tuples
such that the result set is a consecutive memory area in the BAT.
This set can be returned as a BAT view for further processing.

A cracker index is created with the command @sc{crackers.new}
and destroyed using @sc{crackers.destroy}.
Multiple calls to create/destroy the cracker index on the same
argument are ignored.

The cracker index can be created for the time being on
tail columns of type {int,lng,dbl,flt,time}. The head
is always of type @sc{oid}.

Once a cracker index exist, portions can be extracted
using @sc{crackers.select} and @sc{crackers.uselect},
which semantically behave as their algebraic counterparts.
Both operations may have to glue pieces from the cracked
bat to satisfy the BAT semantics.

Qst: are these operators overloaded to initiate a crack
operation first?

In addition, the cracker index can be used to feed a generator
for pieces satisfying a range constraint.
A cracker partition is indicated by the index in the cidx
table. It can be used to initialize a BATview to represent
the partition during processing.

Repeated cracking leads to an ever growing index. This process
can be stopped by setting the granule size,
i.e.  the minimum number of tuples in each piece,
or the maximum number of pieces.
The operations @sc{crackers.setGranule()} and @sc{crackers.setLimit()}
implement them. The default is to allow an arbitrary number pieces
with arbitrary sizes.

Pitfalls.
The policy in the kernel to take a copy of a BAT when there
is a need to write to it and there are also views around becomes
an issue. Instead, it should isolate the views, giving them a
private copy. This way the underlying base table becomes free to re-arrange.
This issue is postponed to the future.

The cracker module should be prepared to deal with any of the base types.
For strings this becomes an issue.

This module contains the experimental code to play with cracked tables.
It supports int-based bats for the time being only.

The current implementation uses an unprotected cracker
index. This limits the interface at slightly more overhead
of searching the cracker index upon each call.

Initial performance indicates around 70 ms processing
overhead on a 1M bat during the first crack operation.
(Athlon 1400, 1Gb)

@= crackfcn
command printCrackerIndex(b:bat[:any_1,:@1]):void
address CRKprintCrackerIndex
comment "Print the cracker index of b";

command printCrackerBAT(b:bat[:any_1,:@1]):void
address CRKprintCrackerBAT
comment "Print the cracker BAT of b";

command getCrackerBAT(b:bat[:any_1,:@1]):bat[:oid,:@1]
address CRKgetCrackerBAT
comment "Get the cracker BAT of b";

command printCrackerInsertions(b:bat[:any_1,:@1]):void
address CRKprintCrackerInsertions
comment "Print the pending insertions of the cracker BAT of b";

command printCrackerDeletions(b:bat[:any_1,:@1]):void
address CRKprintCrackerDeletions
comment "Print the pending deletions of the cracker BAT of b";

command sizeCrackerInsertions(b:bat[:any_1,:@1]):void
address CRKsizeCrackerInsertions
comment "Get the size of the pending insertions of the cracker BAT of b";

command sizeCrackerDeletions(b:bat[:any_1,:@1]):void
address CRKsizeCrackerDeletions
comment "Get the size of the pending deletions of the cracker BAT of b";

command insertionsForget(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeInsertions_Forget
comment "Append c to the cracked bat of b and completelly forget the cracker index";

command insertionsPartiallyForget(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeInsertions_PartiallyForget_@1
comment "Append c to the cracked bat of b and partially forget the cracker index, i.e., forget only what is affected";

command insertionsForce(b:bat[:any_1,:@1], c:bat[:any_1,:@1], deleteNodes:bit):void
address CRKmergeInsertions_Force_@1
comment "Merge the insertions bat with the cracker bat and update the cracker index";

command insertionsBForce(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeInsertionsB_Force_@1
comment "Merge the insertions bat with the cracker bat and update the cracker index";

command insertionsOnNeed(b:bat[:any_1,:@1], c:bat[:any_1,:@1], deleteNodes:bit):void
address CRKmergeInsertions_OnNeed
comment "Keep the insertions bat separatelly and do a complete merge only if a relevant query arrives in the future";

command insertionsBOnNeed(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeInsertionsB_OnNeed
comment "Keep the insertions bat separatelly and do a complete merge only if a relevant query arrives in the future";

command insertionsOnNeedGradually(b:bat[:any_1,:@1], c:bat[:any_1,:@1], deleteNodes:bit):void
address CRKmergeInsertions_OnNeedGradually
comment "Keep the insertions bat separatelly and merge only what is needed if a relevant query arrives in the future";

command insertionsBOnNeedGradually(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeInsertionsB_OnNeedGradually
comment "Keep the insertions bat separatelly and merge only what is needed if a relevant query arrives in the future";

command insertionsOnNeedGraduallyRipple(b:bat[:any_1,:@1], c:bat[:any_1,:@1], deleteNodes:bit):void
address CRKmergeInsertions_OnNeedGraduallyRipple
comment "Keep the insertions bat separatelly and merge only what is needed using the ripple strategy if a relevant query arrives in the future";

command insertionsBOnNeedGraduallyRipple(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeInsertionsB_OnNeedGraduallyRipple
comment "Keep the insertions bat separatelly and merge only what is needed using the ripple strategy if a relevant query arrives in the future";

command deletionsOnNeed(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeDeletions_OnNeed
comment "Keep the deletions bat separatelly and do a complete merge only if a relevant query arrives in the future";

command deletionsOnNeedGradually(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeDeletions_OnNeedGradually
comment "Keep the deletions bat separatelly and merge only what is needed if a relevant query arrives in the future";

command deletionsOnNeedGraduallyRipple(b:bat[:any_1,:@1], c:bat[:any_1,:@1]):void
address CRKmergeDeletions_OnNeedGraduallyRipple
comment "Keep the deletions bat separatelly and merge only what is needed using ripple if a relevant query arrives in the future";

command verifyCrackerIndex(b:bat[:any_1,:@1]):void
address CRKverifyCrackerIndex_@1
comment "Check the cracker index and column, whether each value is in the correct chunk";

command extendCrackerBAT(b:bat[:any_1,:@1], P:lng):void
address CRKextendCrackerBAT
comment "extend the cracker column by P positions";

command printAVLTree_int(b:bat[:any_1,:@1]):void
address CRKprintAVLTree_int
comment "print the AVL Tree";

command buildAVLIndex(b:bat[:any_1,:@1]):void
address CRKmakeAVLIndex_@1
comment "make an AVL tree index for this BAT";

command InsertAVLIndex(b:bat[:any_1,:@1], u:bat[:any_1,:@1]):void
address CRKInsertAVLIndex_@1
comment "Insert u in the AVL tree index of BAT b";

command selectAVL(b:bat[:any_1,:@1],l:any_2,h:any_3,li:any_4,hi:any_5):bat[:any_6,:@1]
address CRKAVLIndexSelectBounds_@1
comment "Retrieve the subset using the AVL index";

command deleteAVL(b:bat[:any_1,:@1],u:bat[:any_2,:@1]):void
address CRKdeleteFromAVL_@1
comment "Delete a collection of values from the index";

@

@mal
module crackers;

@:crackfcn(chr)@
@:crackfcn(sht)@
@:crackfcn(int)@
@:crackfcn(lng)@
@:crackfcn(flt)@
@:crackfcn(dbl)@
@:crackfcn(date)@

@-

A limited set of relational operators is overloaded to deal with
cracked BATs. The relational select collects the pieces
into a single BAT. Preferably using a BATview, otherwise
the pieces are combined to form a new BAT.

@= crackAlgebra
command select(b:bat[:any_1,:@1],l:@1,h:@1):bat[:any_2,:@1]
address CRKselect_@1
comment "Retrieve the subset using a cracker
        index producing preferably a BATview.";

command select(b:bat[:any_1,:@1],l:@1):bat[:any_2,:@1]
address CRKselectValue_@1
comment "Retrieve the subset using a cracker
        index producing preferably a BATview.";

command select(b:bat[:any_1,:@1],l:any_2,h:any_3,li:any_4,hi:any_5):bat[:any_6,:@1]
address CRKselectBounds_@1
comment "Retrieve the subset using a cracker
        index producing preferably a BATview.";

command uselect(b:bat[:any_1,:@1],l:@1,h:@1):bat[:any_2,:void]
address CRKuselect_@1
comment "Retrieve the subset using a cracker
        index producing preferably a BATview.";

command uselect(b:bat[:any_1,:@1],l:@1):bat[:any_2,:void]
address CRKuselectValue_@1
comment "Retrieve the subset using a cracker
        index producing preferably a BATview.";

command uselect(b:bat[:any_1,:@1],l:any_2,h:any_3,li:any_4,hi:any_5):bat[:any_6,:void]
address CRKuselectBounds_@1
comment "Retrieve the subset using a cracker
        index producing preferably a BATview.";

@:joinuselect(@1,v,v)@
@:joinuselect(@1,v,)@
@:joinuselect(@1,,v)@
@:joinuselect(@1,,)@
@
@= joinuselect
command joinuselect( right:bat[:@2oid,:@1], l:@1, h:@1, li:bit, hi:bit, left:bat[:@3oid,:void] ):bat[:oid,:void]
address CRKjoinSelectDefault_@1
comment "Join left and right on head-OIDs.
	From right, only those BUNs qualify that satisfy the range-restriction on the tail.
	The result is a new [:oid,:void] BAT.";

command joinuselect( right:bat[:@2oid,:@1], l:@1, h:@1, li:bit, hi:bit, left:bat[:@3oid,:void], inPlace:bit , isForeignKey:bit):bat[:oid,:void]
address CRKjoinSelectBounds_@1
comment "Join left and right on head-OIDs.
	From right, only those BUNs qualify that satisfy the range-restriction on the tail.
	If inPlace is TRUE (and left has an OID head and is not a BAT-view), we operate in-place,
	overwriting left and returning it as result. Otherwise, the result is a new [:oid,:void] BAT.
	If isForeignKey is TRUE, we assume that each tuple from left finds a match in right,
	and hence skip the respective check.
	(NOTE: This may lead to CRASHES, if isForeignKey is incorrectly passed as TRUE!)";
@
@mal
@:crackAlgebra(chr)@
@:crackAlgebra(sht)@
@:crackAlgebra(int)@
@:crackAlgebra(lng)@
@:crackAlgebra(flt)@
@:crackAlgebra(dbl)@
@:crackAlgebra(date)@

@-
Direct access to the core cracking routines for cracking a complete BAT;
mainly for testing/debugging.
@
@= crackO
command zcrackOrdered (b:bat[:oid,:@1], mid:@1) :bat[:oid,:@1]
address CRKcrackOrderedZero_@1
comment "Break a BAT into two pieces with
	 tail<=mid, tail>mid,
	 respectively; maintaining the head-oid order within each piece.";

command crackOrdered (b:bat[:oid,:@1], mid:@1) :bat[:oid,:@1]
address CRKcrackOrderedOne_@1
comment "Break a BAT into three pieces with
	 tail<mid, tail==mid, tail>mid,
	 respectively; maintaining the head-oid order within each piece.";

command crackOrdered (b:bat[:oid,:@1], low:@1, hgh:@1) :bat[:oid,:@1]
address CRKcrackOrderedTwo_@1
comment "Break a BAT into five pieces with
	 tail<low, tail==low, low<tail<hgh, tail==hgh, tail>hgh,
	 respectively; maintaining the head-oid order within each piece.";

command zcrackOrdered (b:bat[:oid,:@1], low:@1, hgh:@1) :bat[:oid,:@1]
address CRKcrackOrderedThree_@1
comment "Break a BAT into three pieces with
	 tail<=low, low<tail<=hgh, tail>hgh,
	 respectively; maintaining the head-oid order within each piece.";

@
@= crack
command zcrackUnordered (b:bat[:oid,:@1], mid:@1) :bat[:oid,:@1]
address CRKcrackUnorderedZero_@1
comment "Break a BAT into two pieces with
	 tail<=mid, tail>mid,
	 respectively.";

command zcrackUnordered (b:bat[:oid,:@1], low:@1, hgh:@1) :bat[:oid,:@1]
address CRKcrackUnorderedThree_@1
comment "Break a BAT into three pieces with
	 tail<=low, low<tail<=hgh, tail>hgh,
	 respectively.";
@
@= crack_validate
command zcrackOrdered_validate (b:bat[:oid,:@1], mid:@1) :bit
address CRKcrackOrderedZero_validate_@1
comment "Validate whether a BAT is correctly broken into two pieces with
	 tail<=mid, tail>mid,
	 respectively; maintaining the head-oid order within each piece.";

command crackOrdered_validate (b:bat[:oid,:@1], mid:@1) :bit
address CRKcrackOrderedOne_validate_@1
comment "Validate whether a BAT is correctly broken into three pieces with
	 tail<mid, tail==mid, tail>mid,
	 respectively; maintaining the head-oid order within each piece.";

command crackOrdered_validate (b:bat[:oid,:@1], low:@1, hgh:@1) :bit
address CRKcrackOrderedTwo_validate_@1
comment "Validate whether a BAT is correctly broken into five pieces with
	 tail<low, tail==low, low<tail<hgh, tail==hgh, tail>hgh,
	 respectively; maintaining the head-oid order within each piece.";

command zcrackOrdered_validate (b:bat[:oid,:@1], low:@1, hgh:@1) :bit
address CRKcrackOrderedThree_validate_@1
comment "Validate whether a BAT is correctly broken into three pieces with
	 tail<=low, low<tail<=hgh, tail>hgh,
	 respectively; maintaining the head-oid order within each piece.";

command zcrackUnordered_validate (b:bat[:oid,:@1], mid:@1) :bit
address CRKcrackUnorderedZero_validate_@1
comment "Validate whether a BAT is correctly broken into two pieces with
	 tail<=mid, tail>mid,
	 respectively.";

command zcrackUnordered_validate (b:bat[:oid,:@1], low:@1, hgh:@1) :bit
address CRKcrackUnorderedThree_validate_@1
comment "Validate whether a BAT is correctly broken into three pieces with
	 tail<=low, low<tail<=hgh, tail>hgh,
	 respectively.";
@
@mal
@:crack(chr)@
@:crack(sht)@
@:crack(int)@
@:crack(lng)@
@:crack(flt)@
@:crack(dbl)@
@:crack(date)@
@:crackO(chr)@
@:crackO(sht)@
@:crackO(int)@
@:crackO(lng)@
@:crackO(flt)@
@:crackO(dbl)@
@:crack_validate(chr)@
@:crack_validate(sht)@
@:crack_validate(int)@
@:crack_validate(lng)@
@:crack_validate(flt)@
@:crack_validate(dbl)@
@-
@{
@- include prelude.mx
@* Implementation
The implementation is geared at early experimentation
without all the details to make the code robust and
ultra fast.

@h
#ifndef _CRACKERS_H_
#define _CRACKERS_H_

/*#define DEBUG_CRACKERS*/
/*#define DEBUG_CRACKERS_INSERTIONS*/

#ifdef WIN32
#ifndef LIBCRACKERS
#define crackers_export extern __declspec(dllimport)
#else
#define crackers_export extern __declspec(dllexport)
#endif
#else
#define crackers_export extern
#endif

typedef struct {
	int bid;   /* the cracked bat */
	int cbid;  /* the copy on which we actually crack */
	int cid;   /* the index for this cracked bat */
} CrackIndex;

struct Node{
        lng	      position;
	bit 	      inclusive;	
        struct Node  *left;
        struct Node  *right;
        int	      height;
	bit	      head;
	bit	      deleted;
        struct Node  *previous;
	bit 	      isPreviousSmaller;	
	lng	      hols; /* indicates how many hols exist before this piece */
};

typedef struct {
	int 		bid;   		/* the stable bat */
	int 		cbid;   	/* the cracker bat, i.e., the copy on which we actually crack */
	int 		cid;   		/* the index for this cracked bat */
	int 		iid;   		/* pending insertions bat */
	int 		did;   		/* pending deletions bat */
	struct Node 	*Tree; 		/* the AVL tree */
	bit		reCreate;	/* indicates whether we need to recreate the index if we chose to forget it */
	sht		mergeInsertions;/* indicates wether there are insertions to merge -->  -1 no insertions,
												0 complete merge,
												1 gradually,
												2 ripple */
	bit 		deleteNodes;    /* if true, merging operations will delete nodes form the index if it makes things easier */
	bit 		mergeFromTheEnd;
	sht		mergeDeletions; /* indicates wether there are insertions to merge -->  -1 no insertions,
												0 complete merge,
												1 gradually,
												2 ripple */
} CrackTreeIndex;

typedef struct {
	int		bid;
	struct Node 	*Tree;	
} AVLTreeIndex;

crackers_export str CRKselect(int *vid, int *bid, int *low, int *hgh);
crackers_export str CRKselectValue(int *vid, int *bid, int *value);
crackers_export str CRKuselect(int *vid, int *bid, int *low, int *hgh);
crackers_export str CRKuselectValue(int *vid, int *bid, int *value);

crackers_export str CRKprintCrackerIndex(int *k, int *bid);
crackers_export str CRKprintCrackerBAT(int *k, int *bid);
crackers_export str CRKgetCrackerBAT(int *vid, int *bid);
crackers_export str CRKsizeCrackerInsertions(int *k, int *bid);
crackers_export str CRKsizeCrackerDeletions(int *k, int *bid);
crackers_export str CRKprintCrackerInsertions(int *k, int *bid);
crackers_export str CRKprintCrackerDeletions(int *k, int *bid);