001 /*
002 // $Id: //open/mondrian-release/3.2/src/main/mondrian/rolap/agg/Segment.java#3 $
003 // This software is subject to the terms of the Eclipse Public License v1.0
004 // Agreement, available at the following URL:
005 // http://www.eclipse.org/legal/epl-v10.html.
006 // Copyright (C) 2002-2002 Kana Software, Inc.
007 // Copyright (C) 2002-2010 Julian Hyde and others
008 // All Rights Reserved.
009 // You must accept the terms of that agreement to use this software.
010 //
011 // jhyde, 21 March, 2002
012 */
013 package mondrian.rolap.agg;
014
015 import mondrian.olap.*;
016 import mondrian.rolap.*;
017
018 import java.util.*;
019 import java.util.concurrent.CountDownLatch;
020 import java.util.concurrent.locks.ReentrantReadWriteLock;
021 import java.io.PrintWriter;
022
023 import org.apache.log4j.Logger;
024
025 /**
026 * A <code>Segment</code> is a collection of cell values parameterized by
027 * a measure, and a set of (column, value) pairs. An example of a segment is</p>
028 *
029 * <blockquote>
030 * <p>(Unit sales, Gender = 'F', State in {'CA','OR'}, Marital Status = <i>
031 * anything</i>)</p>
032 * </blockquote>
033 *
034 * <p>All segments over the same set of columns belong to an Aggregation, in
035 * this case:</p>
036 *
037 * <blockquote>
038 * <p>('Sales' Star, Gender, State, Marital Status)</p>
039 * </blockquote>
040 *
041 * <p>Note that different measures (in the same Star) occupy the same
042 * Aggregation. Aggregations belong to the AggregationManager, a singleton.</p>
043 *
044 * <p>Segments are pinned during the evaluation of a single MDX query. The query
045 * evaluates the expressions twice. The first pass, it finds which cell values
046 * it needs, pins the segments containing the ones which are already present
047 * (one pin-count for each cell value used), and builds a {@link CellRequest
048 * cell request} for those which are not present. It executes the cell request
049 * to bring the required cell values into the cache, again, pinned. Then it
050 * evalutes the query a second time, knowing that all cell values are
051 * available. Finally, it releases the pins.</p>
052 *
053 * <p>A Segment may have a list of excluded {@link Region} objects. These are
054 * caused by cache flushing. Usually a segment is a hypercube: it is defined by
055 * a set of values on each of its axes. But after a cache flush request, a
056 * segment may have a rectangular 'hole', and therefore not be a hypercube
057 * anymore.
058 *
059 * <p>For example, the segment defined by {CA, OR, WA} * {F, M} is a
060 * 2-dimensional hyper-rectangle with 6 cells. After flushing {CA, OR, TX} *
061 * {F}, the result is 4 cells:
062 *
063 * <pre>
064 * F M
065 * CA out in
066 * OR out in
067 * WA in in
068 * </pre>
069 *
070 * defined by the original segment minus the region ({CA, OR} * {F}).
071 *
072 * @author jhyde
073 * @since 21 March, 2002
074 * @version $Id: //open/mondrian-release/3.2/src/main/mondrian/rolap/agg/Segment.java#3 $
075 */
076 class Segment {
077 private static int nextId = 0; // generator for "id"
078
079 final int id; // for debug
080 private String desc;
081 final Aggregation aggregation;
082 final RolapStar.Measure measure;
083
084 final Aggregation.Axis[] axes;
085
086 /**
087 * <p><code>data</code> holds a reference to the <code>SegmentDataset</code>
088 * that contains the underlying cell values.</p>
089 *
090 * <p>Since the <code>SegmentDataset</code> is loaded and assigned after
091 * <code>Segment</code> is constructed, threadsafe access to it is only
092 * guaranteed if the access is guarded.<p/>
093 *
094 * <p>Access which does not depend on <code>data</code> already having been
095 * loaded should be guarded by obtaining either a read or write lock on
096 * <code>stateLock</code>, as appropriate.</p>
097 *
098 * <p>Access that should not proceed until the <code>data</code> reference
099 * has been loaded should be guarded using the <code>dataGate</code> latch.
100 * This is typically accomplished by calling <code>waitUntilLoaded()</code>,
101 * which will block until the latch is released and throw an error if
102 * <code>data</code> failed to load.</p>
103 *
104 * <p>Once set, the value of <code>data</code> is presumed to be invariant
105 * and should never be reset, nor should the contents be modified. Thus,
106 * for a given thread, any read access to data which comes after
107 * <code>dataGate.await()</code> (or, by extension,
108 * <code>waitUntilLoaded</code> will be threadsafe.</p>
109 */
110 private SegmentDataset data;
111 private final CountDownLatch dataGate = new CountDownLatch(1);
112
113
114 /**
115 * <p><code>state</code> == state of the segment (loading, ready, etc).
116 * Since it correlates to the value of the <code>data</code> reference
117 * and may be accessed from multiple threads, access to it
118 * is guarded by stateLock.</p>
119 *
120 * <p>The initial value of state is Loading. It may then be set to
121 * either Ready or Failed. Ready and Failed are both terminal
122 * states; once set to either, state may not be reset.</p>
123 */
124 private State state = State.Loading;
125 private final ReentrantReadWriteLock stateLock =
126 new ReentrantReadWriteLock();
127
128 /**
129 * List of regions to ignore when reading this segment. This list is
130 * populated when a region is flushed. The cells for these regions may be
131 * physically in the segment, because trimming segments can be expensive,
132 * but should still be ignored.
133 */
134 private final List<Region> excludedRegions;
135
136 private static final Logger LOGGER = Logger.getLogger(Segment.class);
137
138 /**
139 * Creates a <code>Segment</code>; it's not loaded yet.
140 *
141 * @param aggregation The aggregation this <code>Segment</code> belongs to
142 * @param measure Measure whose values this Segment contains
143 * @param axes List of axes; each is a constraint plus a list of values
144 * @param excludedRegions List of regions which are not in this segment.
145 */
146 Segment(
147 Aggregation aggregation,
148 RolapStar.Measure measure,
149 Aggregation.Axis[] axes,
150 List<Region> excludedRegions)
151 {
152 this.id = nextId++;
153 this.aggregation = aggregation;
154 this.measure = measure;
155 this.axes = axes;
156 this.excludedRegions = excludedRegions;
157 for (Region region : excludedRegions) {
158 assert region.getPredicates().size() == axes.length;
159 }
160 }
161
162 /**
163 * Sets the data, and notifies any threads which are blocked in
164 * {@link #waitUntilLoaded}.
165 */
166 void setData(
167 SegmentDataset data,
168 RolapAggregationManager.PinSet pinnedSegments)
169 {
170 stateLock.writeLock().lock(); // need exclusive write access to state
171 try {
172 Util.assertTrue(this.data == null);
173 Util.assertTrue(this.state == State.Loading);
174
175 this.data = data;
176 this.state = State.Ready;
177 } finally {
178 stateLock.writeLock().unlock(); // always release state lock
179 }
180
181 dataGate.countDown(); // allow data reader threads to proceed
182 }
183
184 /**
185 * If this segment is still loading, signals that it failed to load, and
186 * notifies any threads which are blocked in {@link #waitUntilLoaded}.
187 */
188 void setFailIfStillLoading() {
189 stateLock.writeLock().lock(); // need exclusive write access to state
190 try {
191 switch (state) {
192 case Loading:
193 Util.assertTrue(this.data == null);
194 this.state = State.Failed;
195 break;
196 case Ready:
197 // The segment loaded just fine.
198 break;
199 default:
200 throw Util.badValue(state);
201 }
202 } finally {
203 stateLock.writeLock().unlock(); // always release state lock
204 if (this.state == State.Failed) {
205 dataGate.countDown(); // allow data reader threads to proceed
206 }
207 }
208 }
209
210 /**
211 * Compares internal <code>state</code> variable to a passed-in value
212 * in a threadsafe way using the <code>stateLock</code> read lock.
213 *
214 * @param value The State value to which <code>state</code> should be
215 * compared.
216 * @return True if states match, false otherwise
217 */
218 private boolean compareState(State value) {
219 boolean retval = false;
220 stateLock.readLock().lock();
221 try {
222 retval = (state == value);
223 } finally {
224 stateLock.readLock().unlock();
225 }
226 return (retval);
227 }
228
229 public boolean isReady() {
230 return (compareState(State.Ready));
231 }
232
233 boolean isFailed() {
234 return (compareState(State.Failed));
235 }
236
237 private void makeDescription(StringBuilder buf, boolean values) {
238 final String sep = Util.nl + " ";
239 buf.append(printSegmentHeaderInfo(sep));
240
241 RolapStar.Column[] columns = aggregation.getColumns();
242 for (int i = 0; i < columns.length; i++) {
243 buf.append(sep);
244 buf.append(columns[i].getExpression().getGenericExpression());
245 final Aggregation.Axis axis = axes[i];
246 axis.getPredicate().describe(buf);
247 if (values && isReady()) {
248 Object[] keys = axis.getKeys();
249 buf.append(", values={");
250 for (int j = 0; j < keys.length; j++) {
251 if (j > 0) {
252 buf.append(", ");
253 }
254 Object key = keys[j];
255 buf.append(key);
256 }
257 buf.append("}");
258 }
259 }
260 if (!excludedRegions.isEmpty()) {
261 buf.append(sep);
262 buf.append("excluded={");
263 int k = 0;
264 for (Region excludedRegion : excludedRegions) {
265 if (k++ > 0) {
266 buf.append(", ");
267 }
268 excludedRegion.describe(buf);
269 }
270 buf.append('}');
271 }
272 buf.append('}');
273 }
274
275 private String printSegmentHeaderInfo(String sep) {
276 StringBuilder buf = new StringBuilder();
277 buf.append("Segment #");
278 buf.append(id);
279 buf.append(" {");
280 buf.append(sep);
281 buf.append("measure=");
282 buf.append(
283 measure.getAggregator().getExpression(
284 measure.getExpression().getGenericExpression()));
285 return buf.toString();
286 }
287
288 public String toString() {
289 if (this.desc == null) {
290 StringBuilder buf = new StringBuilder(64);
291 makeDescription(buf, false);
292 this.desc = buf.toString();
293 }
294 return this.desc;
295 }
296
297 /**
298 * Retrieves the value at the location identified by
299 * <code>keys</code>.
300 *
301 * <p>Returns<ul>
302 *
303 * <li>{@link Util#nullValue} if the cell value
304 * is null (because no fact table rows met those criteria);</li>
305 *
306 * <li><code>null</code> if the value is not supposed to be in this segment
307 * (because one or more of the keys do not pass the axis criteria);</li>
308 *
309 * <li>the data value otherwise</li>
310 *
311 * </ul></p>
312 *
313 */
314 Object getCellValue(Object[] keys) {
315 assert keys.length == axes.length;
316 int missed = 0;
317 CellKey cellKey = CellKey.Generator.newCellKey(axes.length);
318 for (int i = 0; i < keys.length; i++) {
319 Object key = keys[i];
320 int offset = axes[i].getOffset(key);
321 if (offset < 0) {
322 if (axes[i].getPredicate().evaluate(key)) {
323 // see whether this segment should contain this value
324 missed++;
325 continue;
326 } else {
327 // this value should not appear in this segment; we
328 // should be looking in a different segment
329 return null;
330 }
331 }
332 cellKey.setAxis(i, offset);
333 }
334 if (isExcluded(keys)) {
335 // this value should not appear in this segment; we
336 // should be looking in a different segment
337 return null;
338 }
339 if (missed > 0) {
340 // the value should be in this segment, but isn't, because one
341 // or more of its keys does have any values
342 return Util.nullValue;
343 } else {
344 // waitUntilLoaded() ensures data exists, and makes
345 // following read threadsafe
346 waitUntilLoaded();
347 Object o = data.getObject(cellKey);
348 if (o == null) {
349 o = Util.nullValue;
350 }
351 return o;
352 }
353 }
354
355 /**
356 * Returns whether the given set of key values will be in this segment
357 * when it finishes loading.
358 */
359 boolean wouldContain(Object[] keys) {
360 Util.assertTrue(keys.length == axes.length);
361 for (int i = 0; i < keys.length; i++) {
362 Object key = keys[i];
363 if (!axes[i].getPredicate().evaluate(key)) {
364 return false;
365 }
366 }
367 return !isExcluded(keys);
368 }
369
370 /**
371 * Returns whether a cell value is excluded from this segment.
372 */
373 private boolean isExcluded(Object[] keys) {
374 // Performance critical: cannot use foreach
375 //noinspection ForLoopReplaceableByForEach
376 final int n = excludedRegions.size();
377 for (int i = 0; i < n; i++) {
378 Region excludedRegion = excludedRegions.get(i);
379 if (excludedRegion.wouldContain(keys)) {
380 return true;
381 }
382 }
383 return false;
384 }
385
386 /**
387 * Blocks until this segment has finished loading; if this segment has
388 * already loaded, returns immediately.
389 */
390 public void waitUntilLoaded() {
391 if (isLoading()) {
392 try {
393 LOGGER.debug("Waiting on " + printSegmentHeaderInfo(","));
394 dataGate.await();
395
396 stateLock.readLock().lock();
397 switch (state) {
398 case Ready:
399 return; // excellent!
400 case Failed:
401 throw Util.newError(
402 "Pending segment failed to load: "
403 + toString());
404 default:
405 throw Util.badValue(state);
406 }
407 } catch (InterruptedException e) {
408 //ignore
409 } finally {
410 stateLock.readLock().unlock();
411 }
412 }
413 }
414
415 private boolean isLoading() {
416 return (compareState(State.Loading));
417 }
418
419 /**
420 * Prints the state of this <code>Segment</code>, including constraints
421 * and values. Blocks the current thread until the segment is loaded.
422 *
423 * @param pw Writer
424 */
425 public void print(PrintWriter pw) {
426 waitUntilLoaded();
427 final StringBuilder buf = new StringBuilder();
428 makeDescription(buf, true);
429 pw.print(buf.toString());
430 pw.println();
431 }
432
433 public List<Region> getExcludedRegions() {
434 return excludedRegions;
435 }
436
437 /**
438 * Returns the number of cells in this Segment, deducting cells in
439 * excluded regions.
440 *
441 * <p>This method may return a value which is slightly too low, or
442 * occasionally even negative. This occurs when a Segment has more than one
443 * excluded region, and those regions overlap. Cells which are in both
444 * regions will be counted twice.
445 *
446 * @return Number of cells in this Segment
447 */
448 public int getCellCount() {
449 int cellCount = 1;
450 for (Aggregation.Axis axis : axes) {
451 cellCount *= axis.getKeys().length;
452 }
453 for (Region excludedRegion : excludedRegions) {
454 cellCount -= excludedRegion.cellCount;
455 }
456 return cellCount;
457 }
458
459 /**
460 * Creates a Segment which has the same dimensionality as this Segment and a
461 * subset of the values.
462 *
463 * <p>If <code>bestColumn</code> is not -1, the <code>bestColumn</code>th
464 * column's predicate should be replaced by <code>bestPredicate</code>.
465 *
466 * @param axisKeepBitSets For each axis, a bitmap of the axis values to
467 * keep; each axis must have at least one bit set
468 * @param bestColumn The column that retains most of its values
469 * @param bestPredicate
470 * @param excludedRegions List of regions to exclude from segment
471 * @return Segment containing a subset of the values
472 */
473 Segment createSubSegment(
474 BitSet[] axisKeepBitSets,
475 int bestColumn,
476 StarColumnPredicate bestPredicate,
477 List<Segment.Region> excludedRegions)
478 {
479 assert axisKeepBitSets.length == axes.length;
480
481 // Create a new segment with a subset of the values. If only one
482 // of the axes is restricted, restrict just that axis. If more than
483 // one of the axis is restricted, add a negation to the segment.
484 final Aggregation.Axis[] newAxes = axes.clone();
485
486 // For each axis, map from old position to new position.
487 final Map<Integer, Integer>[] axisPosMaps = new Map[axes.length];
488
489 int valueCount = 1;
490 for (int j = 0; j < axes.length; j++) {
491 Aggregation.Axis axis = axes[j];
492 StarColumnPredicate newPredicate = axis.getPredicate();
493 if (j == bestColumn) {
494 newPredicate = bestPredicate;
495 }
496 final Comparable<?>[] axisKeys = axis.getKeys();
497 BitSet keepBitSet = axisKeepBitSets[j];
498 int firstClearBit = keepBitSet.nextClearBit(0);
499 Comparable<?>[] newAxisKeys;
500 if (firstClearBit >= axisKeys.length) {
501 // Keep everything
502 newAxisKeys = axisKeys;
503 axisPosMaps[j] = null; // identity map
504 } else {
505 List<Object> newAxisKeyList = new ArrayList<Object>();
506 Map<Integer, Integer> map =
507 axisPosMaps[j] =
508 new HashMap<Integer, Integer>();
509 for (int bit = keepBitSet.nextSetBit(0);
510 bit >= 0;
511 bit = keepBitSet.nextSetBit(bit + 1))
512 {
513 map.put(bit, newAxisKeyList.size());
514 newAxisKeyList.add(axisKeys[bit]);
515 }
516 newAxisKeys =
517 newAxisKeyList.toArray(
518 new Comparable<?>[newAxisKeyList.size()]);
519 assert newAxisKeys.length > 0;
520 }
521 final Aggregation.Axis newAxis =
522 new Aggregation.Axis(newPredicate, newAxisKeys);
523 newAxes[j] = newAxis;
524 valueCount *= newAxisKeys.length;
525 }
526
527 // Create a new segment.
528 final Segment newSegment =
529 new Segment(aggregation, measure, newAxes, excludedRegions);
530
531 // isReady() is guarded and ensures visibility of data
532 Util.assertTrue(isReady());
533
534 // Create a dataset containing a subset of the current dataset.
535 // Keep the same representation as the current dataset.
536 // (We could be smarter - sometimes a subset of a sparse dataset will
537 // be dense and VERY occasionally a subset of a relatively dense dataset
538 // will be sparse.)
539 SegmentDataset newData =
540 createDataset(
541 data instanceof SparseSegmentDataset,
542 data.getType(),
543 valueCount);
544
545 // If the source is sparse, it is more efficient to iterate over the
546 // values we need. If it's dense, it doesn't matter too much.
547 int[] pos = new int[axes.length];
548 data:
549 for (Map.Entry<CellKey, Object> entry : data) {
550 CellKey key = entry.getKey();
551
552 // Map each of the source coordinates to the target coordinate.
553 // If any of the coordinates maps to null, it means that the
554 // cell falls outside the subset.
555 for (int i = 0; i < pos.length; i++) {
556 int ordinal = key.getAxis(i);
557
558 Map<Integer, Integer> axisPosMap = axisPosMaps[i];
559 if (axisPosMap == null) {
560 pos[i] = ordinal;
561 } else {
562 Integer integer = axisPosMap.get(ordinal);
563 if (integer == null) {
564 continue data;
565 }
566 pos[i] = integer;
567 }
568 }
569 newData.populateFrom(pos, data, key);
570 }
571 newSegment.setData(newData, null);
572
573 return newSegment;
574 }
575
576 SegmentDataset createDataset(
577 boolean sparse,
578 SqlStatement.Type type,
579 int size)
580 {
581 if (sparse) {
582 return new SparseSegmentDataset(this);
583 } else {
584 switch (type) {
585 case OBJECT:
586 return new DenseObjectSegmentDataset(this, size);
587 case INT:
588 return new DenseIntSegmentDataset(this, size);
589 case DOUBLE:
590 return new DenseDoubleSegmentDataset(this, size);
591 default:
592 throw Util.unexpected(type);
593 }
594 }
595 }
596
597 /**
598 * <p>Returns this Segment's dataset, or null if the data has not yet been
599 * loaded.</p>
600 *
601 * <p>WARNING: the returned SegmentDataset reference should not be modified;
602 * it is assumed to be invariant.</p>
603 *
604 * @return The <code>data</code> reference if it has been loaded,
605 * null otherwise.
606 */
607 SegmentDataset getData() {
608 //Review: letting a non-threadsafe object reference escape
609 //is inherently unsafe. Consider returning a copy.
610 if (isReady()) {
611 // isReady() is guarded, and ensures visibility of data
612 return data;
613 } else {
614 return null;
615 }
616 }
617
618 /**
619 * <code>State</code> enumerates the allowable values of a segment's
620 * state.
621 */
622 private static enum State {
623 Initial, Loading, Ready, Failed
624 }
625
626 /**
627 * Definition of a region of values which are not in a segment.
628 *
629 * <p>A region is defined by a set of constraints, one for each column
630 * in the segment. A constraint may be
631 * {@link mondrian.rolap.agg.LiteralStarPredicate}(true), meaning that
632 * the column is unconstrained.
633 *
634 * <p>For example,
635 * <pre>
636 * segment (State={CA, OR, WA}, Gender=*)
637 * actual values {1997, 1998} * {CA, OR, WA} * {M, F} = 12 cells
638 * excluded region (Year=*, State={CA, OR}, Gender={F})
639 * excluded values {1997, 1998} * {CA, OR} * {F} = 4 cells
640 *
641 * Values:
642 *
643 * F M
644 * CA out in
645 * OR out in
646 * WA in in
647 * </pre>
648 *
649 * <p>Note that the resulting segment is not a hypercube: it has a 'hole'.
650 * This is why regions are required.
651 */
652 static class Region {
653 private final StarColumnPredicate[] predicates;
654 private final StarPredicate[] multiColumnPredicates;
655 private final int cellCount;
656
657 Region(
658 List<StarColumnPredicate> predicateList,
659 List<StarPredicate> multiColumnPredicateList,
660 int cellCount)
661 {
662 this.predicates =
663 predicateList.toArray(
664 new StarColumnPredicate[predicateList.size()]);
665 this.multiColumnPredicates =
666 multiColumnPredicateList.toArray(
667 new StarPredicate[multiColumnPredicateList.size()]);
668 this.cellCount = cellCount;
669 }
670
671 public List<StarColumnPredicate> getPredicates() {
672 return Collections.unmodifiableList(Arrays.asList(predicates));
673 }
674
675 public List<StarPredicate> getMultiColumnPredicates() {
676 return Collections.unmodifiableList(
677 Arrays.asList(multiColumnPredicates));
678 }
679
680 public int getCellCount() {
681 return cellCount;
682 }
683
684 public boolean wouldContain(Object[] keys) {
685 assert keys.length == predicates.length;
686 for (int i = 0; i < keys.length; i++) {
687 final Object key = keys[i];
688 final StarColumnPredicate predicate = predicates[i];
689 if (!predicate.evaluate(key)) {
690 return false;
691 }
692 }
693 return true;
694 }
695
696 public boolean equals(Object obj) {
697 if (obj instanceof Region) {
698 Region that = (Region) obj;
699 return Arrays.equals(
700 this.predicates, that.predicates)
701 && Arrays.equals(
702 this.multiColumnPredicates,
703 that.multiColumnPredicates);
704 } else {
705 return false;
706 }
707 }
708
709 public int hashCode() {
710 return Arrays.hashCode(multiColumnPredicates) ^
711 Arrays.hashCode(predicates);
712 }
713
714 /**
715 * Describes this Segment.
716 * @param buf Buffer to write to.
717 */
718 public void describe(StringBuilder buf) {
719 int k = 0;
720 for (StarColumnPredicate predicate : predicates) {
721 if (predicate instanceof LiteralStarPredicate
722 && ((LiteralStarPredicate) predicate).getValue())
723 {
724 continue;
725 }
726 if (k++ > 0) {
727 buf.append(" AND ");
728 }
729 predicate.describe(buf);
730 }
731 for (StarPredicate predicate : multiColumnPredicates) {
732 if (predicate instanceof LiteralStarPredicate
733 && ((LiteralStarPredicate) predicate).getValue())
734 {
735 continue;
736 }
737 if (k++ > 0) {
738 buf.append(" AND ");
739 }
740 predicate.describe(buf);
741 }
742 }
743 }
744 }
745
746 // End Segment.java