Update of /cvsroot/monetdb/pathfinder/runtime
In directory sc8-pr-cvs16:/tmp/cvs-serv11078/runtime
Modified Files:
ll_prec_foll.mx pf_support.mx
Log Message:
added kind-test push-down for loop-lifted following step.
This speeds up the query reported by JanR in bug report #1654317
"XQ: following step kills Mserver (after 2h)"
(http://sourceforge.net/tracker/index.php?func=detail&aid=1654317&group_id=56967&atid=482468)
from ~45 secs to ~25 secs with the ALG backend
(on a 2 GHz Opteron with 8 GB RAM; Mserver grows to 4/8 GB res/virt);
(MPS version not tested, yet)
Declaration/disclaimer:
-----------------------
On my FC6 desktop (64-bit, 64-bit OIDs, configured with --enable-optimize,
compiled with gcc 4.1.1), this check-in does not make any pathfinder test
fail that did not also fail with the most recent code base in CVS prior to
this check-in.
I did not check in detail, though, whether all previously failing tests
still fail the same way after this check-in as they did before this
check-in.
Index: ll_prec_foll.mx
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/runtime/ll_prec_foll.mx,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- ll_prec_foll.mx 15 May 2007 11:40:15 -0000 1.2
+++ ll_prec_foll.mx 15 May 2007 14:19:32 -0000 1.3
@@ -87,26 +87,30 @@
/* FOLLOWING STEP */
int
-PFll_following(BAT **result, BAT *iter_bat, BAT *ctx_bat, BAT *pre_size, BAT
*doc_pre/*, int *upperbound*/)
+PFll_following(BAT **result, BAT *iter_bat, BAT *ctx_bat, BAT *doc_pre, BAT
*pre_size, BAT *pre_kind, chr *_kind_test)
{
+ @:init(following)@
+
@= init
char *name = "[EMAIL PROTECTED]";
BUN p = 0, q = 0;
int xx = 0, *size = 0;
+ chr *kind = 0, kind_test = *_kind_test;
size_t res_size = 0, grow = 0;
BAT *res = 0;
oid *iter_cur = 0, *iter_end = 0, *ctx_cur = 0, *ctx_end = 0, *res_cur = 0;
int iter_nxt = 0, ctx_nxt = 0;
bit one_ctx = 0;
- oid min_iter = 0, max_iter = 0, num_iter = 0;
+ oid min_iter = 0, max_iter = 0, num_iter = 0, ctx_max = 0;
/* --------------------------- checks ---------------------------------- */
BATcheck(iter_bat, name);
BATcheck(ctx_bat, name);
- BATcheck(pre_size, name);
BATcheck(doc_pre, name);
+ BATcheck(pre_size, name);
+ BATcheck(pre_kind, name);
iter_cur = (oid*) BUNtail(iter_bat, BUNfirst(iter_bat));
iter_end = (oid*) BUNtail(iter_bat, BUNlast(iter_bat));
@@ -115,11 +119,12 @@
ctx_cur = (oid*) BUNtail(ctx_bat, BUNfirst(ctx_bat));
ctx_end = (oid*) BUNtail(ctx_bat, BUNlast(ctx_bat));
ctx_nxt = BUNsize(ctx_bat)/sizeof(oid);
- one_ctx = *ctx_cur == *(ctx_end - ctx_nxt);
+ ctx_max = *(ctx_end - ctx_nxt);
+ one_ctx = *ctx_cur == ctx_max;
ALGODEBUG
- THRprintf(GDKout, "%s: |iter_bat|="SZFMT", |ctx_bat|="SZFMT",
|pre_size|="SZFMT", |doc_pre|="SZFMT", one_ctx=%d\n",
- name, BATcount(iter_bat), BATcount(ctx_bat),
BATcount(pre_size), BATcount(doc_pre), (int)one_ctx);
+ THRprintf(GDKout, "%s: |iter_bat|="SZFMT", |ctx_bat|="SZFMT",
|doc_pre|="SZFMT", |pre_size|="SZFMT", |pre_kind|="SZFMT", kind_test=%d,
one_ctx=%d\n",
+ name, BATcount(iter_bat), BATcount(ctx_bat),
BATcount(doc_pre), BATcount(pre_size), BATcount(pre_kind), (int)kind_test,
(int)one_ctx);
if (!(BAThdense(iter_bat) && BAThdense(ctx_bat)))
{
@@ -142,6 +147,12 @@
return GDK_FAIL;
}
+ if (!(BATtordered(doc_pre) & 1))
+ {
+ GDKerror("%s: doc_pre must be ordered on tail.\n", name);
+ return GDK_FAIL;
+ }
+
if (!BAThdense(pre_size))
{
GDKerror("%s: head of pre_size must be dense.\n", name);
@@ -157,12 +168,36 @@
GDKerror("%s: head (oid) of pre_size must NOT be materialized.\n",
name);
return GDK_FAIL;
}
-
- if (!(BATtordered(doc_pre) & 1))
+ if (*ctx_cur < pre_size->hseqbase || ctx_max >= pre_size->hseqbase +
BATcount(pre_size))
{
- GDKerror("%s: doc_pre must be ordered on tail.\n", name);
+ GDKerror("%s: context nodes exceed collection range.\n", name);
return GDK_FAIL;
}
+ size = ((int*) BUNtloc(pre_size, BUNfirst(pre_size))) -
(int)pre_size->hseqbase;
+
+ if (kind_test != chr_nil) {
+ if (!BAThdense(pre_kind))
+ {
+ GDKerror("%s: head of pre_kind must be dense.\n", name);
+ return GDK_FAIL;
+ }
+ if ((pre_size->hseqbase != pre_kind->hseqbase) || (BATcount(pre_size)
!= BATcount(pre_kind)))
+ {
+ GDKerror("%s: pre_size and pre_kind must be head-aligned, i.e.,
have equal head seqbases and length.\n", name);
+ return GDK_FAIL;
+ }
+ if (pre_kind->ttype != TYPE_chr)
+ {
+ GDKerror("%s: tail of pre_kind must be type CHR.\n", name);
+ return GDK_FAIL;
+ }
+ if (BUNsize(pre_kind) != sizeof(chr))
+ {
+ GDKerror("%s: head (oid) of pre_kind must NOT be materialized.\n",
name);
+ return GDK_FAIL;
+ }
+ kind = ((chr*) BUNtloc(pre_kind, BUNfirst(pre_kind))) -
(int)pre_kind->hseqbase;
+ }
/* --------------------------- empty result ---------------------------- */
@@ -182,9 +217,7 @@
return GDK_SUCCEED;
}
- /* --------------------------- special cases --------------------------- */
-
- size = ((int*) BUNtloc(pre_size, BUNfirst(pre_size))) -
(int)pre_size->hseqbase;
+ /* --------------------------- analyze iters --------------------------- */
if (BATtordered(iter_bat) & 1)
{
@@ -208,6 +241,7 @@
name, min_iter, max_iter, num_iter);
/* --- result bat allocation. for result size use res_size parameter --- */
+
res_size = num_iter * ((BATcount(pre_size) / 2) / BATcount(doc_pre));
res = BATnew(TYPE_oid, TYPE_oid, res_size);
if (res == NULL)
@@ -217,10 +251,18 @@
}
assert(BUNsize(res) == 2 * sizeof(oid));
assert((res->hloc == 0) && (res->tloc == sizeof(oid)));
- res_cur = (oid*) BUNhead(res, BUNlast(res));
+ res_cur = (oid*) BUNhead(res, BUNlast(res));
+@
@c
- @:init(following)@
+ /* ------------------------- actual algorithm -------------------------- */
+ if (kind_test != chr_nil) {
+ @:ll_foll(if (kind[cur_following] == kind_test))@
+ } else {
+ @:ll_foll()@
+ }
+
[EMAIL PROTECTED] ll_foll
if (one_ctx) {
/* 1 ctx, 1/n iter */
p = SORTfndlast(doc_pre, ctx_cur);
@@ -239,8 +281,11 @@
while(cur_following < boundary) {
int sz = size[cur_following];
if (sz >= 0) {
- *res_cur++ = min_iter;
- *res_cur++ = cur_following++;
+ @1 {
+ *res_cur++ = min_iter;
+ *res_cur++ = cur_following;
+ }
+ cur_following++;
} else {
/* this node has been deleted! skip the hole */
cur_following += 1 + (sz & ~(1<<31));
@@ -253,10 +298,12 @@
while(cur_following < boundary) {
int sz = size[cur_following];
if (sz >= 0) {
- oid *cur_iter = iter_cur;
- for (; cur_iter < iter_end; cur_iter +=
iter_nxt) {
- *res_cur++ = *cur_iter;
- *res_cur++ = cur_following;
+ @1 {
+ oid *cur_iter = iter_cur;
+ for (; cur_iter < iter_end; cur_iter +=
iter_nxt) {
+ *res_cur++ = *cur_iter;
+ *res_cur++ = cur_following;
+ }
}
cur_following++;
} else {
@@ -270,13 +317,15 @@
while(cur_following < boundary) {
int sz = size[cur_following];
if (sz >= 0) {
- oid *cur_iter = iter_cur;
- oid prev_iter = oid_nil;
- for (; cur_iter < iter_end; cur_iter +=
iter_nxt) {
- if (*cur_iter != prev_iter) {
- *res_cur++ = *cur_iter;
- *res_cur++ = cur_following;
- prev_iter = *cur_iter;
+ @1 {
+ oid *cur_iter = iter_cur;
+ oid prev_iter = oid_nil;
+ for (; cur_iter < iter_end; cur_iter +=
iter_nxt) {
+ if (*cur_iter != prev_iter) {
+ *res_cur++ = *cur_iter;
+ *res_cur++ = cur_following;
+ prev_iter = *cur_iter;
+ }
}
}
cur_following++;
@@ -321,8 +370,11 @@
while(cur_following < boundary) {
int sz = size[cur_following];
if (sz >= 0) {
- *res_cur++ = min_iter;
- *res_cur++ = cur_following++;
+ @1 {
+ *res_cur++ = min_iter;
+ *res_cur++ = cur_following;
+ }
+ cur_following++;
} else {
/* this node has been deleted! skip the hole */
cur_following += 1 + (sz & ~(1<<31));
@@ -387,10 +439,12 @@
while(cur_following < boundary) {
int sz = size[cur_following];
if (sz >= 0) {
- for (iter = fst_iter; iter <= lst_iter; iter++) {
- if (min_following[iter] <= cur_following) {
- *res_cur++ = iter + min_iter;
- *res_cur++ = cur_following;
+ @1 {
+ for (iter = fst_iter; iter <= lst_iter; iter++) {
+ if (min_following[iter] <= cur_following) {
+ *res_cur++ = iter + min_iter;
+ *res_cur++ = cur_following;
+ }
}
}
cur_following++;
@@ -406,6 +460,9 @@
}
GDKfree(min_following);
}
+@
[EMAIL PROTECTED]
+ @:end@
@= end
/* -------------------- set result properties ---------------------- */
@@ -442,8 +499,8 @@
*result = res;
return GDK_SUCCEED;
+@
@c
- @:end@
}
@@ -489,6 +546,7 @@
}
}
}
+
@:end@
}
@)
Index: pf_support.mx
===================================================================
RCS file: /cvsroot/monetdb/pathfinder/runtime/pf_support.mx,v
retrieving revision 1.229
retrieving revision 1.230
diff -u -d -r1.229 -r1.230
--- pf_support.mx 14 May 2007 10:03:11 -0000 1.229
+++ pf_support.mx 15 May 2007 14:19:32 -0000 1.230
@@ -279,13 +279,17 @@
@= ll_prec_foll_decl
.COMMAND [EMAIL PROTECTED](BAT[oid,oid] iter,
BAT[oid,oid] ctx,
+ BAT[oid,oid] doc_pre,
BAT[oid,int] pre_size,
- BAT[oid,oid] doc_pre): BAT[oid,oid] = [EMAIL PROTECTED];
+ BAT[oid,chr] pre_kind,
+ chr kind_test): BAT[oid,oid] = [EMAIL PROTECTED];
"PARAMETERS:
BAT[void,oid] iter (grouping relation; sorted on tail within each ctx group)
BAT[void,oid] ctx (context set; sorted on tail)
+BAT[void,oid] doc_pre (table of document containers; doc id, preorder start
value)
BAT[void,int] pre_size (from the working set)
-BAT[void,oid] table of document containers (doc id, preorder start value)
+BAT[void,chr] pre_kind (from the working set)
+chr kind_test (kind to test for; chr_nil if no kind test)
DESCRIPTION:
returns all nodes on the @2 axis of the ctx-nodes duplicate free for each
group."
@m
@@ -1719,12 +1723,19 @@
@
@= ll_prec_foll_impl
-PROC @1(BAT[void,oid] iter, BAT[void,oid] item, oid cont, BAT[void,bat] ws,
int order) : BAT[void,bat]
+PROC @1(BAT[void,oid] iter, BAT[void,oid] item, oid cont, BAT[void,bat] ws,
int order, chr kind_test) : BAT[void,bat]
{
# "order" is not (yet?) used, here.
- var pre_sizes := ws.fetch(PRE_SIZE).fetch(cont);
@:foll_prec_code@
- var res := [EMAIL PROTECTED](iter.chk_order(), item.chk_order(),
pre_sizes, doc_pre);
+ var pre_sizes := ws.fetch(PRE_SIZE).fetch(cont);
+ var pre_kinds;
+ if (isnil(kind_test)) {
+ # no kind test
+ pre_kinds := new(void,chr,0).seqbase([EMAIL
PROTECTED]).access(BAT_READ);
+ } else {
+ pre_kinds := ws.fetch(PRE_KIND).fetch(cont);
+ }
+ var res := [EMAIL PROTECTED](iter.chk_order(), item.chk_order(), doc_pre,
pre_sizes, pre_kinds, kind_test);
var result := new(void,bat,2).seqbase([EMAIL
PROTECTED]).append(hmark(res,[EMAIL PROTECTED])).append(tmark(res,[EMAIL
PROTECTED])).access(BAT_READ);
@:post_sort_output@
@@ -1734,6 +1745,7 @@
@
@mil
+@:loop_lifted_scj_step1(parent)@
@:loop_lifted_scj_step1(ancestor)@
@:loop_lifted_scj_step1(ancestor_or_self)@
@@ -1741,10 +1753,10 @@
@:loop_lifted_scj_wrap1(descendant)@
@:loop_lifted_scj_wrap1(descendant_or_self)@
-@:loop_lifted_scj_step1(parent)@
-@:loop_lifted_scj_step1(following)@
-@:loop_lifted_scj_step1(following_sibling)@
+@:loop_lifted_scj_step1x(following)@
@:loop_lifted_scj_step1(preceding)@
+
+@:loop_lifted_scj_step1(following_sibling)@
@:loop_lifted_scj_step1(preceding_sibling)@
@
#==================================================================
@@ -1781,8 +1793,12 @@
@= nsloc_params
, ns, loc
@
[EMAIL PROTECTED] params1
+, kind_test
+@
@= params2
, cands, kind_test
+@
@= postfilter
if (postfilter) {
var pre_cont := ws.fetch(PRE_CONT).fetch(contID);
@@ -1905,6 +1921,14 @@
@:loop_lifted_scj_step2(@1,_with_loc_test, @:loc_args@, @:loc_params@,
@:loc_post@ ,,)@
@:loop_lifted_scj_step2(@1,_with_target_test,@:tgt_args@, @:tgt_params@,
@:target_post@ ,,)@
@
[EMAIL PROTECTED] loop_lifted_scj_step1x
+@:loop_lifted_scj_step2(@1,,,,,
@:params1@,)@
+@:loop_lifted_scj_step2(@1,_with_kind_test, @:kind_args@, @:kind_params@,,
@:params1@,kind_test := kind;)@
+@:loop_lifted_scj_step2(@1,_with_nsloc_test,
@:nsloc_args@,@:nsloc_params@,@:nsloc_post@, @:params1@,)@
+@:loop_lifted_scj_step2(@1,_with_ns_test, @:ns_args@, @:ns_params@,
@:ns_post@, @:params1@,)@
+@:loop_lifted_scj_step2(@1,_with_loc_test, @:loc_args@, @:loc_params@,
@:loc_post@, @:params1@,)@
+@:loop_lifted_scj_step2(@1,_with_target_test,@:tgt_args@, @:tgt_params@,
@:target_post@, @:params1@,)@
+@
#==================================================================
# actual definition of the scj proc
@= loop_lifted_scj_per_cont
-------------------------------------------------------------------------
This SF.net email is sponsored by DB2 Express
Download DB2 Express C - the FREE version of DB2 express and take
control of your XML. No limits. Just data. Click to get it now.
http://sourceforge.net/powerbar/db2/
_______________________________________________
Monetdb-pf-checkins mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/monetdb-pf-checkins
