algebra.mx

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

		not match an head-value in 'inner'.";
command outerjoin( outer:bat[:any_1,:oid], inner:bat[:oid,:any_3]) 
		:bat[:any_1,:any_3] 
address ALGouterjoin
comment "Returns all the result of a join, plus the BUNS formed NIL in 
		the tail and the head-values of 'outer' whose tail-value does 
		not match an head-value in 'inner'.";
command outerjoin( outer:bat[:any_1,:oid], inner:bat[:oid,:any_3]) 
		:bat[:any_1,:any_3] 
address ALGouterjoin
comment "Returns all the result of a join, plus the BUNS formed NIL in 
		the tail and the head-values of 'outer' whose tail-value does 
		not match an head-value in 'inner'.";

command outerjoin( outer:bat[:any_1,:any_2], inner:bat[:any_2,:any_3],
		estimate:lng) :bat[:any_1,:any_3] 
address ALGouterjoinestimate;

@- Theta Join
@mal
command thetajoin( left:bat[:any_1,:any_2], right:bat[:any_2,:any_3],
		opname:int) :bat[:any_1,:any_3] 
address ALGthetajoin
comment "Theta join on for 'mode' in { LE, LT, EQ, GT, GE }.  JOIN_EQ is 
		just the same as join(). All other options do merge algorithms. 
		Either using the fact that they are ordered() already (left on tail, 
	right on head), or by using/creating binary search trees on the 
		join columns. ";

command thetajoin( left:bat[:any_1,:any_2], right:bat[:any_2,:any_3],
		opname:int,estimate:lng) :bat[:any_1,:any_3] 
address ALGthetajoinEstimate;
@- Band Join (approximate match)
@mal
command bandjoin( outer:bat[:any_1,:any_2], inner:bat[:any_2,:any_3],
		   minus:any_2 , plus:any_2 ) :bat[:any_1,:any_3] 
address ALGbandjoin
comment "This is a join() for which the predicate is that two BUNs match 
		if the left-tail value is within the range [right-head - minus, 
		right-head + plus]. Works only for the builtin numerical types, 
		and their derivates.";
@+ Projection operations
@mal
command project(b:bat[:any_1,:any_2]) :bat[:any_1,:oid]
address ALGprojectNIL
comment "Extract the head of a BAT.";

@= projectGrp
command project(v:@1,b:bat[:any_2,:any_1]) :bat[:@1,:any_1] 
address ALGprojecthead_@1
comment "Fill the head with a constant, e.g. [0~b]";
command project(b:bat[:any_2,:any_1],v:@1) :bat[:any_2,:@1] 
address ALGprojecttail_@1
comment "Fill the tail with a constant, e.g. [0~b]";
@mal
	@:projectGrp(bit)@
	@:projectGrp(chr)@
	@:projectGrp(str)@
	@:projectGrp(oid)@
	@:projectGrp(int)@
	@:projectGrp(sht)@
	@:projectGrp(lng)@
	@:projectGrp(flt)@
	@:projectGrp(dbl)@
@+ OID Introducing Commands
For relational processing, some operators are necessary to produce newly
initiated OID columns, for representing n-ary (intermediary) relations.

@mal
command markT( b:bat[:any_1,:any_2], base:oid ) :bat[:any_1,:oid] 
address ALGtmark
comment "Produces a BAT with fresh unique dense sequense of OIDs in 
		the tail that starts at base (i.e. [base,..base+b.count()-1] ).";

command markT( b:bat[:any_1,:any_2] ) :bat[:any_1,:oid] 
address ALGtmark_default
comment "Produces a BAT with fresh unique OIDs in the tail starting at 0@0.";


command markH( b:bat[:any_1,:any_2] ) :bat[:oid,:any_2] 
address ALGmarkHead_default
comment "Produces a BAT with fresh OIDs in the head starting at 0@0.";

command markH( b:bat[:any_1,:any_2], base:oid ) :bat[:oid,:any_2] 
address ALGmarkHead
comment "Produces a new BAT with fresh unique dense sequense of OIDs in 
		the head that starts at base (i.e. [base,..base+b.count()-1] ).";

command number( b:bat[:any_1,:any] ) :bat[:any_1,:int]  
address ALGnumber
comment "Produces a new BAT with identical head column, and consecutively 
		increasing integers (start at 0) in the tail column.";

command merge(b:bat[:oid,:oid]):bat[:lng,:oid]
address ALGmerge
comment "Merge head and tail into a single value";

command split(b:bat[:lng,:oid]):bat[:oid,:oid]
address ALGsplit
comment "Split head into two values";

@+ BAT fragmentation commands
Various operations for splitting BATs into useful fragments.

@- Variable management
It is sometimes needed to cast a type at runtime
@mal
command materialize(b:bat[:oid,:any_1]):bat[:oid,:any_1]
address ALGmaterialize
comment "Materialize the void column";

command reuse(b:bat[:any_1,:any_2]):bat[:any_1,:any_2]
address ALGreuse
comment "Reuse a temporary BAT if you can. Otherwise,
	allocate enough storage to accept result of an
 	operation (not involving the heap)";

@- Hash Split
The commands below is temporarilly postponed, because
we don;t handle nested bats
@mal
command hashsplit( b:bat[:any_1,:any_2], buckects:int ) 
		:bat[:int,:bat] 
address ALGhashsplit
comment "Split a BAT on tail column according (hash-value MOD buckets). 
		Returns a recursive BAT, containing the fragments in the tail, 
		their bucket number in the head.";

command uhashsplit ( b:bat[:any_1,:any_2], buckets:int ) :bat[:int,:bat] 
address ALGuhashsplit
comment "Same as hashsplit, but only collect the head values in the fragments";
@- Range Split
@mil
command rangesplit ( b:bat[:any_1,:any_2], ranges:int ) 
		:bat[:any_2,bat[:any_1,:any_2]] 
address ALGrangesplit
comment "Split a BAT on tail column in 'ranges' equally sized consecutive 
		ranges. Returns a recursive BAT, containing the fragments in the tail, 
		the higher-bound of the range in the head. The higher bound of the last 
	range is 'nil'.";

command urangesplit( b:bat[:any_1,:any_2], ranges:int ) 
		:bat[:any_2,bat[:any_1,:oid]] 
address ALGurangesplit
comment "Same as rangesplit, but only collect the head values in the fragments" ;

@+ Common BAT Aggregates
These operations examine a BAT, and compute some simple aggregate result
over it.
@- BAT size
@mal
module aggr;

command count( b:bat[:any_1,:any] ) :int 
address ALGcount_bat
comment "Return the current size (in number of elements) in a BAT.";
command count ( b:bat[:any_1,:any], ignore_nils:bit ) :int 
address ALGcount_nil
comment "Return the number of elements currently in a BAT ignores 
		BUNs with nil-tail iff ignore_nils==TRUE.";

command count_no_nil ( b:bat[:any_1,:any_2]) :int
address ALGcount_no_nil
comment "Return the number of elements currently 
	in a BAT ignoring BUNs with nil-tail";
@- Histogram on Tail
@mal
command histogram ( b:bat[:any_1,:any_2]) :bat[:any_2,:int] 
address ALGhistogram
comment "Produce a BAT containing the histogram over the tail values.";

@- Default Min and Max
Implementations a generic Min and Max routines get declared first. The
@emph{ min()} and @emph{ max()} routines below catch any tail-type.
The type-specific routines defined later are faster, and will
override these any implementations.
@mal
command cardinality( b:bat[:any_1,:any_2] ) :lng 
address ALGcard
comment "Return the cardinality of the BAT tail values.";
@- 
Implementations a generic Min and Max routines get declared first. The
@emph{ min()} and @emph{ max()} routines below catch any tail-type.
The type-specific routines defined later are faster, and will
override these any implementations.

@- 
@mal
command min(b:bat[:any_1,:any_2]):any_2 
address ALGminany
comment "Return the lowest tail value or nil.";

