001 /*
002 // $Id: //open/mondrian/src/main/mondrian/rolap/agg/Aggregation.java#56 $
003 // This software is subject to the terms of the Common Public License
004 // Agreement, available at the following URL:
005 // http://www.opensource.org/licenses/cpl.html.
006 // Copyright (C) 2001-2008 Julian Hyde and others
007 // Copyright (C) 2001-2002 Kana Software, Inc.
008 // All Rights Reserved.
009 // You must accept the terms of that agreement to use this software.
010 //
011 // jhyde, 28 August, 2001
012 */
013
014 package mondrian.rolap.agg;
015
016 import mondrian.olap.*;
017 import mondrian.rolap.*;
018
019 import java.io.PrintWriter;
020 import java.lang.ref.SoftReference;
021 import java.util.*;
022 import java.util.concurrent.CopyOnWriteArrayList;
023
024 /**
025 * A <code>Aggregation</code> is a pre-computed aggregation over a set of
026 * columns.
027 *
028 * <p>Rollup operations:<ul>
029 * <li>drop an unrestricted column (e.g. state=*)</li>
030 * <li>tighten any restriction (e.g. year={1997,1998} becomes
031 * year={1997})</li>
032 * <li>restrict an unrestricted column (e.g. year=* becomes
033 * year={1997})</li>
034 * </ul>
035 *
036 * <p>Representation of aggregations. Sparse and dense representations are
037 * necessary for different data sets. Should adapt automatically. Use an
038 * interface to hold the data set, so the segment doesn't care.</p>
039 *
040 * Suppose we have a segment {year=1997, quarter={1,2,3},
041 * state={CA,WA}}. We want to roll up to a segment for {year=1997,
042 * state={CA,WA}}. We need to know that we have all quarters. We don't.
043 * Because year and quarter are independent, we know that we have all of
044 * the ...</p>
045 *
046 * <p>Suppose we have a segment specified by {region=West, state=*,
047 * year=*}, which materializes to ({West}, {CA,WA,OR}, {1997,1998}).
048 * Because state=*, we can rollup to {region=West, year=*} or {region=West,
049 * year=1997}.</p>
050 *
051 * <p>The space required for a segment depends upon the dimensionality (d),
052 * cell count (c) and the value count (v). We don't count the space
053 * required for the actual values, which is the same in any scheme.</p>
054 *
055 * @author jhyde
056 * @version $Id: //open/mondrian/src/main/mondrian/rolap/agg/Aggregation.java#56 $
057 * @since 28 August, 2001
058 */
059 public class Aggregation {
060
061 /**
062 * The key that uniquely identify this Aggregation. It is also used
063 * to lookup Aggregation.
064 */
065 private AggregationKey aggregationKey;
066
067 /**
068 * Setting for optimizing sql predicates.
069 */
070 private int maxConstraints;
071
072 /**
073 * List of soft references to segments.
074 * This List implementation should be Thread safe on all mutative operations
075 * (add, set, and so on). Access to this list is not synchronized in the code.
076 * This is the only mutable field in the class.
077 */
078 private final List<SoftReference<Segment>> segmentRefs;
079
080 /**
081 * Timestamp of when the aggregation was created. (We use
082 * {@link java.util.Date} rather than {@link java.sql.Timestamp} because it
083 * has less baggage.)
084 */
085 private final Date creationTimestamp;
086
087 /**
088 * This is set in the load method and is used during
089 * the processing of a particular aggregate load.
090 */
091 private RolapStar.Column[] columns;
092
093 /**
094 * Creates an Aggregation.
095 *
096 * @param aggregationKey the key specifying the axes, the context and
097 * the RolapStar for this Aggregation
098 */
099 public Aggregation(
100 AggregationKey aggregationKey) {
101 this.segmentRefs = getThreadSafeListImplementation();
102 this.maxConstraints =
103 MondrianProperties.instance().MaxConstraints.get();
104 this.creationTimestamp = new Date();
105 this.aggregationKey = aggregationKey;
106
107 }
108
109 private CopyOnWriteArrayList<SoftReference<Segment>> getThreadSafeListImplementation() {
110 return new CopyOnWriteArrayList<SoftReference<Segment>>();
111 }
112
113 /**
114 * @return Returns the timestamp when the aggregation was created
115 */
116 public Date getCreationTimestamp() {
117 return creationTimestamp;
118 }
119
120 /**
121 * Loads a set of segments into this aggregation, one per measure,
122 * each constrained by the same set of column values, and each pinned
123 * once.
124 *
125 * <p>A Column and its constraints are accessed at the same level in their
126 * respective arrays.
127 *
128 * <p>For example,
129 * <blockquote><pre>
130 * measures = {unit_sales, store_sales},
131 * state = {CA, OR},
132 * gender = unconstrained</pre></blockquote>
133 */
134 public void load(
135 RolapStar.Column[] columns,
136 RolapStar.Measure[] measures,
137 StarColumnPredicate[] predicates,
138 RolapAggregationManager.PinSet pinnedSegments,
139 GroupingSetsCollector groupingSetsCollector)
140 {
141 // all constrained columns
142 if (this.columns == null) {
143 this.columns = columns;
144 }
145
146 BitKey measureBitKey = getConstrainedColumnsBitKey().emptyCopy();
147 int axisCount = columns.length;
148 Util.assertTrue(predicates.length == axisCount);
149
150 // This array of Aggregation.Axis is shared by all Segments for
151 // this set of measures and constraints
152 Aggregation.Axis[] axes = new Aggregation.Axis[axisCount];
153 for (int i = 0; i < axisCount; i++) {
154 axes[i] = new Aggregation.Axis(predicates[i]);
155 }
156 Segment[] segments =
157 addSegmentsToAggregation(
158 measures, measureBitKey, axes, pinnedSegments);
159 // The constrained columns are simply the level and foreign columns
160 BitKey levelBitKey = getConstrainedColumnsBitKey();
161 GroupingSet groupingSet =
162 new GroupingSet(
163 segments, levelBitKey, measureBitKey, axes, columns);
164 final List<StarPredicate> compoundPredicateList =
165 aggregationKey.getCompoundPredicateList();
166 if (groupingSetsCollector.useGroupingSets()) {
167 groupingSetsCollector.add(groupingSet);
168 // Segments are loaded using group by grouping sets
169 // by CompositeBatch.loadAggregation
170 } else {
171 new SegmentLoader().load(
172 Collections.singletonList(groupingSet),
173 pinnedSegments,
174 compoundPredicateList);
175 }
176 }
177
178 private Segment[] addSegmentsToAggregation(
179 RolapStar.Measure[] measures,
180 BitKey measureBitKey,
181 Axis[] axes,
182 RolapAggregationManager.PinSet pinnedSegments)
183 {
184 Segment[] segments = new Segment[measures.length];
185 for (int i = 0; i < measures.length; i++) {
186 RolapStar.Measure measure = measures[i];
187 measureBitKey.set(measure.getBitPosition());
188 Segment segment =
189 new Segment(
190 this, measure, axes,
191 Collections.<Segment.Region>emptyList());
192 segments[i] = segment;
193 SoftReference<Segment> ref = new SoftReference<Segment>(segment);
194 segmentRefs.add(ref);
195 ((AggregationManager.PinSetImpl) pinnedSegments).add(segment);
196 }
197 return segments;
198 }
199
200 /**
201 * Drops predicates, where the list of values is close to the values which
202 * would be returned anyway.
203 */
204 public StarColumnPredicate[] optimizePredicates(
205 RolapStar.Column[] columns,
206 StarColumnPredicate[] predicates) {
207 RolapStar star = getStar();
208 Util.assertTrue(predicates.length == columns.length);
209 StarColumnPredicate[] newPredicates = predicates.clone();
210 double[] bloats = new double[columns.length];
211
212 // We want to handle the special case "drilldown" which occurs pretty
213 // often. Here, the parent is here as a constraint with a single member
214 // and the list of children as well.
215 List<Member> potentialParents = new ArrayList<Member>();
216 for (final StarColumnPredicate predicate : predicates) {
217 Member m;
218 if (predicate instanceof MemberColumnPredicate) {
219 m = ((MemberColumnPredicate) predicate).getMember();
220 potentialParents.add(m);
221 }
222 }
223
224 for (int i = 0; i < newPredicates.length; i++) {
225 // A set of constraints with only one entry will not be optimized away
226 if (!(newPredicates[i] instanceof ListColumnPredicate)) {
227 bloats[i] = 0.0;
228 continue;
229 }
230
231 final ListColumnPredicate newPredicate =
232 (ListColumnPredicate) newPredicates[i];
233 final List<StarColumnPredicate> predicateList =
234 newPredicate.getPredicates();
235 final int valueCount = predicateList.size();
236 if (valueCount < 2) {
237 bloats[i] = 0.0;
238 continue;
239 }
240
241 if (valueCount > maxConstraints) {
242 // Some databases can handle only a limited number of elements
243 // in 'WHERE IN (...)'. This set is greater than this database
244 // can handle, so we drop this constraint. Hopefully there are
245 // other constraints that will limit the result.
246 bloats[i] = 1.0; // will be optimized away
247 continue;
248 }
249
250 // more than one - check for children of same parent
251 double constraintLength = (double) valueCount;
252 Member parent = null;
253 Level level = null;
254 for (int j = 0; j < valueCount; j++) {
255 Object value = predicateList.get(j);
256 if (value instanceof MemberColumnPredicate) {
257 MemberColumnPredicate memberColumnPredicate =
258 (MemberColumnPredicate) value;
259 Member m = memberColumnPredicate.getMember();
260 if (j == 0) {
261 parent = m.getParentMember();
262 level = m.getLevel();
263 } else {
264 if (parent != null
265 && !parent.equals(m.getParentMember())) {
266 parent = null; // no common parent
267 }
268 if (level != null
269 && !level.equals(m.getLevel())) {
270 // should never occur, constraints are of same level
271 level = null;
272 }
273 }
274 } else {
275 // Value constraint with no associated member.
276 // Compute bloat by #constraints / column cardinality.
277 parent = null;
278 level = null;
279 bloats[i] = constraintLength / columns[i].getCardinality();
280 break;
281 }
282 }
283 boolean done = false;
284 if (parent != null) {
285 // common parent exists
286 if (parent.isAll() || potentialParents.contains(parent)) {
287 // common parent is there as constraint
288 // if the children are complete, this constraint set is
289 // unneccessary try to get the children directly from
290 // cache for the drilldown case, the children will be
291 // in the cache
292 // - if not, forget this optimization.
293 SchemaReader scr = star.getSchema().getSchemaReader();
294 int childCount = scr.getChildrenCountFromCache(parent);
295 if (childCount == -1) {
296 // nothing gotten from cache
297 if (!parent.isAll()) {
298 // parent is in constraints
299 // no information about children cardinality
300 // constraints must not be optimized away
301 bloats[i] = 0.0;
302 done = true;
303 }
304 } else {
305 bloats[i] = constraintLength / childCount;
306 done = true;
307 }
308 }
309 }
310
311 if (!done && level != null) {
312 // if the level members are cached, we do not need "count *"
313 SchemaReader scr = star.getSchema().getSchemaReader();
314 int memberCount = scr.getLevelCardinality(level, true, false);
315 if (memberCount > 0) {
316 bloats[i] = constraintLength / memberCount;
317 done = true;
318 }
319 }
320
321 if (!done) {
322 bloats[i] = constraintLength / columns[i].getCardinality();
323 }
324 }
325
326 // build a list of constraints sorted by 'bloat factor'
327 ConstraintComparator comparator = new ConstraintComparator(bloats);
328 Integer[] indexes = new Integer[columns.length];
329 for (int i = 0; i < columns.length; i++) {
330 indexes[i] = i;
331 }
332
333 // sort indexes by bloat descending
334 Arrays.sort(indexes, comparator);
335
336 // Eliminate constraints one by one, until the constrained cell count
337 // became half of the unconstrained cell count. We can not have an
338 // absolute value here, because its
339 // very different if we fetch data for 2 years or 10 years (5 times
340 // more means 5 times slower). So a relative comparison is ok here
341 // but not an absolute one.
342
343 double abloat = 1.0;
344 final double aBloatLimit = .5;
345
346 for (Integer j : indexes) {
347 abloat = abloat * bloats[j];
348 if (abloat <= aBloatLimit) {
349 break;
350 }
351 // eliminate this constraint
352 if (MondrianProperties.instance().OptimizePredicates.get()
353 || bloats[j] == 1) {
354 newPredicates[j] = new LiteralStarPredicate(columns[j], true);
355 }
356 }
357 return newPredicates;
358 }
359
360 public String toString() {
361 java.io.StringWriter sw = new java.io.StringWriter(256);
362 PrintWriter pw = new PrintWriter(sw);
363 print(pw);
364 pw.flush();
365 return sw.toString();
366 }
367
368 /**
369 * Prints the state of this <code>Aggregation</code> to a writer.
370 *
371 * @param pw Writer
372 */
373 public void print(PrintWriter pw) {
374 List<Segment> segmentList = new ArrayList<Segment>();
375 for (SoftReference<Segment> ref : segmentRefs) {
376 Segment segment = ref.get();
377 if (segment == null) {
378 continue;
379 }
380 segmentList.add(segment);
381 }
382
383 // Sort segments, to make order deterministic.
384 Collections.sort(
385 segmentList,
386 new Comparator<Segment>() {
387 public int compare(Segment o1, Segment o2) {
388 return o1.id - o2.id;
389 }
390 });
391
392 for (Segment segment : segmentList) {
393 segment.print(pw);
394 }
395 }
396
397 public void flush(
398 CacheControl cacheControl,
399 RolapCacheRegion cacheRegion) {
400 // Compare the bitmaps.
401 //
402 // Case 1: aggregate bitmap contains request bitmap.
403 // E.g. agg = (year={1997, 1998}, quarter=*, nation=USA),
404 // request = (year=1997, nation={USA, Canada}).
405 // Assuming descendants (which we do, for now) flush the segment
406 // based on the {Year, Nation} values:
407 // flush = (year=1997, quarter=*, nation=USA)
408 //
409 // Case 2: aggregate bitmap is strict subset of request bitmap
410 // E.g. agg = (year={1997, 1998}, nation=*)
411 // request = (year={1997}, nation=*, gender="F")
412 // This segment isn't constrained on gender, therefore all cells could
413 // contain gender="F" values:
414 // flush = (year=1997, nation=*)
415 //
416 // Case 3: no overlap
417 // E.g. agg = (product, gender),
418 // request = (year=1997)
419 // This segment isn't constrained on year, therefore all cells could
420 // contain 1997 values. Flush the whole segment.
421 //
422 // The rule is:
423 // - Column in flush request and in segment. Apply constraints.
424 // - Column in flush request, not in segment. Ignore it.
425 // - Column not in flush request, in segment. Ignore it.
426 final boolean bitmapsIntersect =
427 cacheRegion.getConstrainedColumnsBitKey().intersects(
428 getConstrainedColumnsBitKey());
429
430 // New list of segments - will replace segmentRefs when we're done.
431 List<SoftReference<Segment>> newSegmentRefs =
432 new ArrayList<SoftReference<Segment>>();
433 segmentLoop:
434 for (SoftReference<Segment> segmentRef : segmentRefs) {
435 Segment segment = segmentRef.get();
436 if (segment == null) {
437 // Segment has been garbage collected. Flush it.
438 cacheControl.trace("discarding garbage collected segment");
439 continue;
440 }
441 if (!bitmapsIntersect) {
442 // No intersection between the columns constraining the flush
443 // and the columns defining the segment. Therefore, the segment
444 // is definitely affected. Flush it.
445 cacheControl.trace(
446 "discard segment - it has no columns in common: " +
447 segment);
448 continue;
449 }
450
451 // For each axis, indicates which values will be retained when
452 // constraints have been applied.
453 BitSet[] axisKeepBitSets = new BitSet[columns.length];
454 for (int i = 0; i < columns.length; i++) {
455 final Axis axis = segment.axes[i];
456 int keyCount = axis.getKeys().length;
457 final BitSet axisKeepBitSet
458 = axisKeepBitSets[i]
459 = new BitSet(keyCount);
460 final StarColumnPredicate predicate = axis.predicate;
461 assert predicate != null;
462
463 RolapStar.Column column = columns[i];
464 if (!cacheRegion.getConstrainedColumnsBitKey().get(
465 column.getBitPosition())) {
466 axisKeepBitSet.set(0, keyCount);
467 continue;
468 }
469 StarColumnPredicate flushPredicate =
470 cacheRegion.getPredicate(column.getBitPosition());
471
472 // If the flush request is not constrained on this column, move
473 // on to the next column.
474 if (flushPredicate == null) {
475 axisKeepBitSet.set(0, keyCount);
476 continue;
477 }
478
479 // If the segment is constrained on this column,
480 // and the flush request is constrained on this column,
481 // and the constraints do not intersect,
482 // then this flush request does not affect this segment.
483 // Keep it.
484 if (!flushPredicate.mightIntersect(predicate)) {
485 newSegmentRefs.add(segmentRef);
486 continue segmentLoop;
487 }
488
489 // The flush constraints overlap. We need to create a new
490 // constraint which captures what is actually in this segment.
491 //
492 // After the flush, values explicitly flushed must be outside
493 // the constraints of the axis. In particular, if the axis is
494 // initially unconstrained, contains the values {X, Y, Z}, and
495 // value Z is flushed, the new constraint of the axis will be
496 // {X, Y}. This will force the reader to look to another segment
497 // for the Z value, rather than assuming that it does not exist.
498 //
499 // Example #1. Column constraint is {A, B, C},
500 // actual values are {A, B},
501 // flush is {A, D}. New constraint could be
502 // either {B, C} (constraint minus flush)
503 // or {B} (actual minus flush).
504 //
505 // Example #2. Column constraint is * (unconstrained),
506 // actual values are {A, B},
507 // flush is {A, D}. New constraint must be
508 // {B} (actual minus flush) because mondrian cannot model
509 // negative constraints on segments.
510 final Object[] axisKeys = axis.getKeys();
511 for (int k = 0; k < axisKeys.length; k++) {
512 Object key = axisKeys[k];
513 if (!flushPredicate.evaluate(key)) {
514 axisKeepBitSet.set(k);
515 }
516 }
517 }
518
519 // Now go through the multi-column constraints, and eliminate any
520 // values which are always blocked by a given predicate.
521 for (StarPredicate predicate : cacheRegion.getPredicates()) {
522 ValuePruner pruner =
523 new ValuePruner(
524 predicate,
525 segment.axes,
526 segment.getData());
527 pruner.go(axisKeepBitSets);
528 }
529
530 // Figure out which of the axes retains most of its values.
531 float bestRetention = 0f;
532 int bestColumn = -1;
533 for (int i = 0; i < columns.length; i++) {
534 // What proportion of the values on this axis survived the flush
535 // constraint? 1.0 means they all survived. This means that none
536 // of the cells in the segment will be discarded.
537 // But we still need to tighten the constraints on the
538 // segment, in case new axis values have appeared.
539 RolapStar.Column column = columns[i];
540 final int bitPosition = column.getBitPosition();
541 if (!cacheRegion.getConstrainedColumnsBitKey().get(bitPosition)) {
542 continue;
543 }
544
545 final BitSet axisBitSet = axisKeepBitSets[i];
546 final Axis axis = segment.axes[i];
547 final Object[] axisKeys = axis.getKeys();
548
549 if (axisBitSet.cardinality() == 0) {
550 // If one axis is empty, the entire segment is empty.
551 // Discard it.
552 continue segmentLoop;
553 }
554
555 float retention =
556 (float) axisBitSet.cardinality() /
557 (float) axisKeys.length;
558
559 if (bestColumn == -1 || retention > bestRetention) {
560 // If there are multiple partially-satisfied
561 // constraints ANDed together, keep the constraint
562 // which is least selective.
563 bestRetention = retention;
564 bestColumn = i;
565 }
566 }
567
568 // Come up with an estimate of how many cells this region contains.
569 List<StarColumnPredicate> regionPredicates =
570 new ArrayList<StarColumnPredicate>();
571 int cellCount = 1;
572 for (int i = 0; i < this.columns.length; i++) {
573 RolapStar.Column column = this.columns[i];
574 Axis axis = segment.axes[i];
575 final int pos = column.getBitPosition();
576 StarColumnPredicate flushPredicate =
577 cacheRegion.getPredicate(pos);
578 int keysMatched;
579 if (flushPredicate == null) {
580 flushPredicate = LiteralStarPredicate.TRUE;
581 keysMatched = axis.getKeys().length;
582 } else {
583 keysMatched = axis.getMatchCount(flushPredicate);
584 }
585 cellCount *= keysMatched;
586 regionPredicates.add(flushPredicate);
587 }
588
589 // We don't know the selectivity of multi-column predicates
590 // (typically member predicates such as '>= [Time].[1997].[Q2]') so
591 // we guess 50% selectivity.
592 for (StarPredicate p : cacheRegion.getPredicates()) {
593 cellCount *= .5;
594 }
595 Segment.Region region =
596 new Segment.Region(
597 regionPredicates,
598 new ArrayList<StarPredicate>(cacheRegion.getPredicates()),
599 cellCount);
600
601 // How many cells left after we exclude this region? If there are
602 // none left, throw away the segment. It doesn't matter if we
603 // over-estimate how many cells are in the region, and therefore
604 // throw away a segment which has a few cells left.
605 int remainingCellCount = segment.getCellCount();
606 if (remainingCellCount - cellCount <= 0) {
607 continue;
608 }
609
610 // Add the flush region to the list of excluded regions.
611 //
612 // TODO: If the region has been fully accounted for in changes to
613 // the predicates on the axes, then don't add it to the exclusion
614 // list.
615 final List<Segment.Region> excludedRegions =
616 new ArrayList<Segment.Region>(segment.getExcludedRegions());
617 if (!excludedRegions.contains(region)) {
618 excludedRegions.add(region);
619 }
620
621 StarColumnPredicate bestColumnPredicate;
622 if (bestColumn >= 0) {
623 // Instantiate the axis with the best retention.
624 RolapStar.Column column = columns[bestColumn];
625 final int bitPosition = column.getBitPosition();
626 StarColumnPredicate flushPredicate =
627 cacheRegion.getPredicate(bitPosition);
628 final Axis axis = segment.axes[bestColumn];
629 bestColumnPredicate = axis.predicate;
630 if (flushPredicate != null) {
631 bestColumnPredicate =
632 bestColumnPredicate.minus(flushPredicate);
633 }
634 } else {
635 bestColumnPredicate = null;
636 }
637
638 final Segment newSegment =
639 segment.createSubSegment(
640 axisKeepBitSets,
641 bestColumn,
642 bestColumnPredicate,
643 excludedRegions);
644
645 newSegmentRefs.add(new SoftReference<Segment>(newSegment));
646 }
647
648 // Replace list of segments.
649 // FIXME: Synchronize.
650 // TODO: Replace segmentRefs, don't copy.
651 segmentRefs.clear();
652 segmentRefs.addAll(newSegmentRefs);
653 }
654
655 /**
656 * Retrieves the value identified by <code>keys</code>.
657 * If the requested cell is found in the loading segment, current Thread
658 * will be blocked until segment is loaded.
659 *
660 * <p>If <code>pinSet</code> is not null, pins the
661 * segment which holds it. <code>pinSet</code> ensures that a segment is
662 * only pinned once.
663 *
664 * <p>Returns <code>null</code> if no segment contains the cell.
665 *
666 * <p>Returns {@link Util#nullValue} if a segment contains the cell and the
667 * cell's value is null.
668 */
669 public Object getCellValue(
670 RolapStar.Measure measure,
671 Object[] keys,
672 RolapAggregationManager.PinSet pinSet) {
673 for (SoftReference<Segment> segmentref : segmentRefs) {
674 Segment segment = segmentref.get();
675 if (segment == null) {
676 segmentRefs.remove(segmentref);
677 continue; // it's being garbage-collected
678 }
679 if (segment.measure != measure) {
680 continue;
681 }
682 if (segment.isReady()) {
683 Object o = segment.getCellValue(keys);
684 if (o != null) {
685 if (pinSet != null) {
686 ((AggregationManager.PinSetImpl) pinSet).add(segment);
687 }
688 return o;
689 }
690 } else {
691 // avoid to call wouldContain - its slow
692 if (pinSet != null
693 && !((AggregationManager.PinSetImpl) pinSet).contains(segment)
694 && segment.wouldContain(keys)) {
695 segment.waitUntilLoaded(); //Waiting on Segment state
696 if (segment.isReady()) {
697 ((AggregationManager.PinSetImpl) pinSet).add(segment);
698 return segment.getCellValue(keys);
699 }
700 }
701 }
702 }
703 // No segment contains the requested cell.
704 return null;
705 }
706
707 /**
708 * This is called during Sql generation.
709 */
710 public RolapStar.Column[] getColumns() {
711 return columns;
712 }
713
714 /**
715 * This is called during Sql generation.
716 */
717 public RolapStar getStar() {
718 return aggregationKey.getStar();
719 }
720
721 /**
722 * Returns the BitKey for ALL columns (Measures and Levels) involved in the
723 * query.
724 */
725 public BitKey getConstrainedColumnsBitKey() {
726 return aggregationKey.getConstrainedColumnsBitKey();
727 }
728
729 // -- classes -------------------------------------------------------------
730
731 static class Axis {
732
733 /**
734 * Constraint on the keys in this Axis. Never null.
735 */
736 private final StarColumnPredicate predicate;
737
738 /**
739 * Map holding the position of each key value.
740 *
741 * <p>TODO: Hold keys in a sorted array, then deduce ordinal by doing
742 * binary search.
743 */
744 private final Map<Comparable<?>, Integer> mapKeyToOffset =
745 new HashMap<Comparable<?>, Integer>();
746
747 /**
748 * Actual key values retrieved.
749 */
750 private Comparable<?>[] keys;
751 private boolean hasNull;
752
753 /**
754 * Creates an empty Axis.
755 *
756 * @param predicate Predicate defining which keys should appear on
757 * axis. (If a key passes the predicate but is not in the list, every
758 * cell with that key is assumed to have a null value.)
759 */
760 Axis(StarColumnPredicate predicate) {
761 this.predicate = predicate;
762 assert predicate != null;
763 }
764
765 /**
766 * Creates an axis populated with a set of keys.
767 *
768 * @param predicate Predicate defining which keys should appear on
769 * axis. (If a key passes the predicate but is not in the list, every
770 * cell with that key is assumed to have a null value.)
771 * @param keys Keys
772 */
773 Axis(StarColumnPredicate predicate, Comparable<?>[] keys) {
774 this(predicate);
775 this.keys = keys;
776 for (int i = 0; i < keys.length; i++) {
777 Comparable<?> key = keys[i];
778 mapKeyToOffset.put(key, i);
779 assert i == 0 ||
780 ((Comparable) keys[i - 1]).compareTo(keys[i]) < 0;
781 }
782 }
783
784 StarColumnPredicate getPredicate() {
785 return predicate;
786 }
787
788 Comparable<?>[] getKeys() {
789 return this.keys;
790 }
791
792 /**
793 * Loads keys into the axis.
794 *
795 * @param valueSet Set of distinct key values, sorted
796 * @param hasNull Whether the axis contains the null value, in addition
797 * to the values in <code>valueSet</code>
798 * @return Number of keys on axis
799 */
800 int loadKeys(SortedSet<Comparable<?>> valueSet, boolean hasNull) {
801 this.hasNull = hasNull;
802 int size = valueSet.size();
803
804 if (hasNull) {
805 size++;
806 }
807 keys = new Comparable<?>[size];
808
809 valueSet.toArray(keys);
810 if (hasNull) {
811 keys[size - 1] = RolapUtil.sqlNullValue;
812 }
813
814 for (int i = 0; i < size; i++) {
815 mapKeyToOffset.put(keys[i], i);
816 }
817
818 return size;
819 }
820
821 static final Comparable wrap(Object o) {
822 if (Util.PreJdk15 && o instanceof Boolean) {
823 return Integer.valueOf((Boolean) o ? 1 : 0);
824 } else {
825 return (Comparable) o;
826 }
827 }
828
829 final int getOffset(Object o) {
830 return getOffset(wrap(o));
831 }
832
833 final int getOffset(Comparable key) {
834 Integer ordinal = mapKeyToOffset.get(key);
835 if (ordinal == null) {
836 return -1;
837 }
838 return ordinal.intValue();
839 }
840
841 /**
842 * Returns whether this axis contains a given key, or would contain it
843 * if it existed.
844 *
845 * <p>For example, if this axis is unconstrained, then this method
846 * returns <code>true</code> for any value.
847 *
848 * @param key Key
849 * @return Whether this axis would contain <code>key</code>
850 */
851 boolean contains(Object key) {
852 return predicate.evaluate(key);
853 }
854
855 /**
856 * Returns how many of this Axis' keys match a given constraint.
857 *
858 * @param predicate Predicate
859 * @return How many keys match constraint
860 */
861 public int getMatchCount(StarColumnPredicate predicate) {
862 int matchCount = 0;
863 for (Object key : keys) {
864 if (predicate.evaluate(key)) {
865 ++matchCount;
866 }
867 }
868 return matchCount;
869 }
870 }
871
872 /**
873 * Helper class to figure out which axis values evaluate to true at least
874 * once by a given predicate.
875 *
876 * <p>Consider, for example, the flush predicate<blockquote><code>
877 *
878 * member between [Time].[1997].[Q3] and [Time].[1999].[Q1]
879 *
880 * </code></blockquote>applied to the segment <blockquote><code>
881 *
882 * year in (1996, 1997, 1998, 1999)<br/>
883 * quarter in (Q1, Q2, Q3, Q4)
884 *
885 * </code></blockquote> The predicate evaluates to true for the pairs
886 * <blockquote><code>
887 *
888 * {(1997, Q3), (1997, Q4),
889 * (1998, Q1), (1998, Q2), (1998, Q3), (1998, Q4), (1999, Q1)}
890 *
891 * </code></blockquote> and therefore we wish to eliminate these pairs from
892 * the segment. But we can eliminate a value only if <em>all</em> of its
893 * values are eliminated.
894 *
895 * <p>In this case, year=1998 is the only value which can be eliminated from
896 * the segment.
897 */
898 private static class ValuePruner {
899 /**
900 * Multi-column predicate. If the predicate evaluates to true, a cell
901 * will be removed from the segment. But we can only eliminate a value
902 * if all of its cells are eliminated.
903 */
904 private final StarPredicate flushPredicate;
905 /**
906 * Number of columns predicate depends on.
907 */
908 private final int arity;
909 /**
910 * For each column, the segment axis which the column corresponds to, or
911 * null.
912 */
913 private final Axis[] axes;
914 /**
915 * For each column, a bitmap of values for which the predicate is
916 * sometimes false. These values cannot be eliminated from the axis.
917 */
918 private final BitSet[] keepBitSets;
919 /**
920 * For each segment axis, the predicate column which depends on the
921 * axis, or -1.
922 */
923 private final int[] axisInverseOrdinals;
924 /**
925 * Workspace which contains the current key value for each column.
926 */
927 private final Object[] values;
928 /**
929 * View onto {@link #values} as a list.
930 */
931 private final List<Object> valueList;
932 /**
933 * Workspace which contains the ordinal of the current value of each
934 * column on its axis.
935 */
936 private final int[] ordinals;
937
938 private final SegmentDataset data;
939
940 private final CellKey cellKey;
941
942 /**
943 * Creates a ValuePruner.
944 *
945 * @param flushPredicate Multi-column predicate to test
946 * @param segmentAxes Axes of the segment. (The columns that the
947 * predicate may not be present, or may be in a different order.)
948 * @param data Segment dataset, which allows pruner to determine whether
949 * a particular cell is currently empty
950 */
951 ValuePruner(
952 StarPredicate flushPredicate,
953 Axis[] segmentAxes,
954 SegmentDataset data) {
955 this.flushPredicate = flushPredicate;
956 this.arity = flushPredicate.getConstrainedColumnList().size();
957 this.axes = new Axis[arity];
958 this.keepBitSets = new BitSet[arity];
959 this.axisInverseOrdinals = new int[segmentAxes.length];
960 Arrays.fill(axisInverseOrdinals, -1);
961 this.values = new Object[arity];
962 this.valueList = Arrays.asList(values);
963 this.ordinals = new int[arity];
964 assert data != null;
965 this.data = data;
966 this.cellKey = CellKey.Generator.newCellKey(segmentAxes.length);
967
968 // Pair up constraint columns with axes. If one of the constraint's
969 // columns is not in this segment, it gets the null axis. The
970 // constraint will have to evaluate to true for all possible values
971 // of that column.
972 for (int i = 0; i < arity; i++) {
973 RolapStar.Column column =
974 flushPredicate.getConstrainedColumnList().get(i);
975 int axisOrdinal =
976 findAxis(segmentAxes, column.getBitPosition());
977 if (axisOrdinal < 0) {
978 this.axes[i] = null;
979 values[i] = StarPredicate.WILDCARD;
980 keepBitSets[i] = new BitSet(1); // dummy
981 } else {
982 axes[i] = segmentAxes[axisOrdinal];
983 axisInverseOrdinals[axisOrdinal] = i;
984 final int keyCount = axes[i].getKeys().length;
985 keepBitSets[i] = new BitSet(keyCount);
986 }
987 }
988 }
989
990 private int findAxis(Axis[] axes, int bitPosition) {
991 for (int i = 0; i < axes.length; i++) {
992 Axis axis = axes[i];
993 if (axis.getPredicate().getConstrainedColumn().getBitPosition()
994 == bitPosition) {
995 return i;
996 }
997 }
998 return -1;
999 }
1000
1001 /**
1002 * Applies this ValuePruner's predicate and sets bits in axisBitSets
1003 * to indicate extra values which can be removed.
1004 *
1005 * @param axisKeepBitSets Array containing, for each axis, a bitset
1006 * of values to keep (not flush)
1007 */
1008 void go(BitSet[] axisKeepBitSets) {
1009 evaluatePredicate(0);
1010
1011 // Clear bits in the axis bit sets (indicating that a value is never
1012 // used) if this predicate evaluates to true for every combination
1013 // of values which this axis value appears in.
1014 for (int i = 0; i < axisKeepBitSets.length; i++) {
1015 if (axisInverseOrdinals[i] < 0) {
1016 continue;
1017 }
1018 BitSet axisKeepBitSet = axisKeepBitSets[axisInverseOrdinals[i]];
1019 final BitSet keepBitSet = keepBitSets[i];
1020 axisKeepBitSet.and(keepBitSet);
1021 }
1022 }
1023
1024 /**
1025 * Evaluates the predicate for axes <code>i</code> and higher, and marks
1026 * {@link #keepBitSets} if the predicate ever evaluates to false.
1027 * The result is that discardBitSets[i] will be false for column #i if
1028 * the predicate evaluates to true for all cells in the segment which
1029 * have that column value.
1030 *
1031 * @param axisOrdinal Axis ordinal
1032 */
1033 private void evaluatePredicate(int axisOrdinal) {
1034 if (axisOrdinal == arity) {
1035 // If the flush predicate evaluates to false for this cell,
1036 // and this cell currently has some data (*),
1037 // then none of the values which are the coordinates of this
1038 // cell can be discarded.
1039 //
1040 // * Important when there is sparsity. Consider the cell
1041 // {year=1997, quarter=Q1, month=12}. This cell would never have
1042 // data, so there's no point keeping it.
1043 if (!flushPredicate.evaluate(valueList)) {
1044 if (data.get(cellKey) != null) {
1045 for (int k = 0; k < arity; k++) {
1046 keepBitSets[k].set(ordinals[k]);
1047 }
1048 }
1049 }
1050 } else {
1051 final Axis axis = axes[axisOrdinal];
1052 if (axis == null) {
1053 evaluatePredicate(axisOrdinal + 1);
1054 } else {
1055 for (int keyOrdinal = 0; keyOrdinal < axis.keys.length; keyOrdinal++) {
1056 Object key = axis.keys[keyOrdinal];
1057 values[axisOrdinal] = key;
1058 ordinals[axisOrdinal] = keyOrdinal;
1059 cellKey.setAxis(
1060 axisInverseOrdinals[axisOrdinal],
1061 keyOrdinal);
1062 evaluatePredicate(axisOrdinal + 1);
1063 }
1064 }
1065 }
1066 }
1067 }
1068
1069 private static class ConstraintComparator implements Comparator<Integer> {
1070 private final double[] bloats;
1071
1072 ConstraintComparator(double[] bloats) {
1073 this.bloats = bloats;
1074 }
1075
1076 // implement Comparator
1077 // order by bloat descending
1078 public int compare(Integer o0, Integer o1) {
1079 double bloat0 = bloats[o0];
1080 double bloat1 = bloats[o1];
1081 return (bloat0 == bloat1)
1082 ? 0
1083 : (bloat0 < bloat1)
1084 ? 1
1085 : -1;
1086 }
1087 }
1088
1089
1090 }
1091
1092 // End Aggregation.java