001 /*
002 // $Id: //open/mondrian/src/main/mondrian/rolap/agg/Segment.java#51 $
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) 2002-2002 Kana Software, Inc.
007 // Copyright (C) 2002-2008 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.sql.*;
019 import java.util.*;
020 import java.io.PrintWriter;
021
022 import org.apache.log4j.Logger;
023
024 /**
025 * A <code>Segment</code> is a collection of cell values parameterized by
026 * a measure, and a set of (column, value) pairs. An example of a segment is</p>
027 *
028 * <blockquote>
029 * <p>(Unit sales, Gender = 'F', State in {'CA','OR'}, Marital Status = <i>
030 * anything</i>)</p>
031 * </blockquote>
032 *
033 * <p>All segments over the same set of columns belong to an Aggregation, in this
034 * case</p>
035 *
036 * <blockquote>
037 * <p>('Sales' Star, Gender, State, Marital Status)</p>
038 * </blockquote>
039 *
040 * <p>Note that different measures (in the same Star) occupy the same Aggregation.
041 * Aggregations belong to the AggregationManager, a singleton.</p>
042 * <p>Segments are pinned during the evaluation of a single MDX query. The query
043 * evaluates the expressions twice. The first pass, it finds which cell values it
044 * needs, pins the segments containing the ones which are already present (one
045 * pin-count for each cell value used), and builds a {@link CellRequest
046 * cell request} for those which are not present. It executes
047 * the cell request to bring the required cell values into the cache, again,
048 * pinned. Then it evalutes the query a second time, knowing that all cell values
049 * are available. Finally, it releases the pins.</p>
050 *
051 * <p>A Segment may have a list of excluded {@link Region} objects. These are
052 * caused by cache flushing. Usually a segment is a hypercube: it is defined by
053 * a set of values on each of its axes. But after a cache flush request, a
054 * segment may have a rectangular 'hole', and therefore not be a hypercube
055 * anymore.
056 *
057 * <p>For example, the segment defined by {CA, OR, WA} * {F, M} is a
058 * 2-dimensional hyper-rectangle with 6 cells. After flushing {CA, OR, TX} *
059 * {F}, the result is 4 cells:
060 *
061 * <pre>
062 * F M
063 * CA out in
064 * OR out in
065 * WA in in
066 * </pre>
067 *
068 * defined by the original segment minus the region ({CA, OR} * {F}).
069 *
070 * @author jhyde
071 * @since 21 March, 2002
072 * @version $Id: //open/mondrian/src/main/mondrian/rolap/agg/Segment.java#51 $
073 */
074 class Segment {
075 private static int nextId = 0; // generator for "id"
076
077 final int id; // for debug
078 private String desc;
079 final Aggregation aggregation;
080 final RolapStar.Measure measure;
081
082 final Aggregation.Axis[] axes;
083 private SegmentDataset data;
084 private final CellKey cellKey; // workspace
085
086 /** State of the segment (loading, ready, etc.). */
087 private State state;
088
089 /**
090 * List of regions to ignore when reading this segment. This list is
091 * populated when a region is flushed. The cells for these regions may be
092 * physically in the segment, because trimming segments can be expensive,
093 * but should still be ignored.
094 */
095 private final List<Region> excludedRegions;
096 private static final Logger LOGGER =
097 Logger.getLogger(Segment.class);
098
099 /**
100 * Creates a <code>Segment</code>; it's not loaded yet.
101 *
102 * @param aggregation The aggregation this <code>Segment</code> belongs to
103 * @param measure Measure whose values this Segment contains
104 * @param axes List of axes; each is a constraint plus a list of values
105 * @param excludedRegions List of regions which are not in this segment.
106 */
107 Segment(
108 Aggregation aggregation,
109 RolapStar.Measure measure,
110 Aggregation.Axis[] axes,
111 List<Region> excludedRegions)
112 {
113 this.id = nextId++;
114 this.aggregation = aggregation;
115 this.measure = measure;
116 this.axes = axes;
117 this.cellKey = CellKey.Generator.newCellKey(axes.length);
118 this.state = State.Loading;
119 this.excludedRegions = excludedRegions;
120 for (Region region : excludedRegions) {
121 assert region.getPredicates().size() == axes.length;
122 }
123 }
124
125 /**
126 * Sets the data, and notifies any threads which are blocked in
127 * {@link #waitUntilLoaded}.
128 */
129 synchronized void setData(
130 SegmentDataset data,
131 RolapAggregationManager.PinSet pinnedSegments) {
132 Util.assertTrue(this.data == null);
133 Util.assertTrue(this.state == State.Loading);
134
135 this.data = data;
136 this.state = State.Ready;
137
138 notifyAll();
139 }
140
141 /**
142 * If this segment is still loading, signals that it failed to load, and
143 * notifies any threads which are blocked in {@link #waitUntilLoaded}.
144 */
145 synchronized void setFailIfStillLoading() {
146 switch (state) {
147 case Loading:
148 Util.assertTrue(this.data == null);
149 this.state = State.Failed;
150 notifyAll();
151 break;
152 case Ready:
153 // The segment loaded just fine.
154 break;
155 default:
156 throw Util.badValue(state);
157 }
158 }
159
160 public boolean isReady() {
161 return (state == State.Ready);
162 }
163
164 boolean isFailed() {
165 return (state == State.Failed);
166 }
167
168 private void makeDescription(StringBuilder buf, boolean values) {
169 final String sep = Util.nl + " ";
170 buf.append(printSegmentHeaderInfo(sep));
171
172 RolapStar.Column[] columns = aggregation.getColumns();
173 for (int i = 0; i < columns.length; i++) {
174 buf.append(sep);
175 buf.append(columns[i].getExpression().getGenericExpression());
176 final Aggregation.Axis axis = axes[i];
177 axis.getPredicate().describe(buf);
178 if (values && isReady()) {
179 Object[] keys = axis.getKeys();
180 buf.append(", values={");
181 for (int j = 0; j < keys.length; j++) {
182 if (j > 0) {
183 buf.append(", ");
184 }
185 Object key = keys[j];
186 buf.append(key);
187 }
188 buf.append("}");
189 }
190 }
191 if (!excludedRegions.isEmpty()) {
192 buf.append(sep);
193 buf.append("excluded={");
194 int k = 0;
195 for (Region excludedRegion : excludedRegions) {
196 if (k++ > 0) {
197 buf.append(", ");
198 }
199 excludedRegion.describe(buf);
200 }
201 buf.append('}');
202 }
203 buf.append('}');
204 }
205
206 private String printSegmentHeaderInfo(String sep) {
207 StringBuilder buf = new StringBuilder();
208 buf.append("Segment #");
209 buf.append(id);
210 buf.append(" {");
211 buf.append(sep);
212 buf.append("measure=");
213 buf.append(measure.getAggregator().getExpression(
214 measure.getExpression().getGenericExpression()));
215 return buf.toString();
216 }
217
218 public String toString() {
219 if (this.desc == null) {
220 StringBuilder buf = new StringBuilder(64);
221 makeDescription(buf, false);
222 this.desc = buf.toString();
223 }
224 return this.desc;
225 }
226
227 /**
228 * Retrieves the value at the location identified by
229 * <code>keys</code>.
230 *
231 * <p>Returns<ul>
232 *
233 * <li>{@link Util#nullValue} if the cell value
234 * is null (because no fact table rows met those criteria);</li>
235 *
236 * <li><code>null</code> if the value is not supposed to be in this segment
237 * (because one or more of the keys do not pass the axis criteria);</li>
238 *
239 * <li>the data value otherwise</li>
240 *
241 * </ul></p>
242 *
243 */
244 synchronized Object getCellValue(Object[] keys) {
245 assert keys.length == axes.length;
246 int missed = 0;
247 for (int i = 0; i < keys.length; i++) {
248 Object key = keys[i];
249 int offset = axes[i].getOffset(key);
250 if (offset < 0) {
251 if (axes[i].getPredicate().evaluate(key)) {
252 // see whether this segment should contain this value
253 missed++;
254 continue;
255 } else {
256 // this value should not appear in this segment; we
257 // should be looking in a different segment
258 return null;
259 }
260 }
261 cellKey.setAxis(i, offset);
262 }
263 if (isExcluded(keys)) {
264 // this value should not appear in this segment; we
265 // should be looking in a different segment
266 return null;
267 }
268 if (missed > 0) {
269 // the value should be in this segment, but isn't, because one
270 // or more of its keys does have any values
271 return Util.nullValue;
272 } else {
273 Object o = data.get(cellKey);
274 if (o == null) {
275 o = Util.nullValue;
276 }
277 return o;
278 }
279 }
280
281 /**
282 * Returns whether the given set of key values will be in this segment
283 * when it finishes loading.
284 */
285 boolean wouldContain(Object[] keys) {
286 Util.assertTrue(keys.length == axes.length);
287 for (int i = 0; i < keys.length; i++) {
288 Object key = keys[i];
289 if (!axes[i].getPredicate().evaluate(key)) {
290 return false;
291 }
292 }
293 return !isExcluded(keys);
294 }
295
296 /**
297 * Returns whether a cell value is excluded from this segment.
298 */
299 private boolean isExcluded(Object[] keys) {
300 for (Region excludedRegion : excludedRegions) {
301 if (excludedRegion.wouldContain(keys)) {
302 return true;
303 }
304 }
305 return false;
306 }
307
308 /**
309 * Blocks until this segment has finished loading; if this segment has
310 * already loaded, returns immediately.
311 */
312 public synchronized void waitUntilLoaded() {
313 if (isLoading()) {
314 try {
315 LOGGER.debug("Waiting on " + printSegmentHeaderInfo(","));
316 wait();
317 } catch (InterruptedException e) {
318 }
319 switch (state) {
320 case Ready:
321 return; // excellent!
322 case Failed:
323 throw Util.newError("Pending segment failed to load: "
324 + toString());
325 default:
326 throw Util.badValue(state);
327 }
328 }
329 }
330
331 private boolean isLoading() {
332 return state == State.Loading;
333 }
334
335 /**
336 * Prints the state of this <code>Segment</code>, including constraints
337 * and values. Blocks the current thread until the segment is loaded.
338 *
339 * @param pw Writer
340 */
341 public void print(PrintWriter pw) {
342 waitUntilLoaded();
343 final StringBuilder buf = new StringBuilder();
344 makeDescription(buf, true);
345 pw.print(buf.toString());
346 pw.println();
347 }
348
349 public List<Region> getExcludedRegions() {
350 return excludedRegions;
351 }
352
353 /**
354 * Returns the number of cells in this Segment, deducting cells in
355 * excluded regions.
356 *
357 * <p>This method may return a value which is slightly too low, or
358 * occasionally even negative. This occurs when a Segment has more than one
359 * excluded region, and those regions overlap. Cells which are in both
360 * regions will be counted twice.
361 *
362 * @return Number of cells in this Segment
363 */
364 public int getCellCount() {
365 int cellCount = 1;
366 for (Aggregation.Axis axis : axes) {
367 cellCount *= axis.getKeys().length;
368 }
369 for (Region excludedRegion : excludedRegions) {
370 cellCount -= excludedRegion.cellCount;
371 }
372 return cellCount;
373 }
374
375 /**
376 * Creates a Segment which has the same dimensionality as this Segment and a
377 * subset of the values.
378 *
379 * <p>If <code>bestColumn</code> is not -1, the <code>bestColumn</code>th
380 * column's predicate should be replaced by <code>bestPredicate</code>.
381 *
382 * @param axisKeepBitSets For each axis, a bitmap of the axis values to
383 * keep; each axis must have at least one bit set
384 * @param bestColumn
385 * @param bestPredicate
386 * @param excludedRegions List of regions to exclude from segment
387 * @return Segment containing a subset of the values
388 */
389 Segment createSubSegment(
390 BitSet[] axisKeepBitSets,
391 int bestColumn,
392 StarColumnPredicate bestPredicate,
393 List<Segment.Region> excludedRegions) {
394 assert axisKeepBitSets.length == axes.length;
395
396 // Create a new segment with a subset of the values. If only one
397 // of the axes is restricted, restrict just that axis. If more than
398 // one of the axis is restricted, add a negation to the segment.
399 final Aggregation.Axis[] newAxes = axes.clone();
400
401 // For each axis, map from old position to new position.
402 final Map<Integer,Integer>[] axisPosMaps = new Map[axes.length];
403
404 int valueCount = 1;
405 for (int j = 0; j < axes.length; j++) {
406 Aggregation.Axis axis = axes[j];
407 StarColumnPredicate newPredicate = axis.getPredicate();
408 if (j == bestColumn) {
409 newPredicate = bestPredicate;
410 }
411 final Comparable<?>[] axisKeys = axis.getKeys();
412 BitSet keepBitSet = axisKeepBitSets[j];
413 int firstClearBit = keepBitSet.nextClearBit(0);
414 Comparable<?>[] newAxisKeys;
415 if (firstClearBit >= axisKeys.length) {
416 // Keep everything
417 newAxisKeys = axisKeys;
418 axisPosMaps[j] = null; // identity map
419 } else {
420 List<Object> newAxisKeyList = new ArrayList<Object>();
421 Map<Integer, Integer> map
422 = axisPosMaps[j]
423 = new HashMap<Integer, Integer>();
424 for (int bit = keepBitSet.nextSetBit(0);
425 bit >= 0;
426 bit = keepBitSet.nextSetBit(bit + 1)) {
427 map.put(bit, newAxisKeyList.size());
428 newAxisKeyList.add(axisKeys[bit]);
429 }
430 newAxisKeys =
431 newAxisKeyList.toArray(
432 new Comparable<?>[newAxisKeyList.size()]);
433 assert newAxisKeys.length > 0;
434 }
435 final Aggregation.Axis newAxis =
436 new Aggregation.Axis(newPredicate, newAxisKeys);
437 newAxes[j] = newAxis;
438 valueCount *= newAxisKeys.length;
439 }
440
441 // Create a new segment.
442 final Segment newSegment =
443 new Segment(aggregation, measure, newAxes, excludedRegions);
444
445 // Create a dataset containing a subset of the current dataset.
446 // Keep the same representation as the current dataset.
447 // (We could be smarter - sometimes a subset of a sparse dataset will
448 // be dense and VERY occasionally a subset of a relatively dense dataset
449 // will be sparse.)
450 SegmentDataset newData;
451 if (data instanceof SparseSegmentDataset) {
452 newData =
453 new SparseSegmentDataset(
454 newSegment);
455 } else {
456 Object[] newValues = new Object[valueCount];
457 newData =
458 new DenseSegmentDataset(
459 newSegment,
460 newValues);
461 }
462
463 // If the source is sparse, it is more efficient to iterate over the
464 // values we need. If it's dense, it doesn't matter too much.
465 int[] pos = new int[axes.length];
466 CellKey newKey = CellKey.Generator.newRefCellKey(pos);
467 data:
468 for (Map.Entry<CellKey, Object> entry : data) {
469 CellKey key = entry.getKey();
470
471 // Map each of the source coordinates to the target coordinate.
472 // If any of the coordinates maps to null, it means that the
473 // cell falls outside the subset.
474 for (int i = 0; i < pos.length; i++) {
475 int ordinal = key.getAxis(i);
476
477 Map<Integer, Integer> axisPosMap = axisPosMaps[i];
478 if (axisPosMap == null) {
479 pos[i] = ordinal;
480 } else {
481 Integer integer = axisPosMap.get(ordinal);
482 if (integer == null) {
483 continue data;
484 }
485 pos[i] = integer;
486 }
487 }
488 newData.put(newKey, entry.getValue());
489 }
490 newSegment.setData(newData, null);
491
492 return newSegment;
493 }
494
495 /**
496 * Returns this Segment's dataset, or null if the data has not yet been
497 * loaded.
498 */
499 SegmentDataset getData() {
500 return data;
501 }
502
503 /**
504 * <code>State</code> enumerates the allowable values of a segment's
505 * state.
506 */
507 private static enum State {
508 Initial, Loading, Ready, Failed
509 }
510
511 /**
512 * Definition of a region of values which are not in a segment.
513 *
514 * <p>A region is defined by a set of constraints, one for each column
515 * in the segment. A constraint may be
516 * {@link mondrian.rolap.agg.LiteralStarPredicate}(true), meaning that
517 * the column is unconstrained.
518 *
519 * <p>For example,
520 * <pre>
521 * segment (State={CA, OR, WA}, Gender=*)
522 * actual values {1997, 1998} * {CA, OR, WA} * {M, F} = 12 cells
523 * excluded region (Year=*, State={CA, OR}, Gender={F})
524 * excluded values {1997, 1998} * {CA, OR} * {F} = 4 cells
525 *
526 * Values:
527 *
528 * F M
529 * CA out in
530 * OR out in
531 * WA in in
532 * </pre>
533 *
534 * <p>Note that the resulting segment is not a hypercube: it has a 'hole'.
535 * This is why regions are required.
536 */
537 static class Region {
538 private final StarColumnPredicate[] predicates;
539 private final StarPredicate[] multiColumnPredicates;
540 private final int cellCount;
541
542 Region(
543 List<StarColumnPredicate> predicateList,
544 List<StarPredicate> multiColumnPredicateList,
545 int cellCount)
546 {
547 this.predicates =
548 predicateList.toArray(
549 new StarColumnPredicate[predicateList.size()]);
550 this.multiColumnPredicates =
551 multiColumnPredicateList.toArray(
552 new StarPredicate[multiColumnPredicateList.size()]);
553 this.cellCount = cellCount;
554 }
555
556 public List<StarColumnPredicate> getPredicates() {
557 return Collections.unmodifiableList(Arrays.asList(predicates));
558 }
559
560 public List<StarPredicate> getMultiColumnPredicates() {
561 return Collections.unmodifiableList(
562 Arrays.asList(multiColumnPredicates));
563 }
564
565 public int getCellCount() {
566 return cellCount;
567 }
568
569 public boolean wouldContain(Object[] keys) {
570 assert keys.length == predicates.length;
571 for (int i = 0; i < keys.length; i++) {
572 final Object key = keys[i];
573 final StarColumnPredicate predicate = predicates[i];
574 if (!predicate.evaluate(key)) {
575 return false;
576 }
577 }
578 return true;
579 }
580
581 public boolean equals(Object obj) {
582 if (obj instanceof Region) {
583 Region that = (Region) obj;
584 return Arrays.equals(
585 this.predicates, that.predicates) &&
586 Arrays.equals(
587 this.multiColumnPredicates,
588 that.multiColumnPredicates);
589 } else {
590 return false;
591 }
592 }
593
594 public int hashCode() {
595 return Arrays.hashCode(multiColumnPredicates) ^
596 Arrays.hashCode(predicates);
597 }
598
599 /**
600 * Describes this Segment.
601 * @param buf Buffer to write to.
602 */
603 public void describe(StringBuilder buf) {
604 int k = 0;
605 for (StarColumnPredicate predicate : predicates) {
606 if (predicate instanceof LiteralStarPredicate &&
607 ((LiteralStarPredicate) predicate).getValue()) {
608 continue;
609 }
610 if (k++ > 0) {
611 buf.append(" AND ");
612 }
613 predicate.describe(buf);
614 }
615 for (StarPredicate predicate : multiColumnPredicates) {
616 if (predicate instanceof LiteralStarPredicate &&
617 ((LiteralStarPredicate) predicate).getValue()) {
618 continue;
619 }
620 if (k++ > 0) {
621 buf.append(" AND ");
622 }
623 predicate.describe(buf);
624 }
625 }
626 }
627 }
628
629 // End Segment.java