command max(b:bat[:any_1,:any_2]):any_2 
address ALGmaxany
comment "Return the highest tail value or nil.";
@+ Type-Specific Sum, Prod, Max and Min
For X in @{ sht,int,flt,dbl,lng @},  we generate the
aggregate functions using a macro.
@-
@= sum_definition
command sum (b:bat[:any_1,:@1] ) :@2 
address ALGsum_@1_@2
comment "Gives the sum of all tail values";
command product(b:bat[:any_1,:@1] ) :@2 
address ALGprod_@1_@2
comment "Gives the product of all tail values";
@mal
@:sum_definition(sht,sht)@
@:sum_definition(sht,int)@
@:sum_definition(sht,lng)@
@:sum_definition(int,int)@
@:sum_definition(int,lng)@
@:sum_definition(lng,lng)@
@:sum_definition(flt,flt)@
@:sum_definition(flt,dbl)@
@:sum_definition(dbl,dbl)@

@= avg_definition
command avg (b:bat[:any_1,:@1] ) :dbl 
address ALGavg_@1
comment "Gives the avg of all tail values";
@mal
@:avg_definition(sht)@
@:avg_definition(int)@
@:avg_definition(lng)@
@:avg_definition(flt)@
@:avg_definition(dbl)@
@-
@= aggregate_definition
command @1 ( b:bat[:any_1,:@2] ) :@2 
address ALG@1_@2 comment @3;
@= aggregate
@:aggregate_definition(@1,sht,@2)@
@:aggregate_definition(@1,int,@2)@
@:aggregate_definition(@1,flt,@2)@
@:aggregate_definition(@1,dbl,@2)@
@:aggregate_definition(@1,lng,@2)@

@mal
@:aggregate(max,"Give the highest tail value.")@
@:aggregate(min,"Give the lowest tail value. ")@

@+ Exented selection predicates
For SQL convenience we provide a serie of interval selectors.
@mal
module algebra;
@+ Modeling With Properties
The Monet kernel performs run-time optimizations. To choose between
alternative algorithms in a sensible way, it maintains knowledge about
each BAT, sometimes as a BAT property, sometimes as two
column properties for each column (head and tail)
of a BAT. An example of the former is size(bat):int
(which gives the number of BUNs in a BAT), an example
of the latter is ordered(column) :bit, indicating
whether the column contains its valued stored in ascending order.
The convention is to use a BAT as operand also for the column
properties; which then is supposed to be valid for the head
column (ordered(BAT)). Tail columns can be described by
using the mirror BAT with the minus operator (ordered(-BAT)).

@table @code
@item[ordered(BAT) :bit]
	TRUE if the head column is stored in ascending order, else FALSE.
@item[keyed(BAT) :bit]
	TRUE if no duplicates are present in the head column, else FALSE.
@item[idx(BAT) :bit]
	TRUE if a binary index tree search accelerator is present on
	the head column of the BAT, else FALSE.
@item[hashtab(BAT) :bit] 
		presence of hash table on the head column of
		a BAT. TRUE if a bucket-chained hash table search accelerator is
		present on the head column of the BAT, else FALSE.
@item[subcol(BAT, BAT) :bit]
	TRUE if the bag of all values in the head column of the left BAT is
	a bag-subset of the bag of all values in the head column of the
	right BAT, else FALSE.
@item[sync(BAT) :oid]
	Sync-OID on the head column of a BAT. A sync-OID denotes some unique
	sequence of values. If two columns have the same sync-OID, then they
	are guaranteed to contain the same values, in the same sequence.

@item[size(BAT) :int]
	The (estimated) length of a column.
@item[unique(BAT) :int]
	The (estimated) number of distinct values in one column.
@item[subset(BAT, BAT) :bit]
	TRUE if the left BAT is a subset of the BUNs of the right BAT,
	else FALSE.
@item[setunique(BAT) :bit]
	TRUE if the BAT contains no duplicate BUNs, else FALSE.
@end table

@- Property Propagation Rules
At database creation time, the properties of the BATs in the database
can be derived directly from the database schema.

When queries are executed, they will produce @emph{intermediate results},
which in terms are operands for further execution. Hence it is necessary
to @emph{propagate properties} from the operands of an algebraic operator,
to its result.

This process can be captured by having a series of @emph{propagation rules}
for each algebraic operand. Since each algebraic operands may apply
different strategies, according to different status in its operand properties,
each algebraic operator may have different propagation rules with these
different situations as conditions.

@include kprelude.mx
@h
#ifndef ALGEBRA_H
#define ALGEBRA_H

