Java > Open Source Codes > mondrian > rolap > agg > Aggregation


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags