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