Changeset: 7be54df219e8 for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=7be54df219e8
Modified Files:
gdk/Makefile.ag
gdk/gdk.h
gdk/gdk_batop.c
gdk/gdk_relop.c
gdk/gdk_relop.mx
Branch: headless
Log Message:
Colified relop.
The following functions are (currently?) the only interfaces that are
defined:
int COLjoin(COL **o1, COL **o2, COL *l, COL *r, oid estimate);
int COLouterjoin(COL **o1, COL **o2, COL *l, COL *r, oid estimate);
int COLantijoin(COL **o1, COL **o2, COL *l, COL *r, oid estimate);
int COLthetajoin(COL **o1, COL **o2, COL *l, COL *r, int op, oid estimate);
COL *COLproject(COL *l, COL *r);
int COLcross(COL **o1, COL **o2, COL *l, COL *r);
The various join variants all return two lists of OIDs in their first
two parameters.
COLproject takes a list of OIDs and a list of values and returns a COL
with values from the second argument in the order indicated by the
first. If an OID from the first column is out of range COLproject
returns an error; if an OID is equal to nil, the corresponding value
will be nil as well (i.e. no error).
COLcross returns two lists of OIDs indicating a full Carthesian
product of the two inputs. Only the sizes of the inputs are used
(i.e. not their contents).
There is loads of room for (speed) improvements.
diffs (truncated from 3876 to 300 lines):
diff --git a/gdk/Makefile.ag b/gdk/Makefile.ag
--- a/gdk/Makefile.ag
+++ b/gdk/Makefile.ag
@@ -19,8 +19,6 @@
INCLUDES = ../common/options ../common/stream ../common/utils
$(valgrind_CFLAGS)
-# gdk_relop.mx
-
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
lib_gdk = {
@@ -30,7 +28,7 @@
gdk_batop.c \
gdk_search.c \
gdk_setop.c gdk_utils.c gdk_atoms.c \
-# gdk_relop.mx \
+ gdk_relop.c \
gdk_tm.c gdk_align.c gdk_cbp.c \
gdk_heap.c \
gdk_qsort.c gdk_ssort.c gdk_storage.c gdk_col.c \
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -2232,7 +2232,6 @@
gdk_export COL *COLhash(COL *b, oid masksize);
gdk_export COL *COLhashsplit(COL *b, oid n, int unary);
gdk_export COL *COLrangesplit(COL *b, oid n, int unary);
-gdk_export COL *COLhashjoin(COL *l, COL *r, oid estimate);
/* low level functions */
gdk_export oid SORTfnd(COL *b, ptr v);
@@ -3251,22 +3250,14 @@
gdk_export int COLsubselect(COL **ret, COL *b, COL *s, ptr tl, ptr th, bit li,
bit hi, bit anti);
gdk_export COL *COLconst(oid cnt, int tpe, ptr val);
-gdk_export COL *COLthetajoin(COL *l, COL *r, int mode, oid estimate);
-gdk_export COL *COLleftthetajoin(COL *l, COL *r, int mode, oid estimate);
-gdk_export COL *COLnlthetajoin(COL *l, COL *r, int mode, oid estimate);
-gdk_export COL *COLsemijoin(COL *l, COL *r);
-gdk_export COL *COLmergejoin(COL *l, COL *r, oid estimate);
-gdk_export COL *COLleftmergejoin(COL *l, COL *r, oid estimate);
-gdk_export COL *COLjoin(COL *l, COL *r, oid estimate);
-gdk_export COL *COLantijoin(COL *l, COL *r);
-gdk_export COL *COLleftjoin(COL *l, COL *r, oid estimate);
-gdk_export COL *COLouterjoin(COL *l, COL *r, oid estimate);
-gdk_export COL *COLcross(COL *l, COL *r);
+gdk_export int COLthetajoin(COL **o1, COL **o2, COL *l, COL *r, int op, oid
estimate);
+gdk_export int COLjoin(COL **o1, COL **o2, COL *l, COL *r, oid estimate);
+gdk_export int COLantijoin(COL **o1, COL **o2, COL *l, COL *r, oid estimate);
+gdk_export int COLouterjoin(COL **o1, COL **o2, COL *l, COL *r, oid estimate);
+gdk_export COL *COLproject(COL *l, COL *r);
+gdk_export int COLcross(COL **o1, COL **o2, COL *l, COL *r);
gdk_export COL *COLslice(COL *b, oid low, oid high);
-gdk_export COL *COLfetch(COL *b, COL *s);
-gdk_export COL *COLfetchjoin(COL *b, COL *s, oid estimate);
-gdk_export COL *COLleftfetchjoin(COL *b, COL *s, oid estimate);
gdk_export COL *COLunique_select(COL *b);
gdk_export COL *COLintersect_select(COL *b, COL *c);
diff --git a/gdk/gdk_batop.c b/gdk/gdk_batop.c
--- a/gdk/gdk_batop.c
+++ b/gdk/gdk_batop.c
@@ -786,7 +786,7 @@
* nils, so instead we return nothing. */
if (*ret == NULL)
*ret = COLnewdensecol(0);
- return 0;
+ return GDK_SUCCEED;
} else if (equi && lnil) {
/* antiselect for nil value: turn into range
* select for nil-nil range (i.e. everything
@@ -807,7 +807,7 @@
if (*ret == NULL)
*ret = COLnewdensecol(0);
- return 0;
+ return GDK_SUCCEED;
}
if (!equi && !lval && !hval && b->nonil && lnil) {
bn = COLnewdensecol(b->count);
@@ -817,12 +817,12 @@
CBPreclaim(bn);
bn = *ret;
}
- return 0;
+ return GDK_SUCCEED;
}
if (equi && lnil && b->nonil) {
if (*ret == NULL)
*ret = COLnewdensecol(0);
- return 0;
+ return GDK_SUCCEED;
}
batcnt = b->count;
@@ -926,7 +926,7 @@
}
}
*ret = bn;
- return 0;
+ return GDK_SUCCEED;
}
/*
* @-
@@ -946,7 +946,7 @@
COL *tmp2 = NULL;
ALGODEBUG THRprintf(GDKout, "#COL_select_(b=%s):
sampling: tmp2 = COL_select_(tmp1=%s, tl, th, tail);\n", COLgetId(b),
COLgetId(tmp1));
- if (COLsubselect(&tmp2, tmp1, NULL, tl, th, li, hi,
anti) == 0) {
+ if (COLsubselect(&tmp2, tmp1, NULL, tl, th, li, hi,
anti) == GDK_SUCCEED) {
/* reserve 105% of what has been estimated */
estimate = (oid) ((((lng) tmp2->count) * (lng)
batcnt) / LL_CONSTANT(100));
CBPreclaim(tmp2);
@@ -987,7 +987,7 @@
}
}
if (bn == NULL) {
- return -1; /* error occurred */
+ return GDK_FAIL; /* error occurred */
}
ALGODEBUG THRprintf(GDKout, "#COL_select_(b=%s): %s: key=%d, sorted=%d,
revsorted=%d.\n",
COLgetId(b), COLgetId(bn), bn->key, bn->sorted,
bn->revsorted);
@@ -995,14 +995,14 @@
COLgetId(b), estimate, bn->count);
*ret = bn;
- return 0;
+ return GDK_SUCCEED;
}
COL *
COL_select_(COL *b, ptr tl, ptr th, bit li, bit hi, bit anti)
{
COL *bn = NULL;
- if (COLsubselect(&bn, b, NULL, tl, th, li, hi, anti) == 0)
+ if (COLsubselect(&bn, b, NULL, tl, th, li, hi, anti) == GDK_SUCCEED)
return bn;
return NULL;
}
@@ -1011,7 +1011,7 @@
COLselect_(COL *b, ptr l, ptr h, bit li, bit hi)
{
COL *bn = NULL;
- if (COLsubselect(&bn, b, NULL, l, h, li, hi, FALSE) == 0)
+ if (COLsubselect(&bn, b, NULL, l, h, li, hi, FALSE) == GDK_SUCCEED)
return bn;
return NULL;
}
@@ -1020,7 +1020,7 @@
COLantiselect_(COL *b, ptr l, ptr h, bit li, bit hi)
{
COL *bn = NULL;
- if (COLsubselect(&bn, b, NULL, l, h, li, hi, TRUE) == 0)
+ if (COLsubselect(&bn, b, NULL, l, h, li, hi, TRUE) == GDK_SUCCEED)
return bn;
return NULL;
}
@@ -1029,7 +1029,7 @@
COLselect(COL *b, ptr l, ptr h)
{
COL *bn = NULL;
- if (COLsubselect(&bn, b, NULL, l, h, TRUE, TRUE, FALSE) == 0)
+ if (COLsubselect(&bn, b, NULL, l, h, TRUE, TRUE, FALSE) == GDK_SUCCEED)
return bn;
return NULL;
}
@@ -1171,7 +1171,7 @@
if (bn1 == NULL)
return NULL;
- bn = COLleftfetchjoin(bn1, b, bn1->count);
+ bn = COLproject(bn1, b);
CBPreclaim(bn1);
return bn;
}
@@ -1856,7 +1856,7 @@
r++;
}
} else {
- COL *buv = COLleftfetchjoin(bu, b, bu->count);
+ COL *buv = COLproject(bu, b);
COLiter buvi;
if (buv == NULL) {
diff --git a/gdk/gdk_relop.mx b/gdk/gdk_relop.c
rename from gdk/gdk_relop.mx
rename to gdk/gdk_relop.c
--- a/gdk/gdk_relop.mx
+++ b/gdk/gdk_relop.c
@@ -1,3339 +1,399 @@
-@/
-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_relop
-@a M. L. Kersten, P. Boncz, S. Manegold
-@* COL relational operators
-The basic relational operators are implemented for COLs.
-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
+/*
+ * @f gdk_relop
+ * @a M. L. Kersten, P. Boncz, S. Manegold
+ * @* COL relational operators
+ * The basic relational operators are implemented for COLs.
+ * Particular attention has been paid to speed-up processing
+ * joins, such that navigational access and object re-assembly
+ * are not being harmed too much.
+ */
#include "monetdb_config.h"
#include "gdk.h"
#include "gdk_private.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 COL 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.
+static int
+COLjoin_impl(COL **o1, COL **o2, COL *l, COL *r, oid estimate, int op, int
anti, int outer)
+{
+ COL *bn1, *bn2;
+ oid p, q;
+ ptr v, nil;
+ int li, hi;
+ int usel, user;
+ COLiter lit;
-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.
+ ERRORcheck(l == NULL, "COLjoin: invalid left operand");
+ ERRORcheck(r == NULL, "COLjoin: invalid right operand");
+ ERRORcheck(TYPEerror(l->type, r->type), "COLjoin: type conflict\n");
+ ERRORcheck(o1 == NULL || o2 == NULL,
+ "COLjoin: invalid return argument(s)");
+ assert(!anti || op == JOIN_EQ);
-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 == BUN_NONE) {
- oid _lcount = COLcount(l);
- oid _rcount = COLcount(r);
- oid _slices = 0;
+ switch (op) {
+ case JOIN_EQ:
+ li = 1;
+ hi = 1;
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
