Changeset: 7fca865e0f8e for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=7fca865e0f8e
Modified Files:
gdk/Makefile.ag
gdk/gdk_rangejoin.c
gdk/gdk_rangejoin.h
gdk/gdk_rangejoin.mx
Branch: headless
Log Message:
Converted gdk_rangejoin.
Only the nested loop implementation is done, but for bandjoin there is
type expansion (no other way to do it).
diffs (truncated from 1080 to 300 lines):
diff --git a/gdk/Makefile.ag b/gdk/Makefile.ag
--- a/gdk/Makefile.ag
+++ b/gdk/Makefile.ag
@@ -21,7 +21,7 @@
EXTRA_DIST = gdk.h gdk_cbp.h gdk_col.h gdk_delta.h \
# gdk_logger.h \
- gdk_posix.h gdk_private.h gdk_qsort_impl.h gdk_ssort_impl.h
gdk_storage.h gdk_system.h gdk_tm.h gdk_utils.h gdk_setop.h
+ gdk_posix.h gdk_private.h gdk_qsort_impl.h gdk_rangejoin.h
gdk_ssort_impl.h gdk_storage.h gdk_system.h gdk_tm.h gdk_utils.h gdk_setop.h
lib_gdk = {
VERSION = $(GDK_VERSION)
@@ -36,7 +36,7 @@
gdk_qsort.c gdk_ssort.c gdk_storage.c gdk_col.c \
gdk_delta.c \
gdk_system.c gdk_value.c \
-# gdk_rangejoin.mx \
+ gdk_rangejoin.c \
gdk_posix.c \
# gdk_logger.c \
bat.feps bat1.feps bat2.feps \
diff --git a/gdk/gdk_rangejoin.mx b/gdk/gdk_rangejoin.c
rename from gdk/gdk_rangejoin.mx
rename to gdk/gdk_rangejoin.c
--- a/gdk/gdk_rangejoin.mx
+++ b/gdk/gdk_rangejoin.c
@@ -1,473 +1,563 @@
-@/
-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
+/*
+ * 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-July 2008 CWI.
+ * Copyright August 2008-2011 MonetDB B.V.
+ * All Rights Reserved.
+ */
-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-July 2008 CWI.
-Copyright August 2008-2011 MonetDB B.V.
-All Rights Reserved.
-@
-
-@f gdk_rangejoin
-@a N. J. Nes
-
-@* Range Join Operators
-The sql statement b.x <= a.z <= b.y, could be implemented using too thetajoins.
-But that results in very large intermediates.
-
-@{
-@h
-#ifndef GDK_RANGEJOIN_H
-#define GDK_RANGEJOIN_H
-
-@- COL range and band join operators
-The @%COLbandjoin@ produces the associations [A, D] such that S.C-c1 <=
-R.b <= S.C + c2. The special case c1 = 0 and c2 = infinite leads to a
-thetajoin.
-
-@h
-gdk_export COL *COLrangejoin(COL *l, COL *rl, COL *rh, bit li, bit hi);
-@
-Join all BUNs of the COLs that have tail values: {rl <= l <= rh}.
-
-@h
-gdk_export COL *COLbandjoin(COL *l, COL *r, ptr mnus, ptr plus, bit li, bit
hi);
-@
-Join all BUNs of the COLs that have tail values: {r-mnus <= l <= r+plus}.
-
-@h
-@
-Versions of bandjoin fixed on the merge implementation (possibly with a
cut-off limit);
-
-@h
-#endif /* GDK_RANGEJOIN_H */
-@c
+/*
+ * @f gdk_rangejoin
+ * @a N. J. Nes
+ *
+ * @* Range Join Operators
+ * The sql statement b.x <= a.z <= b.y, could be implemented using too
thetajoins.
+ * But that results in very large intermediates.
+ *
+ */
#include "monetdb_config.h"
#include "gdk.h"
#include "gdk_private.h"
#include "gdk_rangejoin.h"
-@{
-COL *COLrangejoin(COL *l, COL *rl, COL *rh, bit li, bit hi)
+int
+COLrangejoin(COL **o1, COL **o2, COL *l, COL *rl, COL *rh, bit li, bit hi)
{
- COL *bn;
-
- ERRORcheck(l == NULL, "COLrangejoin: invalid left operand");
- ERRORcheck(rl == NULL, "COLrangejoin: invalid right low operand");
- ERRORcheck(rh == NULL, "COLrangejoin: invalid right high operand");
- ERRORcheck(TYPEerror(l->ttype, rl->ttype), "COLrangejoin: type
conflict\n");
- ERRORcheck(TYPEerror(l->ttype, rh->ttype), "COLrangejoin: type
conflict\n");
- /* TODO check that rl and rh are aligned */
-
- bn = COLnew(COLhtype(l), COLhtype(rl), MIN(COLcount(l), COLcount(rl)));
- if (bn == NULL)
- return bn;
- switch (ATOMstorage(rl->ttype)) {
-#ifndef NOEXPAND_CHR
- case TYPE_chr:
- @:rangejoin(chr,)@
-#endif
-#ifndef NOEXPAND_BTE
- case TYPE_bte:
- @:rangejoin(bte,)@
-#endif
-#ifndef NOEXPAND_SHT
- case TYPE_sht:
- @:rangejoin(sht,)@
-#endif
-#ifndef NOEXPAND_INT
- case TYPE_int:
- @:rangejoin(int,)@
-#endif
-#ifndef NOEXPAND_WRD
- case TYPE_wrd:
- @:rangejoin(wrd,)@
-#endif
-#ifndef NOEXPAND_FLT
- case TYPE_flt:
- @:rangejoin(flt,)@
-#endif
-#ifndef NOEXPAND_DBL
- case TYPE_dbl:
- @:rangejoin(dbl,)@
-#endif
-#ifndef NOEXPAND_LNG
- case TYPE_lng:
- @:rangejoin(lng,)@
-#endif
- default:
- @:rangejoin(any,any)@
- }
- /* set sorted flags by hand, because we used BUNfastins() */
- bn->hsorted = COLhordered(l);
- bn->tsorted = FALSE;
-
- ESTIDEBUG THRprintf(GDKout, "#COLrangejoin: actual resultsize: " OIDFMT
"\n", COLcount(bn));
-
- return bn;
-}
-
-@= rangejoin
-if (li && hi)
- @:rangejoin_@2(@1,>=,<=)
-else if (li && !hi)
- @:rangejoin_@2(@1,>=,<)
-else if (!li && hi)
- @:rangejoin_@2(@1,>,<=)
-else
- @:rangejoin_@2(@1,>,<)
-break;
-@
-@= rangejoin_
-{
- COLiter li = col_iterator(l);
- COLiter rli = col_iterator(rl);
- COLiter rhi = col_iterator(rh);
+ COL *bn1, *bn2;
+ COLiter lit;
+ COLiter rli;
+ COLiter rhi;
oid p, q;
oid v, w;
+ int (*cmp)(void*,void*);
+ ptr x1;
+
+ ERRORcheck(l == NULL, "COLrangejoin: invalid left operand\n");
+ ERRORcheck(rl == NULL, "COLrangejoin: invalid right low operand\n");
+ ERRORcheck(rh == NULL, "COLrangejoin: invalid right high operand\n");
+ ERRORcheck(TYPEerror(l->type, rl->type), "COLrangejoin: type
conflict\n");
+ ERRORcheck(TYPEerror(l->type, rh->type), "COLrangejoin: type
conflict\n");
+ ERRORcheck(rl->count != rh->count, "COLrangejoin: low and high operand
are not aligned\n");
+ ERRORcheck(!ATOMlinear(l->type), "COLrangejoin: join not possible on
non-linear types\n");
+ ERRORcheck(o1 == NULL || o2 == NULL, "COLrangejoin: no output
location\n");
+
+ bn1 = COLnew(TYPE_oid, MIN(l->count, rl->count));
+ bn2 = COLnew(TYPE_oid, MIN(l->count, rl->count));
+ if (bn1 == NULL || bn2 == NULL) {
+ if (bn1)
+ CBPreclaim(bn1);
+ if (bn2)
+ CBPreclaim(bn2);
+ return GDK_FAIL;
+ }
+
+ lit = col_iterator(l);
+ rli = col_iterator(rl);
+ rhi = col_iterator(rh);
+ cmp = COLatoms[l->type].atomCmp;
COLloop(l, p, q) {
- @1 x1 = *(@1 *) BUNtloc(li, p);
- COLloop(rl, v, w) {
- if ((x1 @2 *(@1 *) BUNtloc(rli, v)) &&
- (x1 @3 *(@1 *) BUNtloc(rhi, v))) {
- if (BUNfastins(bn, BUNhead(li, p), BUNhead(rli,
v)) == NULL) {
- CBPreclaim(bn);
- return NULL;
+ x1 = BUNhead(lit, p);
+ if (li && hi) {
+ COLloop(rl, v, w) {
+ if (cmp(x1, BUNhead(rli, v)) >= 0 &&
+ cmp(x1, BUNhead(rhi, v)) <= 0) {
+ bunfastins_oid(bn1, p - l->first);
+ bunfastins_oid(bn2, v - rl->first);
+ }
+ }
+ } else if (li && !hi) {
+ COLloop(rl, v, w) {
+ if (cmp(x1, BUNhead(rli, v)) >= 0 &&
+ cmp(x1, BUNhead(rhi, v)) < 0) {
+ bunfastins_oid(bn1, p - l->first);
+ bunfastins_oid(bn2, v - rl->first);
+ }
+ }
+ } else if (!li && hi) {
+ COLloop(rl, v, w) {
+ if (cmp(x1, BUNhead(rli, v)) > 0 &&
+ cmp(x1, BUNhead(rhi, v)) <= 0) {
+ bunfastins_oid(bn1, p - l->first);
+ bunfastins_oid(bn2, v - rl->first);
+ }
+ }
+ } else {
+ COLloop(rl, v, w) {
+ if (cmp(x1, BUNhead(rli, v)) > 0 &&
+ cmp(x1, BUNhead(rhi, v)) < 0) {
+ bunfastins_oid(bn1, p - l->first);
+ bunfastins_oid(bn2, v - rl->first);
}
}
}
}
+ ESTIDEBUG THRprintf(GDKout, "#COLrangejoin: actual resultsize: " OIDFMT
"\n", bn1->count);
+
+ assert(bn1->count == bn2->count);
+ bn1->nil = 0;
+ bn1->nonil = 1;
+ bn2->nil = 0;
+ bn2->nonil = 1;
+ bn1->sorted = 1;
+ bn1->revsorted = bn1->count <= 1;
+ bn1->key = bn1->count <= 1;
+ bn2->sorted = bn2->count <= 1;
+ bn2->revsorted = bn2->count <= 1;
+ bn2->key = bn2->count <= 1;
+ *o1 = bn1;
+ *o2 = bn2;
+
+ return GDK_SUCCEED;
+
+ bunins_failed:
+ if (bn1)
+ CBPreclaim(bn1);
+ if (bn2)
+ CBPreclaim(bn2);
+ return GDK_FAIL;
}
-@= rangejoin_any
+
+/*
+ * @-
+ * @+ Bandjoin
+ * A non-equi join of two relations R and S is called a Band-join if
+ * the join predicate requires the values of R to fall within a given range.
+ * This kind of joins is encountered in real world domains, such as those
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
