001/* 002// This software is subject to the terms of the Eclipse Public License v1.0 003// Agreement, available at the following URL: 004// http://www.eclipse.org/legal/epl-v10.html. 005// You must accept the terms of that agreement to use this software. 006// 007// Copyright (C) 2011-2013 Pentaho and others 008// All Rights Reserved. 009*/ 010package mondrian.rolap.cache; 011 012import mondrian.olap.QueryCanceledException; 013import mondrian.olap.Util; 014import mondrian.rolap.BitKey; 015import mondrian.rolap.RolapUtil; 016import mondrian.rolap.agg.*; 017import mondrian.server.Execution; 018import mondrian.spi.*; 019import mondrian.util.*; 020 021import java.io.PrintWriter; 022import java.sql.Statement; 023import java.util.*; 024import java.util.Map.Entry; 025import java.util.concurrent.CopyOnWriteArrayList; 026import java.util.concurrent.Future; 027 028/** 029 * Data structure that identifies which segments contain cells. 030 * 031 * <p>Not thread safe.</p> 032 * 033 * @author Julian Hyde 034 */ 035public class SegmentCacheIndexImpl implements SegmentCacheIndex { 036 037 private final Map<List, List<SegmentHeader>> bitkeyMap = 038 new HashMap<List, List<SegmentHeader>>(); 039 040 /** 041 * The fact map allows us to spot quickly which 042 * segments have facts relating to a given header. 043 */ 044 private final Map<List, FactInfo> factMap = 045 new HashMap<List, FactInfo>(); 046 047 /** 048 * The fuzzy fact map allows us to spot quickly which 049 * segments have facts relating to a given header, but doesn't 050 * consider the compound predicates in the key. This allows 051 * flush operations to be consistent. 052 */ 053 // TODO Get rid of the fuzzy map once we have a way to parse 054 // compound predicates into rich objects that can be serialized 055 // as part of the SegmentHeader. 056 private final Map<List, FuzzyFactInfo> fuzzyFactMap = 057 new HashMap<List, FuzzyFactInfo>(); 058 059 private final Map<SegmentHeader, HeaderInfo> headerMap = 060 new HashMap<SegmentHeader, HeaderInfo>(); 061 062 private final Thread thread; 063 064 /** 065 * Creates a SegmentCacheIndexImpl. 066 * 067 * @param thread Thread that must be used to execute commands. 068 */ 069 public SegmentCacheIndexImpl(Thread thread) { 070 this.thread = thread; 071 assert thread != null; 072 } 073 074 public static List makeConverterKey(SegmentHeader header) { 075 return Arrays.asList( 076 header.schemaName, 077 header.schemaChecksum, 078 header.cubeName, 079 header.rolapStarFactTableName, 080 header.measureName, 081 header.compoundPredicates); 082 } 083 084 public static List makeConverterKey(CellRequest request, AggregationKey key) 085 { 086 return Arrays.asList( 087 request.getMeasure().getStar().getSchema().getName(), 088 request.getMeasure().getStar().getSchema().getChecksum(), 089 request.getMeasure().getCubeName(), 090 request.getMeasure().getStar().getFactTable().getAlias(), 091 request.getMeasure().getName(), 092 AggregationKey.getCompoundPredicateStringList( 093 key.getStar(), 094 key.getCompoundPredicateList())); 095 } 096 097 public List<SegmentHeader> locate( 098 String schemaName, 099 ByteString schemaChecksum, 100 String cubeName, 101 String measureName, 102 String rolapStarFactTableName, 103 BitKey constrainedColsBitKey, 104 Map<String, Comparable> coordinates, 105 List<String> compoundPredicates) 106 { 107 checkThread(); 108 109 List<SegmentHeader> list = Collections.emptyList(); 110 final List starKey = 111 makeBitkeyKey( 112 schemaName, 113 schemaChecksum, 114 cubeName, 115 rolapStarFactTableName, 116 constrainedColsBitKey, 117 measureName, 118 compoundPredicates); 119 final List<SegmentHeader> headerList = bitkeyMap.get(starKey); 120 if (headerList == null) { 121 return Collections.emptyList(); 122 } 123 for (SegmentHeader header : headerList) { 124 if (matches(header, coordinates, compoundPredicates)) { 125 // Be lazy. Don't allocate a list unless there is at least one 126 // entry. 127 if (list.isEmpty()) { 128 list = new ArrayList<SegmentHeader>(); 129 } 130 list.add(header); 131 } 132 } 133 return list; 134 } 135 136 public boolean add( 137 SegmentHeader header, 138 boolean loading, 139 SegmentBuilder.SegmentConverter converter) 140 { 141 checkThread(); 142 143 HeaderInfo headerInfo = headerMap.get(header); 144 if (headerInfo != null) { 145 if (loading && headerInfo.slot == null) { 146 headerInfo.slot = new SlotFuture<SegmentBody>(); 147 // Returns true. same as creating. 148 return true; 149 } 150 return false; 151 } 152 headerInfo = new HeaderInfo(); 153 if (loading) { 154 headerInfo.slot = new SlotFuture<SegmentBody>(); 155 } 156 headerMap.put(header, headerInfo); 157 158 final List bitkeyKey = makeBitkeyKey(header); 159 List<SegmentHeader> headerList = bitkeyMap.get(bitkeyKey); 160 if (headerList == null) { 161 headerList = new ArrayList<SegmentHeader>(); 162 bitkeyMap.put(bitkeyKey, headerList); 163 } 164 headerList.add(header); 165 166 final List factKey = makeFactKey(header); 167 FactInfo factInfo = factMap.get(factKey); 168 if (factInfo == null) { 169 factInfo = new FactInfo(); 170 factMap.put(factKey, factInfo); 171 } 172 factInfo.headerList.add(header); 173 factInfo.bitkeyPoset.add(header.getConstrainedColumnsBitKey()); 174 if (converter != null) { 175 factInfo.converter = converter; 176 } 177 178 final List fuzzyFactKey = makeFuzzyFactKey(header); 179 FuzzyFactInfo fuzzyFactInfo = fuzzyFactMap.get(fuzzyFactKey); 180 if (fuzzyFactInfo == null) { 181 fuzzyFactInfo = new FuzzyFactInfo(); 182 fuzzyFactMap.put(fuzzyFactKey, fuzzyFactInfo); 183 } 184 fuzzyFactInfo.headerList.add(header); 185 return true; 186 } 187 188 public void loadSucceeded(SegmentHeader header, SegmentBody body) { 189 checkThread(); 190 191 final HeaderInfo headerInfo = headerMap.get(header); 192 assert headerInfo != null 193 : "segment header " + header.getUniqueID() + " is missing"; 194 assert headerInfo.slot != null 195 : "segment header " + header.getUniqueID() + " is not loading"; 196 if (!headerInfo.slot.isDone()) { 197 headerInfo.slot.put(body); 198 } 199 if (headerInfo.removeAfterLoad) { 200 remove(header); 201 } 202 // Cleanup the HeaderInfo 203 headerInfo.stmt = null; 204 headerInfo.clients.clear(); 205 } 206 207 public void loadFailed(SegmentHeader header, Throwable throwable) { 208 checkThread(); 209 210 final HeaderInfo headerInfo = headerMap.get(header); 211 assert headerInfo != null 212 : "segment header " + header.getUniqueID() + " is missing"; 213 assert headerInfo.slot != null 214 : "segment header " + header.getUniqueID() + " is not loading"; 215 headerInfo.slot.fail(throwable); 216 remove(header); 217 // Cleanup the HeaderInfo 218 headerInfo.stmt = null; 219 headerInfo.clients.clear(); 220 } 221 222 public void remove(SegmentHeader header) { 223 checkThread(); 224 225 final HeaderInfo headerInfo = headerMap.get(header); 226 if (headerInfo == null) { 227 return; 228 } 229 if (headerInfo.slot != null && !headerInfo.slot.isDone()) { 230 // Cannot remove while load is pending; flag for removal after load 231 headerInfo.removeAfterLoad = true; 232 return; 233 } 234 235 headerMap.remove(header); 236 237 final List factKey = makeFactKey(header); 238 final FactInfo factInfo = factMap.get(factKey); 239 if (factInfo != null) { 240 factInfo.headerList.remove(header); 241 if (factInfo.headerList.size() == 0) { 242 factMap.remove(factKey); 243 } 244 } 245 246 final List fuzzyFactKey = makeFuzzyFactKey(header); 247 final FuzzyFactInfo fuzzyFactInfo = fuzzyFactMap.get(fuzzyFactKey); 248 if (fuzzyFactInfo != null) { 249 fuzzyFactInfo.headerList.remove(header); 250 if (fuzzyFactInfo.headerList.size() == 0) { 251 fuzzyFactMap.remove(fuzzyFactKey); 252 } 253 } 254 255 final List bitkeyKey = makeBitkeyKey(header); 256 final List<SegmentHeader> headerList = bitkeyMap.get(bitkeyKey); 257 headerList.remove(header); 258 if (headerList.size() == 0) { 259 bitkeyMap.remove(bitkeyKey); 260 factInfo.bitkeyPoset.remove(header.getConstrainedColumnsBitKey()); 261 } 262 } 263 264 private void checkThread() { 265 assert thread == Thread.currentThread() 266 : "expected " + thread + ", but was " + Thread.currentThread(); 267 } 268 269 public static boolean matches( 270 SegmentHeader header, 271 Map<String, Comparable> coords, 272 List<String> compoundPredicates) 273 { 274 if (!header.compoundPredicates.equals(compoundPredicates)) { 275 return false; 276 } 277 for (Map.Entry<String, Comparable> entry : coords.entrySet()) { 278 // Check if the segment explicitly excludes this coordinate. 279 final SegmentColumn excludedColumn = 280 header.getExcludedRegion(entry.getKey()); 281 if (excludedColumn != null) { 282 final SortedSet<Comparable> values = 283 excludedColumn.getValues(); 284 if (values == null || values.contains(entry.getValue())) { 285 return false; 286 } 287 } 288 // Check if the dimensionality of the segment intersects 289 // with the coordinate. 290 final SegmentColumn constrainedColumn = 291 header.getConstrainedColumn(entry.getKey()); 292 if (constrainedColumn == null) { 293 // One of the required column/value pairs is not a constraining 294 // column for the header. This will not happen if the header 295 // has been acquired from bitkeyMap, but may happen if a list 296 // of mixed-dimensionality headers is being scanned. 297 return false; 298 } 299 final SortedSet<Comparable> values = 300 constrainedColumn.getValues(); 301 if (values != null 302 && !values.contains(entry.getValue())) 303 { 304 return false; 305 } 306 } 307 return true; 308 } 309 310 public List<SegmentHeader> intersectRegion( 311 String schemaName, 312 ByteString schemaChecksum, 313 String cubeName, 314 String measureName, 315 String rolapStarFactTableName, 316 SegmentColumn[] region) 317 { 318 checkThread(); 319 320 final List factKey = makeFuzzyFactKey( 321 schemaName, 322 schemaChecksum, 323 cubeName, 324 rolapStarFactTableName, 325 measureName); 326 final FuzzyFactInfo factInfo = fuzzyFactMap.get(factKey); 327 List<SegmentHeader> list = Collections.emptyList(); 328 if (factInfo == null) { 329 return list; 330 } 331 for (SegmentHeader header : factInfo.headerList) { 332 // Don't return stale segments. 333 if (headerMap.get(header).removeAfterLoad) { 334 continue; 335 } 336 if (intersects(header, region)) { 337 // Be lazy. Don't allocate a list unless there is at least one 338 // entry. 339 if (list.isEmpty()) { 340 list = new ArrayList<SegmentHeader>(); 341 } 342 list.add(header); 343 } 344 } 345 return list; 346 } 347 348 private boolean intersects( 349 SegmentHeader header, 350 SegmentColumn[] region) 351 { 352 // most selective condition first 353 if (region.length == 0) { 354 return true; 355 } 356 for (SegmentColumn regionColumn : region) { 357 final SegmentColumn headerColumn = 358 header.getConstrainedColumn(regionColumn.getColumnExpression()); 359 if (headerColumn == null) { 360 // If the segment header doesn't contain a column specified 361 // by the region, then it always implicitly intersects. 362 // This allows flush operations to be valid. 363 return true; 364 } 365 final SortedSet<Comparable> regionValues = 366 regionColumn.getValues(); 367 final SortedSet<Comparable> headerValues = 368 headerColumn.getValues(); 369 if (headerValues == null || regionValues == null) { 370 // This is a wildcard, so it always intersects. 371 return true; 372 } 373 for (Comparable myValue : regionValues) { 374 if (headerValues.contains(myValue)) { 375 return true; 376 } 377 } 378 } 379 return false; 380 } 381 382 public void printCacheState(PrintWriter pw) { 383 checkThread(); 384 final List<List<SegmentHeader>> values = 385 new ArrayList<List<SegmentHeader>>( 386 bitkeyMap.values()); 387 Collections.sort( 388 values, 389 new Comparator<List<SegmentHeader>>() { 390 public int compare( 391 List<SegmentHeader> o1, 392 List<SegmentHeader> o2) 393 { 394 if (o1.size() == 0) { 395 return -1; 396 } 397 if (o2.size() == 0) { 398 return 1; 399 } 400 return o1.get(0).getUniqueID() 401 .compareTo(o2.get(0).getUniqueID()); 402 } 403 }); 404 for (List<SegmentHeader> key : values) { 405 final List<SegmentHeader> headerList = 406 new ArrayList<SegmentHeader>(key); 407 Collections.sort( 408 headerList, 409 new Comparator<SegmentHeader>() { 410 public int compare(SegmentHeader o1, SegmentHeader o2) { 411 return o1.getUniqueID().compareTo(o2.getUniqueID()); 412 } 413 }); 414 for (SegmentHeader header : headerList) { 415 pw.println(header.getDescription()); 416 } 417 } 418 } 419 420 public Future<SegmentBody> getFuture(Execution exec, SegmentHeader header) { 421 checkThread(); 422 HeaderInfo hi = headerMap.get(header); 423 if (!hi.clients.contains(exec)) { 424 hi.clients.add(exec); 425 } 426 return hi.slot; 427 } 428 429 public void linkSqlStatement(SegmentHeader header, Statement stmt) { 430 checkThread(); 431 headerMap.get(header).stmt = stmt; 432 } 433 434 public boolean contains(SegmentHeader header) { 435 return headerMap.containsKey(header); 436 } 437 438 public void cancel(Execution exec) { 439 checkThread(); 440 List<SegmentHeader> toRemove = new ArrayList<SegmentHeader>(); 441 for (Entry<SegmentHeader, HeaderInfo> entry : headerMap.entrySet()) { 442 if (entry.getValue().clients.remove(exec)) { 443 if (entry.getValue().slot != null 444 && !entry.getValue().slot.isDone() 445 && entry.getValue().clients.isEmpty()) 446 { 447 toRemove.add(entry.getKey()); 448 } 449 } 450 } 451 // Make sure to cleanup the orphaned segments. 452 for (SegmentHeader header : toRemove) { 453 final Statement stmt = headerMap.get(header).stmt; 454 loadFailed( 455 header, 456 new QueryCanceledException( 457 "Canceling due to an absence of interested parties.")); 458 // We only want to cancel the statement, but we can't close it. 459 // Some drivers will not notice the interruption flag on their 460 // own thread before a considerable time has passed. If we were 461 // using a pooling layer, calling close() would make the 462 // underlying connection available again, despite the first 463 // statement still being processed. Some drivers will fail 464 // there. It is therefore important to close and release the 465 // resources on the proper thread, namely, the thread which 466 // runs the actual statement. 467 Util.cancelStatement(stmt); 468 } 469 } 470 471 public SegmentBuilder.SegmentConverter getConverter( 472 String schemaName, 473 ByteString schemaChecksum, 474 String cubeName, 475 String rolapStarFactTableName, 476 String measureName, 477 List<String> compoundPredicates) 478 { 479 checkThread(); 480 481 final List factKey = makeFactKey( 482 schemaName, 483 schemaChecksum, 484 cubeName, 485 rolapStarFactTableName, 486 measureName, 487 compoundPredicates); 488 final FactInfo factInfo = factMap.get(factKey); 489 if (factInfo == null) { 490 return null; 491 } 492 return factInfo.converter; 493 } 494 495 public void setConverter( 496 String schemaName, 497 ByteString schemaChecksum, 498 String cubeName, 499 String rolapStarFactTableName, 500 String measureName, 501 List<String> compoundPredicates, 502 SegmentBuilder.SegmentConverter converter) 503 { 504 checkThread(); 505 506 final List factKey = makeFactKey( 507 schemaName, 508 schemaChecksum, 509 cubeName, 510 rolapStarFactTableName, 511 measureName, 512 compoundPredicates); 513 final FactInfo factInfo = factMap.get(factKey); 514 assert factInfo != null : "should have called 'add' first"; 515 if (factInfo == null) { 516 return; 517 } 518 factInfo.converter = converter; 519 } 520 521 private List makeBitkeyKey(SegmentHeader header) { 522 return makeBitkeyKey( 523 header.schemaName, 524 header.schemaChecksum, 525 header.cubeName, 526 header.rolapStarFactTableName, 527 header.constrainedColsBitKey, 528 header.measureName, 529 header.compoundPredicates); 530 } 531 532 private List makeBitkeyKey( 533 String schemaName, 534 ByteString schemaChecksum, 535 String cubeName, 536 String rolapStarFactTableName, 537 BitKey constrainedColsBitKey, 538 String measureName, 539 List<String> compoundPredicates) 540 { 541 return Arrays.asList( 542 schemaName, 543 schemaChecksum, 544 cubeName, 545 rolapStarFactTableName, 546 constrainedColsBitKey, 547 measureName, 548 compoundPredicates); 549 } 550 551 private List makeFactKey(SegmentHeader header) { 552 return makeFactKey( 553 header.schemaName, 554 header.schemaChecksum, 555 header.cubeName, 556 header.rolapStarFactTableName, 557 header.measureName, 558 header.compoundPredicates); 559 } 560 561 private List makeFactKey( 562 String schemaName, 563 ByteString schemaChecksum, 564 String cubeName, 565 String rolapStarFactTableName, 566 String measureName, 567 List<String> compoundPredicates) 568 { 569 return Arrays.asList( 570 schemaName, 571 schemaChecksum, 572 cubeName, 573 rolapStarFactTableName, 574 measureName, 575 compoundPredicates); 576 } 577 578 private List makeFuzzyFactKey(SegmentHeader header) { 579 return makeFuzzyFactKey( 580 header.schemaName, 581 header.schemaChecksum, 582 header.cubeName, 583 header.rolapStarFactTableName, 584 header.measureName); 585 } 586 587 private List makeFuzzyFactKey( 588 String schemaName, 589 ByteString schemaChecksum, 590 String cubeName, 591 String rolapStarFactTableName, 592 String measureName) 593 { 594 return Arrays.asList( 595 schemaName, 596 schemaChecksum, 597 cubeName, 598 rolapStarFactTableName, 599 measureName); 600 } 601 602 public List<List<SegmentHeader>> findRollupCandidates( 603 String schemaName, 604 ByteString schemaChecksum, 605 String cubeName, 606 String measureName, 607 String rolapStarFactTableName, 608 BitKey constrainedColsBitKey, 609 Map<String, Comparable> coordinates, 610 List<String> compoundPredicates) 611 { 612 final List factKey = makeFactKey( 613 schemaName, 614 schemaChecksum, 615 cubeName, 616 rolapStarFactTableName, 617 measureName, 618 compoundPredicates); 619 final FactInfo factInfo = factMap.get(factKey); 620 if (factInfo == null) { 621 return Collections.emptyList(); 622 } 623 624 // Iterate over all dimensionalities that are a superset of the desired 625 // columns and for which a segment is known to exist. 626 // 627 // It helps that getAncestors returns dimensionalities with fewer bits 628 // set first. These will contain fewer cells, and therefore be less 629 // effort to roll up. 630 631 final List<List<SegmentHeader>> list = 632 new ArrayList<List<SegmentHeader>>(); 633 final List<BitKey> ancestors = 634 factInfo.bitkeyPoset.getAncestors(constrainedColsBitKey); 635 for (BitKey bitKey : ancestors) { 636 final List bitkeyKey = makeBitkeyKey( 637 schemaName, 638 schemaChecksum, 639 cubeName, 640 rolapStarFactTableName, 641 bitKey, 642 measureName, 643 compoundPredicates); 644 final List<SegmentHeader> headers = bitkeyMap.get(bitkeyKey); 645 assert headers != null : "bitkeyPoset / bitkeyMap inconsistency"; 646 647 // For columns that are still present after roll up, make sure that 648 // the required value is in the range covered by the segment. 649 // Of the columns that are being aggregated away, are all of 650 // them wildcarded? If so, this segment is a match. If not, we 651 // will need to combine with other segments later. 652 findRollupCandidatesAmong(coordinates, list, headers); 653 } 654 return list; 655 } 656 657 /** 658 * Finds rollup candidates among a list of headers with the same 659 * dimensionality. 660 * 661 * <p>For each column that is being aggregated away, we need to ensure that 662 * we have all values of that column. If the column is wildcarded, it's 663 * easy. For example, if we wish to roll up to create Segment1:</p> 664 * 665 * <pre>Segment1(Year=1997, MaritalStatus=*)</pre> 666 * 667 * <p>then clearly Segment2:</p> 668 * 669 * <pre>Segment2(Year=1997, MaritalStatus=*, Gender=*, Nation=*)</pre> 670 * 671 * <p>has all gender and Nation values. If the values are specified as a 672 * list:</p> 673 * 674 * <pre>Segment3(Year=1997, MaritalStatus=*, Gender={M, F}, Nation=*)</pre> 675 * 676 * <p>then we need to check the metadata. We see that Gender has two 677 * distinct values in the database, and we have two values, therefore we 678 * have all of them.</p> 679 * 680 * <p>What if we have multiple non-wildcard columns? Consider:</p> 681 * 682 * <pre> 683 * Segment4(Year=1997, MaritalStatus=*, Gender={M}, 684 Nation={Mexico, USA}) 685 * Segment5(Year=1997, MaritalStatus=*, Gender={F}, 686 Nation={USA}) 687 * Segment6(Year=1997, MaritalStatus=*, Gender={F, M}, 688 Nation={Canada, Mexico, Honduras, Belize}) 689 * </pre> 690 * 691 * <p>The problem is similar to finding whether a collection of rectangular 692 * regions covers a rectangle (or, generalizing to n dimensions, an 693 * n-cube). Or better, find a minimal collection of regions.</p> 694 * 695 * <p>Our algorithm solves it by iterating over all combinations of values. 696 * Those combinations are exponential in theory, but tractible in practice, 697 * using the following trick. The algorithm reduces the number of 698 * combinations by looking for values that are always treated the same. In 699 * the above, Canada, Honduras and Belize are always treated the same, so to 700 * prove covering, it is sufficient to prove that all combinations involving 701 * Canada are covered.</p> 702 * 703 * @param coordinates Coordinates 704 * @param list List to write candidates to 705 * @param headers Headers of candidate segments 706 */ 707 private void findRollupCandidatesAmong( 708 Map<String, Comparable> coordinates, 709 List<List<SegmentHeader>> list, 710 List<SegmentHeader> headers) 711 { 712 final List<Pair<SegmentHeader, List<SegmentColumn>>> matchingHeaders = 713 new ArrayList<Pair<SegmentHeader, List<SegmentColumn>>>(); 714 headerLoop: 715 for (SegmentHeader header : headers) { 716 // Skip headers that have exclusions. 717 // 718 // TODO: This is a bit harsh. 719 if (!header.getExcludedRegions().isEmpty()) { 720 continue; 721 } 722 723 List<SegmentColumn> nonWildcards = 724 new ArrayList<SegmentColumn>(); 725 for (SegmentColumn column : header.getConstrainedColumns()) { 726 final SegmentColumn constrainedColumn = 727 header.getConstrainedColumn(column.columnExpression); 728 729 // REVIEW: How are null key values represented in coordinates? 730 // Assuming that they are represented by null ref. 731 if (coordinates.containsKey(column.columnExpression)) { 732 // Matching column. Will not be aggregated away. Needs 733 // to be in range. 734 Comparable value = 735 coordinates.get(column.columnExpression); 736 if (value == null) { 737 value = RolapUtil.sqlNullValue; 738 } 739 if (constrainedColumn.values != null 740 && !constrainedColumn.values.contains(value)) 741 { 742 continue headerLoop; 743 } 744 } else { 745 // Non-matching column. Will be aggregated away. Needs 746 // to be wildcarded (or some more complicated conditions 747 // to be dealt with later). 748 if (constrainedColumn.values != null) { 749 nonWildcards.add(constrainedColumn); 750 } 751 } 752 } 753 754 if (nonWildcards.isEmpty()) { 755 list.add(Collections.singletonList(header)); 756 } else { 757 matchingHeaders.add(Pair.of(header, nonWildcards)); 758 } 759 } 760 761 // Find combinations of segments that can roll up. Need at least two. 762 if (matchingHeaders.size() < 2) { 763 return; 764 } 765 766 // Collect the list of non-wildcarded columns. 767 final List<SegmentColumn> columnList = new ArrayList<SegmentColumn>(); 768 final List<String> columnNameList = new ArrayList<String>(); 769 for (Pair<SegmentHeader, List<SegmentColumn>> pair : matchingHeaders) { 770 for (SegmentColumn column : pair.right) { 771 if (!columnNameList.contains(column.columnExpression)) { 772 final int valueCount = column.getValueCount(); 773 if (valueCount <= 0) { 774 // Impossible to safely roll up. If we don't know the 775 // number of values, we don't know that we have all of 776 // them. 777 return; 778 } 779 columnList.add(column); 780 columnNameList.add(column.columnExpression); 781 } 782 } 783 } 784 785 // Gather known values of each column. For each value, remember which 786 // segments refer to it. 787 final List<List<Comparable>> valueLists = 788 new ArrayList<List<Comparable>>(); 789 for (SegmentColumn column : columnList) { 790 // For each value, which equivalence class it belongs to. 791 final SortedMap<Comparable, BitSet> valueMap = 792 new TreeMap<Comparable, BitSet>(RolapUtil.ROLAP_COMPARATOR); 793 794 int h = -1; 795 for (SegmentHeader header : Pair.leftIter(matchingHeaders)) { 796 ++h; 797 final SegmentColumn column1 = 798 header.getConstrainedColumn( 799 column.columnExpression); 800 if (column1.getValues() == null) { 801 // Wildcard. Mark all values as present. 802 for (Entry<Comparable, BitSet> entry : valueMap.entrySet()) 803 { 804 for (int pos = 0; 805 pos < entry.getValue().cardinality(); 806 pos++) 807 { 808 entry.getValue().set(pos); 809 } 810 } 811 } else { 812 for (Comparable value : column1.getValues()) { 813 BitSet bitSet = valueMap.get(value); 814 if (bitSet == null) { 815 bitSet = new BitSet(); 816 valueMap.put(value, bitSet); 817 } 818 bitSet.set(h); 819 } 820 } 821 } 822 823 // Is the number of values discovered equal to the known cardinality 824 // of the column? If not, we can't cover the space. 825 if (valueMap.size() < column.valueCount) { 826 return; 827 } 828 829 // Build equivalence sets of values. These group together values 830 // that are used identically in segments. 831 // 832 // For instance, given segments Sx over column c, 833 // 834 // S1: c = {1, 2, 3, 4} 835 // S2: c = {3, 4, 5} 836 // S3: c = {3, 6, 7, 8} 837 // 838 // the equivalence classes are: 839 // 840 // E1 = {1, 2} used in {S1} 841 // E2 = {3} used in {S1, S2, S3} 842 // E3 = {4} used in {S1, S2} 843 // E4 = {6, 7, 8} used in {S3} 844 // 845 // The equivalence classes reduce the size of the search space. (In 846 // this case, from 8 values to 4 classes.) We can use any value in a 847 // class to stand for all values. 848 final Map<BitSet, Comparable> eqclassPrimaryValues = 849 new HashMap<BitSet, Comparable>(); 850 for (Map.Entry<Comparable, BitSet> entry : valueMap.entrySet()) { 851 final BitSet bitSet = entry.getValue(); 852 if (!eqclassPrimaryValues.containsKey(bitSet)) { 853 final Comparable value = entry.getKey(); 854 eqclassPrimaryValues.put(bitSet, value); 855 } 856 } 857 valueLists.add( 858 new ArrayList<Comparable>( 859 eqclassPrimaryValues.values())); 860 } 861 862 // Iterate over every combination of values, and make sure that some 863 // segment can satisfy each. 864 // 865 // TODO: A greedy algorithm would probably be better. Rather than adding 866 // the first segment that contains a particular value combination, add 867 // the segment that contains the most value combinations that we are are 868 // not currently covering. 869 final CartesianProductList<Comparable> tuples = 870 new CartesianProductList<Comparable>(valueLists); 871 final List<SegmentHeader> usedSegments = new ArrayList<SegmentHeader>(); 872 final List<SegmentHeader> unusedSegments = 873 new ArrayList<SegmentHeader>(Pair.left(matchingHeaders)); 874 tupleLoop: 875 for (List<Comparable> tuple : tuples) { 876 // If the value combination is handled by one of the used segments, 877 // great! 878 for (SegmentHeader segment : usedSegments) { 879 if (contains(segment, tuple, columnNameList)) { 880 continue tupleLoop; 881 } 882 } 883 // Does one of the unused segments contain it? Use the first one we 884 // find. 885 for (SegmentHeader segment : unusedSegments) { 886 if (contains(segment, tuple, columnNameList)) { 887 unusedSegments.remove(segment); 888 usedSegments.add(segment); 889 continue tupleLoop; 890 } 891 } 892 // There was a value combination not contained in any of the 893 // segments. Fail. 894 return; 895 } 896 list.add(usedSegments); 897 } 898 899 private boolean contains( 900 SegmentHeader segment, 901 List<Comparable> values, 902 List<String> columns) 903 { 904 for (int i = 0; i < columns.size(); i++) { 905 String columnName = columns.get(i); 906 final SegmentColumn column = 907 segment.getConstrainedColumn(columnName); 908 final SortedSet<Comparable> valueSet = column.getValues(); 909 if (valueSet != null && !valueSet.contains(values.get(i))) { 910 return false; 911 } 912 } 913 return true; 914 } 915 916 private static class FactInfo { 917 private static final PartiallyOrderedSet.Ordering<BitKey> ORDERING = 918 new PartiallyOrderedSet.Ordering<BitKey>() { 919 public boolean lessThan(BitKey e1, BitKey e2) { 920 return e2.isSuperSetOf(e1); 921 } 922 }; 923 924 private final List<SegmentHeader> headerList = 925 new ArrayList<SegmentHeader>(); 926 927 private final PartiallyOrderedSet<BitKey> bitkeyPoset = 928 new PartiallyOrderedSet<BitKey>(ORDERING); 929 930 private SegmentBuilder.SegmentConverter converter; 931 932 FactInfo() { 933 } 934 } 935 936 private static class FuzzyFactInfo { 937 private final List<SegmentHeader> headerList = 938 new ArrayList<SegmentHeader>(); 939 940 FuzzyFactInfo() { 941 } 942 } 943 944 /** 945 * A private class that we use in the index to track who was interested in 946 * which headers, the SQL statement that is populating it and a future 947 * object which we pass to clients. 948 */ 949 private static class HeaderInfo { 950 /** 951 * The SQL statement populating this header. 952 * Will be null until the SQL thread calls us back to register it. 953 */ 954 private Statement stmt; 955 /** 956 * The future object to pass on to clients. 957 */ 958 private SlotFuture<SegmentBody> slot; 959 /** 960 * A list of clients interested in this segment. 961 */ 962 private final List<Execution> clients = 963 new CopyOnWriteArrayList<Execution>(); 964 /** 965 * Whether this segment is already considered stale and must 966 * be deleted after it is done loading. This can happen 967 * when flushing. 968 */ 969 private boolean removeAfterLoad; 970 } 971} 972 973// End SegmentCacheIndexImpl.java