gdk_relop.c

这个是内存数据库中的一个管理工具

						v2 = BUNhloc(r, r_end);
						neq = simple_CMP(v1, v2, flt);
						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_flt(rr, v1);
					}
					if (r_start < r_last) {
						v2 = BUNhloc(r, r_start);
						neq = !simple_EQ(v1, v2, flt);
					} 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 = BUNhloc(r, r_end);
						if (!simple_EQ(v1, v2, flt))
							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 */
			}
		}
	}


#line 288 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
;
		break;
#endif
#ifndef NOEXPAND_LNG
	case TYPE_lng:
		
#line 153 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
	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 = BUNtloc(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 = BUNtloc(l, l_end);
				} while (simple_EQ(v1, v2, lng));

			/* lookup value in r (if not nil, that is) */
			if (!simple_EQ(v1, nil, lng)) {
				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 = BUNhloc(r, r_end);
						neq = simple_CMP(v1, v2, lng);
						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_lng(rr, v1);
					}
					if (r_start < r_last) {
						v2 = BUNhloc(r, r_start);
						neq = !simple_EQ(v1, v2, lng);
					} 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 = BUNhloc(r, r_end);
						if (!simple_EQ(v1, v2, lng))
							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 */
			}
		}
	}


#line 293 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
;
		break;
#endif
#ifndef NOEXPAND_DBL
	case TYPE_dbl:
		
#line 153 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
	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 = BUNtloc(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 = BUNtloc(l, l_end);
				} while (simple_EQ(v1, v2, dbl));

			/* lookup value in r (if not nil, that is) */
			if (!simple_EQ(v1, nil, dbl)) {
				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 = BUNhloc(r, r_end);
						neq = simple_CMP(v1, v2, dbl);
						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_dbl(rr, v1);
					}
					if (r_start < r_last) {
						v2 = BUNhloc(r, r_start);
						neq = !simple_EQ(v1, v2, dbl);
					} 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 = BUNhloc(r, r_end);
						if (!simple_EQ(v1, v2, dbl))
							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 */
			}
		}
	}


#line 298 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
;
		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 */
				
#line 153 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
	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 = BUNtvar(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 = BUNtvar(l, l_end);
				} while (atom_EQ(v1, v2, var));

			/* lookup value in r (if not nil, that is) */
			if (!atom_EQ(v1, nil, var)) {
				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 = BUNhvar(r, r_end);
						neq = atom_CMP(v1, v2, var);
						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_var(rr, v1);
					}
					if (r_start < r_last) {
						v2 = BUNhvar(r, r_start);
						neq = !atom_EQ(v1, v2, var);
					} 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 = BUNhvar(r, r_end);
						if (!atom_EQ(v1, v2, var))
							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 */
			}
		}
	}


#line 308 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"

			} else {
				/* l is void, r is oid */
				loc = ATOMstorage(r->htype);
				
#line 153 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
	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 = BUNtvar(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 = BUNtvar(l, l_end);
				} while (atom_EQ(v1, v2, loc));

			/* lookup value in r (if not nil, that is) */
			if (!atom_EQ(v1, nil, loc)) {
				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 = BUNhloc(r, r_end);
						neq = atom_CMP(v1, v2, loc);
						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_loc(rr, v1);
					}
					if (r_start < r_last) {
						v2 = BUNhloc(r, r_start);
						neq = !atom_EQ(v1, v2, loc);
					} 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 = BUNhloc(r, r_end);
						if (!atom_EQ(v1, v2, loc))
							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 */
			}
		}
	}


#line 312 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"

			}
		} else {
			/* we can't handle void r anyway, so don't worry about it here */
			loc = ATOMstorage(l->ttype);
			
#line 153 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
	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 = BUNtloc(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 = BUNtloc(l, l_end);
				} while (atom_EQ(v1, v2, loc));

			/* lookup value in r (if not nil, that is) */
			if (!atom_EQ(v1, nil, loc)) {
				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 = BUNhloc(r, r_end);
						neq = atom_CMP(v1, v2, loc);
						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_loc(rr, v1);
					}
					if (r_start < r_last) {
						v2 = BUNhloc(r, r_start);
						neq = !atom_EQ(v1, v2, loc);
					} 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 = BUNhloc(r, r_end);
						if (!atom_EQ(v1, v2, loc))
							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 */
			}
		}
	}


#line 317 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"

		}
		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)
{
	
#line 51 "/export/scratch0/monet/monet.GNU.64.64.d.14791/MonetDB/src/gdk/gdk_relop.mx"
	ERRORcheck(l == NULL, "BATmergejoin: invalid left operand");
	ERRORcheck(r == NULL, "BATmergejoin: invalid right operand");
	ERRORcheck(TYPEerror(l->ttype, r->htype), "BATmergejoin: type conflict\n");