Changeset: d62a2cdd371b for MonetDB
URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=d62a2cdd371b
Modified Files:
MonetDB5/src/modules/mal/pqueue.mx
MonetDB5/src/optimizer/opt_mergetable.mx
MonetDB5/src/optimizer/opt_prelude.mx
MonetDB5/src/optimizer/opt_support.mx
sql/rel.txt
sql/src/backends/monet5/sql_gencode.mx
sql/src/include/sql_relation.h
sql/src/server/bin_optimizer.mx
sql/src/server/rel_bin.mx
sql/src/server/rel_optimizer.mx
sql/src/server/sql_statement.mx
Branch: Oct2010
Log Message:
handle the full topn/slice + projection joins in a consistent way.
ie push tonp/slice though the parts of the mat and in the second
phase merge and repeat the topn/slice operants. For slice in the
first run we need to ignore the offset.
After the second phase the projection columns need to first project
using the first phase results (ie per part) then merge and project
against the second phase result.
This required a new topn operator with 2 column inputs (ie handle
topn over multicolumns).
diffs (truncated from 1480 to 300 lines):
diff -r 033e855d37d5 -r d62a2cdd371b MonetDB5/src/modules/mal/pqueue.mx
--- a/MonetDB5/src/modules/mal/pqueue.mx Fri Sep 03 17:31:30 2010 +0200
+++ b/MonetDB5/src/modules/mal/pqueue.mx Sun Sep 05 23:18:01 2010 +0200
@@ -54,19 +54,19 @@
address pqdeque...@1@2
comment "Removes top element of the @2-pqueue and updates it";
-command to...@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:@1]
+command to...@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:oid]
address pqto...@1@2
comment "Return the topn elements of the bat t using a @2-pqueue";
-command to...@2(t:bat[:void,:@1], n:wrd) :bat[:oid,:@1]
+command to...@2(t:bat[:void,:@1], n:wrd) :bat[:oid,:oid]
address pqto...@1@2
comment "Return the topn elements of the bat t using a @2-pqueue";
-command uto...@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:@1]
+command uto...@2(t:bat[:oid,:@1], n:wrd) :bat[:oid,:oid]
address pquto...@1@2
comment "Return the unique topn elements of the bat t using a @2-pqueue";
-command uto...@2(t:bat[:void,:@1], n:wrd) :bat[:oid,:@1]
+command uto...@2(t:bat[:void,:@1], n:wrd) :bat[:oid,:oid]
address pquto...@1@2
comment "Return the unique topn elements of the bat t using a @2-pqueue";
@@ -83,22 +83,38 @@
address pqdequeue_...@1
comment "Removes top element of the @1-pqueue and updates it";
-command to...@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:any_1]
+command to...@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
address pqtopn_...@1
comment "Return the topn elements of the bat t using a @1-pqueue";
-command to...@1(t:bat[:void,:any_1], n:wrd) :bat[:oid,:any_1]
+command to...@1(t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
address pqtopn_...@1
comment "Return the topn elements of the bat t using a @1-pqueue";
-command uto...@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:any_1]
+command uto...@1(t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
address pqutopn_...@1
comment "Return the unique topn elements of the bat t using a @1-pqueue";
-command uto...@1(t:bat[:void,:any_1], n:wrd) :bat[:oid,:any_1]
+command uto...@1(t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
address pqutopn_...@1
comment "Return the unique topn elements of the bat t using a @1-pqueue";
+command to...@1(a:bat[:oid,:oid], t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
+address pqtopn2_...@1
+comment "Return the topn elements of the bat t using a @1-pqueue";
+
+command to...@1(a:bat[:oid,:oid], t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
+address pqtopn2_...@1
+comment "Return the topn elements of the bat t using a @1-pqueue";
+
+command uto...@1(a:bat[:oid,:oid], t:bat[:oid,:any_1], n:wrd) :bat[:oid,:oid]
+address pqutopn2_...@1
+comment "Return the unique topn elements of the bat t using a @1-pqueue";
+
+command uto...@1(a:bat[:oid,:oid], t:bat[:void,:any_1], n:wrd) :bat[:oid,:oid]
+address pqutopn2_...@1
+comment "Return the unique topn elements of the bat t using a @1-pqueue";
+
@= mel_pqueue_any
@:mel_minmax_any(min)@
@:mel_minmax_any(max)@
@@ -308,8 +324,31 @@
/* TopN, based on @2-pqueue */
+static BAT *
+heap2b...@1@2( BAT *h )
+{
+ BAT *r, *n = BATnew(TYPE_oid, TYPE_oid, BATcount(h));
+ BUN f = BUNfirst(h);
+ oid *o = (oid*)Hloc(h, f), oo = *o;
+ @1 *v = (@1*)Tloc(h, f), ov = *v;
+
+ for(f = BUNfirst(h); f < BUNlast(h); f = BUNfirst(h)) {
+ o = (oid*)Hloc(h, f);
+ v = (@1*)Tloc(h, f);
+ if (ov != *v) {
+ oo = *o;
+ ov = *v;
+ }
+ BUNins(n, o, &oo, FALSE);
+ pqueue_deque...@1@2(h);
+ }
+ r = BATrevert(n);
+ return r;
+}
+
int pqueue_topn_v...@1@2(BAT **H, BAT *t, wrd *N)
{
+ BAT *h = NULL;
BATiter ti = bat_iterator(t);
@1 *v;
BUN i, n = BATcount(t);
@@ -317,38 +356,43 @@
if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX && (BUN) *N < n)
n = (BUN) *N;
- if (do_pqueue_init(H,t,n) == GDK_FAIL)
+ if (do_pqueue_init(&h,t,n) == GDK_FAIL)
return GDK_FAIL;
v = (@1*)BUNtail(ti,BUNfirst(t));
for(i=0; i<n; i++, idx++, v++) {
- pqueue_enque...@1@2(*H, &idx, v);
+ pqueue_enque...@1@2(h, &idx, v);
}
n = BATcount(t);
for(; i<n; i++, idx++, v++) {
- pqueue_toprepla...@1@2(*H, &idx, v);
+ pqueue_toprepla...@1@2(h, &idx, v);
}
+ *H = heap2b...@1@2(h);
+ BBPunfix(h->batCacheid);
return GDK_SUCCEED;
}
int pqueue_to...@1@2(BAT **H, BAT *t, wrd *N)
{
+ BAT *h = NULL;
BATiter ti = bat_iterator(t);
BUN i, n = BATcount(t);
BUN p = BUNfirst(t);
if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX && (BUN) *N < n)
n = (BUN) *N;
- if (do_pqueue_init(H,t,n) == GDK_FAIL)
+ if (do_pqueue_init(&h,t,n) == GDK_FAIL)
return GDK_FAIL;
for(i=0; i<n; i++, p++) {
- pqueue_enque...@1@2(*H, (oid*)BUNhloc(ti,p), (@1*)BUNtloc(ti,p));
+ pqueue_enque...@1@2(h, (oid*)BUNhloc(ti,p), (@1*)BUNtloc(ti,p));
}
n = BATcount(t);
for(; i<n; i++, p++) {
- pqueue_toprepla...@1@2(*H, (oid*)BUNhloc(ti,p), (@1*)BUNtloc(ti,p));
+ pqueue_toprepla...@1@2(h, (oid*)BUNhloc(ti,p), (@1*)BUNtloc(ti,p));
}
+ *H = heap2b...@1@2(h);
+ BBPunfix(h->batCacheid);
return GDK_SUCCEED;
}
@@ -397,10 +441,14 @@
}
}
}
- b = BATjoin(BATmirror(duplicates), *H, BATcount(duplicates));
+ b = heap2b...@1@2(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = VIEWcombine(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = BATleftjoin(*H, duplicates, BATcount(duplicates));
BBPunfix((*H)->batCacheid);
BBPunfix(duplicates->batCacheid);
- *H = b;
+ *H = BATmirror(b);
return GDK_SUCCEED;
}
@@ -448,10 +496,14 @@
}
}
}
- b = BATjoin(BATmirror(duplicates), *H, BATcount(duplicates));
- BBPunfix((*H)->batCacheid);
+ b = heap2b...@1@2(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = VIEWcombine(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = BATleftjoin(*H, duplicates, BATcount(duplicates));
+ BBPunfix((*H)->batCacheid);
BBPunfix(duplicates->batCacheid);
- *H = b;
+ *H = BATmirror(b);
return GDK_SUCCEED;
}
@c
@@ -480,12 +532,13 @@
BUN hbase;
BUN ins,cur;
BUN p, posel;
- unsigned short ts = Tsize(h);
+ unsigned short ts;
hbase = BUNfirst(h);
posel = BATcount(h); /*last position*/
BUNins(h, (ptr)idx, (ptr)el, FALSE);
+ ts = Tsize(h);
ins = hbase+posel;
while(posel >0) {
@@ -592,8 +645,33 @@
return GDK_SUCCEED;
}
+static BAT *
+heap2bat_...@1( BAT *h )
+{
+ BATiter hi = bat_iterator(h);
+ BAT *r, *n = BATnew(TYPE_oid, TYPE_oid, BATcount(h));
+ BUN f = BUNfirst(h);
+ oid *o = (oid*)Hloc(h, f), oo = *o;
+ ptr v = (ptr)BUNtail(hi, f), ov = v;
+ int tpe = h->ttype;
+
+ for(f = BUNfirst(h); f < BUNlast(h); f = BUNfirst(h)) {
+ o = (oid*)Hloc(h, f);
+ v = (ptr)BUNtail(hi, f);
+ if (atom_CMP(ov,v, tpe) != 0) {
+ oo = *o;
+ ov = v;
+ }
+ BUNins(n, o, &oo, FALSE);
+ pqueue_dequeue_...@1(h);
+ }
+ r = BATrevert(n);
+ return r;
+}
+
int pqueue_topn_void...@1(BAT **H, BAT *t, wrd *N)
{
+ BAT *h = NULL;
BATiter ti = bat_iterator(t);
BUN i, n = BATcount(t);
oid idx = t->hseqbase;
@@ -602,21 +680,24 @@
if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX && (BUN) *N < n)
n = (BUN) *N;
- if (do_pqueue_init(H,t,n) == GDK_FAIL)
+ if (do_pqueue_init(&h,t,n) == GDK_FAIL)
return GDK_FAIL;
for(i=0; i<n; i++, idx++, p++) {
- pqueue_enqueue_...@1(*H, &idx, BUNtail(ti,p), tpe);
+ pqueue_enqueue_...@1(h, &idx, BUNtail(ti,p), tpe);
}
n = BATcount(t);
for(; i<n; i++, idx++, p++) {
- pqueue_topreplace_...@1(*H, &idx, BUNtail(ti,p), tpe);
+ pqueue_topreplace_...@1(h, &idx, BUNtail(ti,p), tpe);
}
+ *H = heap2bat_...@1(h);
+ BBPunfix(h->batCacheid);
return GDK_SUCCEED;
}
int pqueue_topn_...@1(BAT **H, BAT *t, wrd *N)
{
+ BAT *h = NULL;
BATiter ti = bat_iterator(t);
BUN i, n = BATcount(t);
BUN p = BUNfirst(t);
@@ -624,16 +705,18 @@
if (*N != wrd_nil && *N >= 0 && *N <= (wrd) BUN_MAX && (BUN) *N < n)
n = (BUN) *N;
- if (do_pqueue_init(H,t,n) == GDK_FAIL)
+ if (do_pqueue_init(&h,t,n) == GDK_FAIL)
return GDK_FAIL;
for(i=0; i<n; i++, p++) {
- pqueue_enqueue_...@1(*H, (oid*)BUNhloc(ti,p), BUNtail(ti,p), tpe);
+ pqueue_enqueue_...@1(h, (oid*)BUNhloc(ti,p), BUNtail(ti,p), tpe);
}
n = BATcount(t);
for(; i<n; i++, p++) {
- pqueue_topreplace_...@1(*H, (oid*)BUNhloc(ti,p), BUNtail(ti,p), tpe);
+ pqueue_topreplace_...@1(h, (oid*)BUNhloc(ti,p), BUNtail(ti,p), tpe);
}
+ *H = heap2bat_...@1(h);
+ BBPunfix(h->batCacheid);
return GDK_SUCCEED;
}
@@ -684,10 +767,14 @@
}
}
}
- b = BATjoin(BATmirror(duplicates), *H, BATcount(duplicates));
- BBPunfix((*H)->batCacheid);
+ b = heap2bat_...@1(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = VIEWcombine(*H);
+ BBPunfix((*H)->batCacheid); *H = b;
+ b = BATleftjoin(*H, duplicates, BATcount(duplicates));
+ BBPunfix((*H)->batCacheid);
BBPunfix(duplicates->batCacheid);
- *H = b;
_______________________________________________
Checkin-list mailing list
[email protected]
http://mail.monetdb.org/mailman/listinfo/checkin-list