#include <gdk.h>
#include "mal_exception.h"

#ifdef WIN32
#ifndef LIBALGEBRA
#define algebra_export extern __declspec(dllimport)
#else
#define algebra_export extern __declspec(dllexport)
#endif
#else
#define algebra_export extern
#endif
algebra_export ptr BATmax(BAT *b, ptr aggr);
algebra_export ptr BATmin(BAT *b, ptr aggr);
algebra_export int doCMDfetch(ptr ret, BAT *b, lng i);
algebra_export str ALGprojectNIL(int *ret, int *bid);
@= avg_export
algebra_export str ALGavg_@1(dbl *res, int *bid);
@h
@:avg_export(sht)@
@:avg_export(int)@
@:avg_export(lng)@
@:avg_export(flt)@
@:avg_export(dbl)@

#endif

@c
#include "mal_config.h"
#include "algebra.h"

@= BATaggr
ptr BAT@1(BAT *b, ptr aggr) {
		int t;
		size_t s;
		ptr v, x;

		BATcheck(b, "BAT@1");
		s = BATcount(b);
		t = b->ttype;
		if (BATtvoid(b)) {
			@:aggr@1(chr,loc,simple,chr,void)@
		} else {
			switch(ATOMstorage(t)) {
			case TYPE_chr: @:aggr@1(chr,loc,simple,chr,atom)@ break;
			case TYPE_sht: @:aggr@1(sht,loc,simple,sht,atom)@ break;
			case TYPE_int: @:aggr@1(int,loc,simple,int,atom)@ break;
			case TYPE_flt: @:aggr@1(flt,loc,simple,flt,atom)@ break;
			case TYPE_dbl: @:aggr@1(dbl,loc,simple,dbl,atom)@ break;
			case TYPE_lng: @:aggr@1(lng,loc,simple,lng,atom)@ break;
			default:if (b->tvarsized) {
						   @:aggr@1(chr,var,atom,t,atom)@ break;
					 } else {
						   @:aggr@1(chr,loc,atom,t,atom)@ break;
			}		}
		}
		return x;
}

@c
@:BATaggr(min)@
@:BATaggr(max)@

@* Command Implementations in C
This module contains just a wrapper implementations; since all described
operations are part of the GDK kernel.

@+ BAT sum operation
The sum aggregate only works for int and float fields.
The routines below assumes that the caller knows what type
is large enough to prevent overflow.

@= sum_implementation
int
CMDsum_@1_@2(@2* res, BAT *b)
{
	BUN p,q;
	int xx;
	@2 result=@3;

	BATcheck(b,"BATsum_@1_@2");
	BATloopFast(b, p, q, xx) {
		@1 *value = (@1*) BUNtloc(b, p);
		if (*value == @1_nil) {
			result = @2_nil;
			break;
		} else {
			result += *value;
		}
	}
	*res = result;
	return GDK_SUCCEED;
}

@+ BAT prod[uct] operation
The prod[uct] aggregate only works for int and float fields.
The routines below assumes that the caller knows what type
is large enough to prevent overflow.

@= prod_implementation
int
CMDprod_@1_@2(@2* res, BAT *b)
{
	BUN p,q;
	int xx;
	@2 result=@3;

	BATcheck(b,"BATprodInt");
	BATloopFast(b, p, q, xx) {
		@1 *value = (@1*) BUNtloc(b, p);
		if (*value == @1_nil) {
			result = @2_nil;
			break;
		} else {
			result *= *value;
		}
	}
	*res = result;
	return GDK_SUCCEED;
}

@+ BAT avg operation
The avg aggregate only works for int and float fields.

@= avg_implementation
int
CMDavg_@1(dbl* res, BAT *b)
{
	int cnt = BATcount(b);
	dbl result=0.0;

	CMDsum_@1_dbl(&result, b);
	*res = result/cnt;
	return GDK_SUCCEED;
}

@+ Minimum and Maximum
The routines @`BATmin@5(b) and @`BATmax@5(b) compute the minimum and
maximum value of the tail column of a BAT.
Aggregate values are calculated just before they are requested by
the user. They are not maintained continuously, because we expect
them to be used sparsely.

@= aggregate_implementation