Changeset: a62315e6e373 for MonetDB
URL: https://dev.monetdb.org/hg/MonetDB/rev/a62315e6e373
Modified Files:
gdk/gdk.h
gdk/gdk_join.c
monetdb5/modules/kernel/algebra.c
Branch: groupjoin
Log Message:
Implemented BATmarkjoin.
diffs (truncated from 1907 to 300 lines):
diff --git a/gdk/gdk.h b/gdk/gdk.h
--- a/gdk/gdk.h
+++ b/gdk/gdk.h
@@ -2307,6 +2307,8 @@ gdk_export gdk_return BAToutercross(BAT
gdk_export gdk_return BATleftjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT
*sl, BAT *sr, bool nil_matches, BUN estimate)
__attribute__((__warn_unused_result__));
+gdk_export gdk_return BATmarkjoin(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT
*r, BAT *sl, BAT *sr, BUN estimate)
+ __attribute__((__warn_unused_result__));
gdk_export gdk_return BATouterjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT
*sl, BAT *sr, bool nil_matches, bool match_one, BUN estimate)
__attribute__((__warn_unused_result__));
gdk_export gdk_return BATthetajoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r, BAT
*sl, BAT *sr, int op, bool nil_matches, BUN estimate)
diff --git a/gdk/gdk_join.c b/gdk/gdk_join.c
--- a/gdk/gdk_join.c
+++ b/gdk/gdk_join.c
@@ -44,6 +44,13 @@
* equi-join, but the left output is sorted, and if there are
* multiple matches, only one is returned (i.e., the left output
* is also key, making it a candidate list)
+ * BATmarkjoin
+ * equi-join, but the left output is sorted, if there is no
+ * match for a value in the left input, there is still an output
+ * with NIL in the right output, and there is a third output column
+ * containing a flag that indicates the "certainty" of the match: 1
+ * there is a match, 0, there is no match and there are no NIL
+ * values, NIL, there is no match but there are NIL values
* BATthetajoin
* theta-join: an extra operator must be provided encoded as an
* integer (macros JOIN_EQ, JOIN_NE, JOIN_LT, JOIN_LE, JOIN_GT,
@@ -99,11 +106,11 @@ joinparamcheck(BAT *l, BAT *r1, BAT *r2,
/* Create the result bats for a join, returns the absolute maximum
* number of outputs that could possibly be generated. */
static BUN
-joininitresults(BAT **r1p, BAT **r2p, BUN lcnt, BUN rcnt, bool lkey, bool rkey,
- bool semi, bool nil_on_miss, bool only_misses, bool min_one,
- BUN estimate)
+joininitresults(BAT **r1p, BAT **r2p, BAT **r3p, BUN lcnt, BUN rcnt,
+ bool lkey, bool rkey, bool semi, bool nil_on_miss,
+ bool only_misses, bool min_one, BUN estimate)
{
- BAT *r1, *r2;
+ BAT *r1, *r2, *r3;
BUN maxsize, size;
/* if nil_on_miss is set, we really need a right output */
@@ -115,6 +122,8 @@ joininitresults(BAT **r1p, BAT **r2p, BU
*r1p = NULL;
if (r2p)
*r2p = NULL;
+ if (r3p)
+ *r3p = NULL;
if (lcnt == 0) {
/* there is nothing to match */
maxsize = 0;
@@ -173,6 +182,17 @@ joininitresults(BAT **r1p, BAT **r2p, BU
}
*r2p = r2;
}
+ if (r3p) {
+ r3 = COLnew(0, TYPE_bit, 0, TRANSIENT);
+ if (r3 == NULL) {
+ BBPreclaim(r1);
+ BBPreclaim(r2);
+ if (r2p)
+ *r2p = NULL;
+ return BUN_NONE;
+ }
+ *r3p = r3;
+ }
*r1p = r1;
return 0;
}
@@ -204,6 +224,22 @@ joininitresults(BAT **r1p, BAT **r2p, BU
r2->theap->dirty = true;
*r2p = r2;
}
+ if (r3p) {
+ BAT *r3 = COLnew(0, TYPE_bit, size, TRANSIENT);
+ if (r3 == NULL) {
+ BBPreclaim(r1);
+ BBPreclaim(r2);
+ return BUN_NONE;
+ }
+ r3->tnil = false;
+ r3->tnonil = true;
+ r3->tkey = false;
+ r3->tsorted = false;
+ r3->trevsorted = false;
+ r3->tseqbase = oid_nil;
+ r3->theap->dirty = true;
+ *r3p = r3;
+ }
return maxsize;
}
@@ -216,7 +252,7 @@ joininitresults(BAT **r1p, BAT **r2p, BU
#define APPEND(b, o) (((oid *) b->theap->base)[b->batCount++] = (o))
static inline gdk_return
-maybeextend(BAT *restrict r1, BAT *restrict r2,
+maybeextend(BAT *restrict r1, BAT *restrict r2, BAT *restrict r3,
BUN cnt, BUN lcur, BUN lcnt, BUN maxsize)
{
if (BATcount(r1) + cnt > BATcapacity(r1)) {
@@ -243,11 +279,17 @@ maybeextend(BAT *restrict r1, BAT *restr
return GDK_FAIL;
assert(BATcapacity(r1) == BATcapacity(r2));
}
+ if (r3) {
+ BATsetcount(r3, BATcount(r3));
+ if (BATextend(r3, newcap) != GDK_SUCCEED)
+ return GDK_FAIL;
+ assert(BATcapacity(r1) == BATcapacity(r3));
+ }
}
return GDK_SUCCEED;
}
-/* Return BATs through r1p and r2p for the case that there is no
+/* Return BATs through r1p, r2p, and r3p for the case that there is no
* match between l and r, taking all flags into consideration.
*
* This means, if nil_on_miss is set or only_misses is set, *r1p is a
@@ -255,10 +297,11 @@ maybeextend(BAT *restrict r1, BAT *restr
* values of l, and *r2p (if r2p is not NULL) is all nil. If neither
* of those flags is set, the result is two empty BATs. */
static gdk_return
-nomatch(BAT **r1p, BAT **r2p, BAT *l, BAT *r, struct canditer *restrict lci,
+nomatch(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r,
+ struct canditer *restrict lci, bit defmark,
bool nil_on_miss, bool only_misses, const char *func, lng t0)
{
- BAT *r1, *r2 = NULL;
+ BAT *r1, *r2 = NULL, *r3 = NULL;
MT_thread_setalgorithm(__func__);
if (lci->ncand == 0 || !(nil_on_miss | only_misses)) {
@@ -272,6 +315,14 @@ nomatch(BAT **r1p, BAT **r2p, BAT *l, BA
}
*r2p = r2;
}
+ if (r3p) {
+ if ((r3 = COLnew(0, TYPE_bit, 0, TRANSIENT)) == NULL) {
+ BBPreclaim(r1);
+ BBPreclaim(r2);
+ return GDK_FAIL;
+ }
+ *r3p = r3;
+ }
} else {
r1 = canditer_slice(lci, 0, lci->ncand);
if (r2p) {
@@ -281,16 +332,24 @@ nomatch(BAT **r1p, BAT **r2p, BAT *l, BA
}
*r2p = r2;
}
+ if (r3p) {
+ if ((r3 = BATconstant(0, TYPE_bit, &defmark,
lci->ncand, TRANSIENT)) == NULL) {
+ BBPreclaim(r1);
+ BBPreclaim(r2);
+ return GDK_FAIL;
+ }
+ *r3p = r3;
+ }
}
*r1p = r1;
TRC_DEBUG(ALGO, "l=" ALGOBATFMT ",r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT
",nil_on_miss=%s,only_misses=%s"
- " - > " ALGOBATFMT "," ALGOOPTBATFMT
+ " - > " ALGOBATFMT "," ALGOOPTBATFMT "," ALGOOPTBATFMT
" (%s -- " LLFMT "usec)\n",
ALGOBATPAR(l), ALGOBATPAR(r), ALGOOPTBATPAR(lci->s),
nil_on_miss ? "true" : "false",
only_misses ? "true" : "false",
- ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
+ ALGOBATPAR(r1), ALGOOPTBATPAR(r2), ALGOOPTBATPAR(r3),
func, GDKusec() - t0);
return GDK_SUCCEED;
}
@@ -299,7 +358,7 @@ nomatch(BAT **r1p, BAT **r2p, BAT *l, BA
* repeated multiple times) on the left. This means we can use a
* point select to find matches in the right column. */
static gdk_return
-selectjoin(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
+selectjoin(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r,
struct canditer *lci, struct canditer *rci,
bool nil_matches, bool nil_on_miss, bool semi, bool max_one, bool
min_one,
lng t0, bool swapped, const char *reason)
@@ -327,8 +386,9 @@ selectjoin(BAT **r1p, BAT **r2p, BAT *l,
(*ATOMcompare(li.type))(v, ATOMnilptr(li.type)) == 0) {
/* NIL doesn't match anything */
bat_iterator_end(&li);
- return nomatch(r1p, r2p, l, r, lci, nil_on_miss, false,
- reason, t0);
+ gdk_return rc = nomatch(r1p, r2p, r3p, l, r, lci, bit_nil,
nil_on_miss,
+ false, reason, t0);
+ return rc;
}
bn = BATselect(r, rci->s, v, NULL, true, true, false);
@@ -343,9 +403,11 @@ selectjoin(BAT **r1p, BAT **r2p, BAT *l,
GDKerror("not enough matches");
return GDK_FAIL;
}
- if (!nil_on_miss)
- return nomatch(r1p, r2p, l, r, lci, nil_on_miss, false,
- reason, t0);
+ if (!nil_on_miss) {
+ assert(r3p == NULL);
+ return nomatch(r1p, r2p, r3p, l, r, lci, 0, nil_on_miss,
+ false, reason, t0);
+ }
/* special case: return nil on RHS */
bncount = 1;
bn = NULL;
@@ -447,16 +509,39 @@ selectjoin(BAT **r1p, BAT **r2p, BAT *l,
BATsetcount(r2, lci->ncand * bncount);
*r2p = r2;
}
+ BAT *r3 = NULL;
+ if (r3p) {
+ bit mark;
+ if (bn) {
+ /* there is a match */
+ mark = 1;
+ } else if (r->tnonil) {
+ /* no match, no NIL in r */
+ mark = 0;
+ } else {
+ /* no match, search for NIL in r */
+ BAT *n = BATselect(r, rci->s, ATOMnilptr(r->ttype),
NULL, true, true, false);
+ if (n == NULL)
+ goto bailout;
+ mark = BATcount(n) == 0 ? 0 : bit_nil;
+ BBPreclaim(n);
+ }
+ r3 = BATconstant(0, TYPE_bit, &mark, lci->ncand, TRANSIENT);
+ if (r3 == NULL)
+ goto bailout;
+ *r3p = r3;
+ }
BBPreclaim(bn);
TRC_DEBUG(ALGO, "l=" ALGOBATFMT ","
"r=" ALGOBATFMT ",sl=" ALGOOPTBATFMT ","
"sr=" ALGOOPTBATFMT ",nil_matches=%s;%s %s "
- "-> " ALGOBATFMT "," ALGOOPTBATFMT " (" LLFMT "usec)\n",
+ "-> " ALGOBATFMT "," ALGOOPTBATFMT "," ALGOOPTBATFMT
+ " (" LLFMT "usec)\n",
ALGOBATPAR(l), ALGOBATPAR(r),
ALGOOPTBATPAR(lci->s), ALGOOPTBATPAR(rci->s),
nil_matches ? "true" : "false",
swapped ? " swapped" : "", reason,
- ALGOBATPAR(r1), ALGOOPTBATPAR(r2),
+ ALGOBATPAR(r1), ALGOOPTBATPAR(r2), ALGOOPTBATPAR(r3),
GDKusec() - t0);
return GDK_SUCCEED;
@@ -475,13 +560,14 @@ selectjoin(BAT **r1p, BAT **r2p, BAT *l,
#endif
/* Implementation of join where the right-hand side is dense, and if
- * there is a right candidate list, it too is dense. In case
- * nil_on_miss is not set, we use a range select (BATselect) to find
- * the matching values in the left column and then calculate the
- * corresponding matches from the right. If nil_on_miss is set, we
- * need to do some more work. */
+ * there is a right candidate list, it too is dense. This means there
+ * are no NIL values in r. In case nil_on_miss is not set, we use a
+ * range select (BATselect) to find the matching values in the left
+ * column and then calculate the corresponding matches from the right.
+ * If nil_on_miss is set, we need to do some more work. The latter is
+ * also the only case in which r3p van be set. */
static gdk_return
-mergejoin_void(BAT **r1p, BAT **r2p, BAT *l, BAT *r,
+mergejoin_void(BAT **r1p, BAT **r2p, BAT **r3p, BAT *l, BAT *r,
struct canditer *restrict lci, struct canditer *restrict rci,
bool nil_on_miss, bool only_misses, lng t0, bool swapped,
const char *reason)
@@ -489,7 +575,8 @@ mergejoin_void(BAT **r1p, BAT **r2p, BAT
oid lo, hi;
BUN i;
oid o, *o1p = NULL, *o2p = NULL;
- BAT *r1 = NULL, *r2 = NULL;
+ bit *m3p = NULL;
+ BAT *r1 = NULL, *r2 = NULL, *r3 = NULL;
bool ltsorted = false, ltrevsorted = false, ltkey = false;
/* r is dense, and if there is a candidate list, it too is
@@ -520,6 +607,7 @@ mergejoin_void(BAT **r1p, BAT **r2p, BAT
/* at this point, the matchable values in r are [lo..hi) */
if (!nil_on_miss) {
+ assert(r3p == NULL);
r1 = BATselect(l, lci->s, &lo, &hi, true, false, only_misses);
if (r1 == NULL)
return GDK_FAIL;
@@ -602,8 +690,9 @@ mergejoin_void(BAT **r1p, BAT **r2p, BAT
*r2p = r2;
goto doreturn2;
}
_______________________________________________
checkin-list mailing list -- [email protected]
To unsubscribe send an email to [email protected]
