Changeset: e5ace4ff55d6 for MonetDB URL: http://dev.monetdb.org/hg/MonetDB?cmd=changeset;node=e5ace4ff55d6 Modified Files: gdk/ChangeLog gdk/gdk.h gdk/gdk_aggr.c gdk/gdk_batop.c gdk/gdk_orderidx.c gdk/gdk_private.h sql/test/orderidx/Tests/simpletable.stable.out sql/test/orderidx/Tests/smalltable.stable.out Branch: default Log Message:
Produce order index as by product of BATsort, use it for quantiles. We produce the order index in BATsort if we need to return the ordering, or if the BAT being sorted is persistent. diffs (truncated from 613 to 300 lines): diff --git a/gdk/ChangeLog b/gdk/ChangeLog --- a/gdk/ChangeLog +++ b/gdk/ChangeLog @@ -2,6 +2,9 @@ # This file is updated with Maddlog * Fri Feb 17 2017 Sjoerd Mullender <[email protected]> +- BATsort may now create an order index as a by product. +- Quantile calculations now use the order index if available (and use + BATsort otherwise, producing an order index). - Quantiles calculate a position in the sorted column. If this position is not an integer, we now choose the nearest position, favoring the lower if the distance to the two adjacent positions is equal (round diff --git a/gdk/gdk.h b/gdk/gdk.h --- a/gdk/gdk.h +++ b/gdk/gdk.h @@ -844,7 +844,7 @@ typedef struct { PROPrec *props; /* list of dynamic properties stored in the bat descriptor */ } COLrec; -#define ORDERIDXOFF 2 +#define ORDERIDXOFF 3 /* assert that atom width is power of 2, i.e., width == 1<<shift */ #define assert_shift_width(shift,width) assert(((shift) == 0 && (width) == 0) || ((unsigned)1<<(shift)) == (unsigned)(width)) diff --git a/gdk/gdk_aggr.c b/gdk/gdk_aggr.c --- a/gdk/gdk_aggr.c +++ b/gdk/gdk_aggr.c @@ -2383,8 +2383,8 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, BAT *t1, *t2; BATiter bi; const void *v; - const void *nil; - int (*atomcmp)(const void *, const void *); + const void *nil = ATOMnilptr(tp); + int (*atomcmp)(const void *, const void *) = ATOMcompare(tp); const char *err; (void) abort_on_error; @@ -2394,9 +2394,9 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, return NULL; } assert(tp == b->ttype); - if (!ATOMlinear(b->ttype)) { + if (!ATOMlinear(tp)) { GDKerror("BATgroupquantile: cannot determine quantile on " - "non-linear type %s\n", ATOMname(b->ttype)); + "non-linear type %s\n", ATOMname(tp)); return NULL; } if (quantile < 0 || quantile > 1) { @@ -2404,12 +2404,11 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, "p=%f (p has to be in [0,1])\n", quantile); return NULL; } - assert(quantile >=0 && quantile <=1); if (BATcount(b) == 0 || ngrp == 0) { /* trivial: no values, thus also no quantiles, * so return bat aligned with e with nil in the tail */ - return BATconstant(ngrp == 0 ? 0 : min, tp, ATOMnilptr(tp), ngrp, TRANSIENT); + return BATconstant(ngrp == 0 ? 0 : min, tp, nil, ngrp, TRANSIENT); } if (s) { @@ -2431,11 +2430,17 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, * if g is given, sort g and subsort b so that we can get the * quantile for each group */ if (g) { + const oid *restrict grps; + oid prev; + BUN p, q, r; + if (BATtdense(g)) { /* singleton groups, so calculating quantile is * easy */ - bn = COLcopy(b, b->ttype, 0, TRANSIENT); + bn = COLcopy(b, tp, 0, TRANSIENT); BAThseqbase(bn, g->tseqbase); + if (freeb) + BBPunfix(b->batCacheid); if (freeg) BBPunfix(g->batCacheid); return bn; @@ -2446,33 +2451,22 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, BBPunfix(g->batCacheid); g = t1; freeg = 1; - } else { - t2 = NULL; - } - if (BATsort(&t1, NULL, NULL, b, t2, g, 0, 0) != GDK_SUCCEED) { - if (t2) + + if (BATsort(&t1, NULL, NULL, b, t2, g, 0, 0) != GDK_SUCCEED) { BBPunfix(t2->batCacheid); - goto bunins_failed; - } - if (freeb) - BBPunfix(b->batCacheid); - b = t1; - freeb = 1; - if (t2) + goto bunins_failed; + } + if (freeb) + BBPunfix(b->batCacheid); + b = t1; + freeb = 1; BBPunfix(t2->batCacheid); - bn = COLnew(g ? min : 0, b->ttype, ngrp, TRANSIENT); - if (bn == NULL) - goto bunins_failed; + bn = COLnew(min, tp, ngrp, TRANSIENT); + if (bn == NULL) + goto bunins_failed; - bi = bat_iterator(b); - nil = ATOMnilptr(b->ttype); - atomcmp = ATOMcompare(b->ttype); - - if (g) { /* we have to do this by group */ - const oid *restrict grps; - oid prev; - BUN p, q, r; + bi = bat_iterator(b); grps = (const oid *) Tloc(g, 0); prev = grps[0]; @@ -2480,11 +2474,13 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, * of the current group, respectively) */ for (r = 0, p = 1, q = BATcount(g); p <= q; p++) { assert(r < p); - if ( p == q || grps[p] != prev) { + if (p == q || grps[p] != prev) { BUN qindex; if (skip_nils && !b->tnonil) { - while (r < p && (*atomcmp)(BUNtail(bi, r), nil) == 0) - r++; + r = binsearch(NULL, 0, tp, Tloc(b, 0), + b->tvheap ? b->tvheap->base : NULL, + b->twidth, r, p, nil, + 1, 1); } if (r == p) { v = nil; @@ -2493,8 +2489,7 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, /* round *down* to nearest integer */ qindex = r + p - (BUN) (p + 0.5 - (p - r - 1) * quantile); /* be a little paranoid about the index */ - assert(qindex >= r); - assert(qindex < p); + assert(qindex >= r && qindex < p); v = BUNtail(bi, qindex); nils += (*atomcmp)(v, nil) == 0; } @@ -2509,25 +2504,67 @@ BATgroupquantile(BAT *b, BAT *g, BAT *e, while (BATcount(bn) < ngrp) { bunfastapp_nocheck(bn, BUNlast(bn), nil, Tsize(bn)); } - } else { /* quantiles for entire BAT b, EZ */ + BBPunfix(g->batCacheid); + } else { + BUN index, r, p = BATcount(b); + BAT *pb = NULL; + const oid *ords; - BUN index, r = 0, p = BATcount(b); + bn = COLnew(0, tp, 1, TRANSIENT); + if (bn == NULL) + goto bunins_failed; - if (skip_nils) { - while (r < p && (*atomcmp)(BUNtail(bi, r), nil) == 0) - r++; + t1 = NULL; + + if (BATcheckorderidx(b) || + (VIEWtparent(b) && + (pb = BBPdescriptor(VIEWtparent(b))) != NULL && + pb->theap.base == b->theap.base && + BATcount(pb) == BATcount(b) && + pb->hseqbase == b->hseqbase && + BATcheckorderidx(pb))) { + ords = (const oid *) (pb ? pb->torderidx->base : b->torderidx->base) + ORDERIDXOFF; + } else { + BATsort(NULL, &t1, NULL, b, NULL, g, 0, 0); + if (BATtdense(t1)) + ords = NULL; + else + ords = (const oid *) Tloc(t1, 0); } - index = r + p - (BUN) (p + 0.5 - (p - r - 1) * quantile); - v = BUNtail(bi, index); + + if (skip_nils && !b->tnonil) + r = binsearch(ords, 0, tp, Tloc(b, 0), + b->tvheap ? b->tvheap->base : NULL, + b->twidth, 0, p, + nil, 1, 1); + else + r = 0; + + if (r == p) { + /* no non-nil values, so quantile is nil */ + v = nil; + nils++; + } else { + bi = bat_iterator(b); + /* round (p-r-1)*quantile *down* to nearest + * integer (i.e., 1.49 and 1.5 are rounded to + * 1, 1.51 is rounded to 2) */ + index = r + p - (BUN) (p + 0.5 - (p - r - 1) * quantile); + if (ords) + index = ords[index] - b->hseqbase; + else + index = index + t1->tseqbase; + v = BUNtail(bi, index); + nils += (*atomcmp)(v, nil) == 0; + } + if (t1) + BBPunfix(t1->batCacheid); if (BUNappend(bn, v, FALSE) != GDK_SUCCEED) goto bunins_failed; - nils += (*atomcmp)(v, nil) == 0; } if (freeb) BBPunfix(b->batCacheid); - if (freeg) - BBPunfix(g->batCacheid); bn->tkey = BATcount(bn) <= 1; bn->tsorted = BATcount(bn) <= 1; diff --git a/gdk/gdk_batop.c b/gdk/gdk_batop.c --- a/gdk/gdk_batop.c +++ b/gdk/gdk_batop.c @@ -1248,8 +1248,8 @@ gdk_return BATsort(BAT **sorted, BAT **order, BAT **groups, BAT *b, BAT *o, BAT *g, int reverse, int stable) { - BAT *bn = NULL, *on = NULL, *gn; - oid *restrict grps, prev; + BAT *bn = NULL, *on = NULL, *gn, *pb = NULL; + oid *restrict grps, *restrict ords, prev; BUN p, q, r; if (b == NULL) { @@ -1281,6 +1281,11 @@ BATsort(BAT **sorted, BAT **order, BAT * /* no place to put result, so we're done quickly */ return GDK_SUCCEED; } + if (g == NULL && !stable) { + /* pre-ordering doesn't make sense if we're not + * subsorting and the sort is not stable */ + o = NULL; + } if (BATcount(b) <= 1 || ((reverse ? BATtrevordered(b) : BATtordered(b)) && o == NULL && g == NULL && @@ -1324,6 +1329,45 @@ BATsort(BAT **sorted, BAT **order, BAT * } return GDK_SUCCEED; } + if (VIEWtparent(b)) { + pb = BBPdescriptor(VIEWtparent(b)); + if (b->theap.base != pb->theap.base || + BATcount(b) != BATcount(pb) || + b->hseqbase != pb->hseqbase || + BATatoms[b->ttype].atomCmp != BATatoms[pb->ttype].atomCmp) + pb = NULL; + } else { + pb = b; + } + if (g == NULL && groups == NULL && o == NULL && !reverse && + pb != NULL && BATcheckorderidx(pb) && + /* if we want a stable sort, the order index must be + * stable, if we don't want stable, we don't care */ + (!stable || ((oid *) pb->torderidx->base)[2])) { + /* there is a order index that we can use */ + on = COLnew(pb->hseqbase, TYPE_oid, BATcount(pb), TRANSIENT); + if (on == NULL) + goto error; + memcpy(Tloc(on, 0), (oid *) pb->torderidx->base + ORDERIDXOFF, BATcount(pb) * sizeof(oid)); + BATsetcount(on, BATcount(b)); + on->tkey = 1; + on->tnil = 0; + on->tnonil = 1; + on->tsorted = on->trevsorted = 0; + on->tdense = 0; + if (sorted) { + bn = BATproject(on, b); + if (bn == NULL) + goto error; + bn->tsorted = 1; + *sorted = bn; + } + if (order) + *order = on; _______________________________________________ checkin-list mailing list [email protected] https://www.monetdb.org/mailman/listinfo/checkin-list
