gdk_relop.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 gdk_relop
@a M. L. Kersten, P. Boncz, S. Manegold
@* BAT relational operators
The basic relational operators are implemented for BATs.
Particular attention has been paid to speed-up processing
joins, such that navigational access and object re-assembly
are not being harmed too much.
@{
@c
#include "monetdb_config.h"
#include "gdk.h"

#define SAMPLE_TRESHOLD_LOG 17
#define SAMPLE_SLICE_SIZE 1000
@}
@+ Join Algorithms
All join related operations have the same prelude to check
domain compatibility and to creates the BAT to hold the result.

We do some dynamic effort to estimate the result size. Good
estimates enhance performance and reduce the memory hunger of the join.
Method: we sample on l, and join on the whole r. This macro is called by
the physical join algorithms, hence we already decided on the algorithm
and join method, so the initial costs on r (e.g. hash creation) would have
to be paid anyway, and are reused later in the real join phase.

Sampling was made more robust by using a logarithmic number of slices
taken at equal-spaced intervals across l. The results are then analyzed
and checked for outliers. If outliers are present, a real sample is taken
and executed with the generic join algorithm to obtain an better estimate.

On small joins we just assume 1-N joins with a limited (=3) hit rate.
@{
@= joincheck
	ERRORcheck(l == NULL, "@1: invalid left operand");
	ERRORcheck(r == NULL, "@1: invalid right operand");
	ERRORcheck(TYPEerror(@2, @3), "@1: type conflict\n");
@= joinestimate
	if (@3 == (size_t) oid_nil) {
		size_t _lcount = BATcount(l);
		size_t _rcount = BATcount(r);
		size_t _slices = 0;

		/* limit estimate with simple bounds first; only spend effort if the join result might be big */
		if (@1 == JOIN_EQ) {
			if (l->tkey)
				@3 = r->hkey ? MIN(_rcount, _lcount) : _rcount;
			else if (r->hkey)
				@3 = _lcount;
		}
		if (@3 == oid_nil) {
			size_t _heuristic = 3 * MIN(_lcount, _rcount);

			if (_heuristic <= (1 << SAMPLE_TRESHOLD_LOG))
				@3 = _heuristic;
		}
		if (@3 == oid_nil) {
			size_t _idx;

			for (_idx = _lcount; _idx > 0; _idx >>= 1)
				_slices++;
		}
		if (_slices > SAMPLE_TRESHOLD_LOG) {
			/* use cheapo sampling by taking a number of slices and joining those with the algo */
			size_t _idx = 0, _tot = 0, _step, _lo, _avg, _sample, *_cnt;
			BAT *_tmp1 = l, *_tmp2, *_tmp3 = NULL;

			_step = _lcount / (_slices -= SAMPLE_TRESHOLD_LOG);
			_sample = _slices * SAMPLE_SLICE_SIZE;
			_cnt = (size_t *) alloca(_slices * sizeof(size_t));
			for (_lo = 0; _idx < _slices; _lo += _step) {
				size_t _size = 0, _hi = _lo + SAMPLE_SLICE_SIZE;

				l = BATslice(_tmp1, _lo, _hi);	/* slice keeps all parent properties */
				if (l == NULL)
					return NULL;
				_tmp2 = @2;	/* @2 = e.g. BATXjoin(l,r) */
				if (_tmp2) {
					_size = BATcount(_tmp2);
					BBPreclaim(_tmp2);
				}
				_tot += (_cnt[_idx++] = _size);
				BBPreclaim(l);
			}
			/* do outlier detection on sampling results; this guards against skew */
			if (@1 == JOIN_EQ) {
				for (_avg = _tot / _slices, _idx = 0; _idx < _slices; _idx++) {
					size_t _diff = _cnt[_idx] - _avg;

					if (_avg > _cnt[_idx])
						_diff = _avg - _cnt[_idx];
					if (_diff > MAX(SAMPLE_SLICE_SIZE, _avg))
						break;
				}
				if (_idx < _slices) {
					/* outliers detected, compute a real sample on at most 1% of the data */
					_sample = MIN(_lcount / 100, (1 << SAMPLE_TRESHOLD_LOG) / 3);
					_tmp2 = BATsample(_tmp1, _sample);
					if (_tmp2) {
						_tmp3 = BATjoin(_tmp2, r, oid_nil);	/* might be expensive */
						if (_tmp3) {
							_tot = BATcount(_tmp3);
							BBPreclaim(_tmp3);
						}
						BBPreclaim(_tmp2);
					}
					if (_tmp3 == NULL)
						return NULL;
				}
			}
			/* overestimate always by 5% */
			@3 = (size_t) ((double) (((lng) _tot) * ((lng) _lcount)) / (0.95 * (double) _sample));
			l = _tmp1;
		} else {
			@3 = MAX(_lcount,_rcount);
		}
	}
@= joinbat
	{
		size_t _estimate = @3;

		@:joinestimate(@1, @2, _estimate)@
		bn = BATnew(BAThtype(l), BATttype(r), _estimate);
		if (bn == NULL) {
			return bn;
		}
	}
@}
@- Merge join
In the case that both join columns are ordered, we can do a merging
(@%BATmergejoin@). The merge is opportunistic in that it tries to do
merge between l and r, but if for a long time no matching tuples are
found in r, it uses binary search. It also allows joining of an
unsorted l with a sorted r; in that case it always uses binary search.
@{
@= mergejoin
	if (((!BATtvoid(l)) || l->tseqbase != oid_nil) &&
	    ((!BAThvoid(r)) || r->hseqbase != oid_nil || nil_on_miss)) {
		assert(r->htype != TYPE_void);
		while (l_start < l_last) {
			ptr v2, v1 = BUNt@2(l, l_start);
			int neq = 1;

			/* lookup range in l */
			l_end = l_start;
			if (l_key) {
				l_end += l_next;
			} else
				do {
					if ((l_end += l_next) >= l_last)
						break;
					v2 = BUNt@2(l, l_end);
				} while (@1_EQ(v1, v2, @4));

			/* lookup value in r (if not nil, that is) */
			if (!@1_EQ(v1, nil, @4)) {
				if (r_scan > 0) {
					/* first try scanning; but give up after a while */
					for (r_lim = MIN(r_last, r_end + r_scan); r_end < r_lim; r_end += r_next) {
						v2 = BUNh@3(r, r_end);
						neq = @1_CMP(v1, v2, @4);
						if (neq <= 0)
							break;
					}
					r_start = r_end;
				}
				if (neq == 1) {
					/* use binary search after failed scan or if scanning is impossible (l not sorted) */
					if (r_scan < 0 || r_start < r_last) {
						/* if merge not ended (or if no merge at all) */
						r_start = (BUN) SORTfndfirst_@4(rr, v1);
					}
					if (r_start < r_last) {
						v2 = BUNh@3(r, r_start);
						neq = !@1_EQ(v1, v2, @4);
					} else if (r_scan >= 0) {
						/* r is already at end => break off merge join */
						break;
					}
				}
			}
			if (neq == 0) {
				/* lookup range in r */
				r_end = r_start + r_next;
				if (r_key == 0)
					while (r_end < r_last) {
						v2 = BUNh@3(r, r_end);
						if (!@1_EQ(v1, v2, @4))
							break;
						r_end += r_next;
					}
				/* generate match-product as join result */
				for (; l_start < l_end; l_start += l_next)
					for (r_cur = r_start; r_cur < r_end; r_cur += r_next)
						bunfastins(bn, BUNhead(l, l_start), BUNtail(r, r_cur));
			} else if (nil_on_miss) {
				/* outerjoin inserts nils on a miss */
				hasnils = 1;
				for (; l_start < l_end; l_start += l_next)
					bunfastins(bn, BUNhead(l, l_start), nil_on_miss);
			} else {
				l_start = l_end;	/* no match found in equi-join */
			}
		}
	}
@c
/* serves both normal equi-join (nil_on_miss==NULL) and outerjoin (nil_on_miss=nil) */
static BAT *
mergejoin(BAT *l, BAT *r, BAT *bn, ptr nil_on_miss, size_t estimate)
{
	ptr nil = ATOMnilptr(r->htype);
	int r_scan = -1;	/* no scanning in r */
	BAT *rr = BATmirror(r);
	BUN l_last, r_last;	/* last BUN of the BAT */
	BUN l_start, r_start;	/* start of current chunk  */
	BUN l_end, r_end;	/* end of current chunk */
	int r_next = BUNsize(r);
	int l_next = BUNsize(l);
	int l_key = l->tkey;
	int r_key = r->hkey;
	BUN r_cur, r_lim;
	int loc, var, hasnils = 0;

	if (BATtordered(l) & 1) {
		size_t i;
		int logr = 4;

		/* 4*log2(r.count) = estimation of the cost of binary search in units of scan comparisons */
		for (i = BATcount(r); i > 0; logr++)
			i >>= 1;
		r_scan = logr * BUNsize(r);	/* opportunistic scan window in r */
	}
	if (!(BAThordered(r) & 1)) {
		GDKerror("mergejoin: right input is not sorted.\n");
		return NULL;
	}
	if (bn == NULL) {
		@:joinbat(JOIN_EQ,mergejoin(l,r,NULL,nil_on_miss,oid_nil),estimate)@
	}

	/* the algorithm */
	loc = ATOMstorage(l->ttype);

	l_last = BUNlast(l);
	r_last = BUNlast(r);
	l_start = l_end = BUNfirst(l);
	r_start = r_end = BUNfirst(r);

	switch (loc) {
#ifndef NOEXPAND_CHR
	case TYPE_chr:
		@:mergejoin(simple,loc,loc,chr)@;
		break;
#endif
#ifndef NOEXPAND_BTE
	case TYPE_bte:
		@:mergejoin(simple,loc,loc,bte)@;
		break;
#endif
#ifndef NOEXPAND_SHT
	case TYPE_sht:
		@:mergejoin(simple,loc,loc,sht)@;
		break;
#endif
#ifndef NOEXPAND_INT
	case TYPE_int:
		@:mergejoin(simple,loc,loc,int)@;
		break;
#endif
#ifndef NOEXPAND_FLT
	case TYPE_flt:
		@:mergejoin(simple,loc,loc,flt)@;
		break;
#endif
#ifndef NOEXPAND_LNG
	case TYPE_lng:
		@:mergejoin(simple,loc,loc,lng)@;
		break;
#endif
#ifndef NOEXPAND_DBL
	case TYPE_dbl:
		@:mergejoin(simple,loc,loc,dbl)@;
		break;
#endif
	default:
		/* watch it: l->tvarsized may be set due to void l */
		if (l->tvarsized) {
			var = ATOMstorage(l->ttype);

			if (r->hvarsized) {
				/* l and r both real varsized types */
				@:mergejoin(atom,var,var,var)@
			} else {
				/* l is void, r is oid */
				loc = ATOMstorage(r->htype);
				@:mergejoin(atom,var,loc,loc)@
			}
		} else {
			/* we can't handle void r anyway, so don't worry about it here */
			loc = ATOMstorage(l->ttype);
			@:mergejoin(atom,loc,loc,loc)@
		}
		break;
	}

	if (nil_on_miss && l_start < l_last) {
		hasnils = 1;
		for (; l_start < l_last; l_start += l_next)
			bunfastins(bn, BUNhead(l, l_start), nil_on_miss);
	}

	/* propagate properties */
	bn->hsorted = BAThordered(l);
	bn->tsorted = FALSE;
	if (r->hkey) {
		if (BATcount(bn) == BATcount(l)) {
			ALIGNsetH(bn, l);
		} else if (l->hkey) {
			BATkey(bn, TRUE);
		}
	}
	if (l->tkey) {
		bn->tsorted = BATtordered(r) & BATtordered(l) & 1;
		if (!nil_on_miss) {
			if (BATcount(bn) == BATcount(r)) {
				ALIGNsetT(bn, r);
			} else if (r->tkey) {
				BATkey(BATmirror(bn), TRUE);
			}
		} else if (hasnils) {
			bn->tsorted = 0;	/* nils destroy the ordering */
		}
	}
	return bn;
      bunins_failed:
	BBPreclaim(bn);
	return NULL;
}

static BAT * batfetchjoin(BAT *l, BAT *r, size_t estimate, bit swap, bit hitalways);

static BAT *
batmergejoin(BAT *l, BAT *r, size_t estimate, bit swap)
{
	@:joincheck(BATmergejoin,l->ttype,r->htype)@
        if (BAThdense(r) || (swap && BATtdense(l))) {
            /* batmergejoin can't handle void tail columns at all (fetchjoin is better anyway) */
            return batfetchjoin(l, r, estimate, swap, FALSE);
        }
	if (swap && (((BAThordered(r) & 1) == 0) || ((BATtordered(l) & 1) && (BATcount(l) > BATcount(r))))) {
		/* reverse join if required (r not sorted) or if l is larger (quick jump through l with binary search) */
		BAT *bn = mergejoin(BATmirror(r), BATmirror(l), NULL, NULL, estimate);

		return bn ? BATmirror(bn) : NULL;
	}
	return mergejoin(l, r, NULL, NULL, estimate);
}

BAT *
BATmergejoin(BAT *l, BAT *r, size_t estimate)
{
	/* allows swapping of left and right input for faster processing */
	return batmergejoin(l, r, estimate, TRUE);
}

BAT *
BATleftmergejoin(BAT *l, BAT *r, size_t estimate)
{
	/* do not swap left and right input,
	   and hence maintain order of left head in result */
	return batmergejoin(l, r, estimate, FALSE);
}

@- hash join
These macros encode the core of the join algorithm. They are
the fast inner loops, optimized towards their type.

@= hashjoin
	{
		int xx;
		hash_t yy;

		BATloopFast(l, p, q, xx) {
			v = BUN@3(l,p);
			if (@1_EQ(v,nil,@2)) {
				continue; /* skip nil */
			}
			HASHloop_@2(r, r->hhash, yy, v, w) {
				bunfastins(bn, BUNhead(l,p), BUNtail(r,w));
			}
		}
		/* set sorted flags by hand, because we used BUNfastins() */
		bn->hsorted = BAThordered(l);
		bn->tsorted = FALSE;
		break;
	}
@c
BAT *
BAThashjoin(BAT *l, BAT *r, size_t estimate)
{
	ptr v, nil = ATOMnilptr(r->htype);
	BUN p, q, w;
	int any;
	BAT *bn = NULL;

	@:joincheck(BAThashjoin,l->ttype,r->htype)@
	@:joinbat(JOIN_EQ,BAThashjoin(l,r,oid_nil),estimate)@

	BATmmap_pin(r);
	if (BATprepareHash(r))
		return NULL;
	switch (any = ATOMstorage(l->ttype)) {
#ifndef NOEXPAND_CHR
	case TYPE_chr:
		@:hashjoin(simple,chr,tloc)@
#endif
#ifndef NOEXPAND_BTE
	case TYPE_bte:
		@:hashjoin(simple,bte,tloc)@
#endif
#ifndef NOEXPAND_SHT
	case TYPE_sht:
		@:hashjoin(simple,sht,tloc)@
#endif
#if !defined(NOEXPAND_INT) || !defined(NOEXPAND_FLT)
	case TYPE_int:
	case TYPE_flt:
		@:hashjoin(simple,int,tloc)@
#endif
#if !defined(NOEXPAND_DBL) || !defined(NOEXPAND_LNG)
	case TYPE_dbl:
	case TYPE_lng:
		@:hashjoin(simple,lng,tloc)@
#endif
	default:
	      @:hashjoin(atom,any,tail);@
	}
	BATmmap_unpin(r);

	/* propagate alignment info */
	bn->hsorted = BAThordered(l);
	if (BAThkey(r)) {
		if (BATcount(bn) == BATcount(l))
			ALIGNsetH(bn, l);
		if (BAThkey(l))
			BATkey(bn, TRUE);
	}
	ESTIDEBUG THRprintf(GDKout, "#BAThashjoin: actual resultsize: " SZFMT "\n", BATcount(bn));

	return bn;
      bunins_failed: