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) 2005-2012 Pentaho
008// All Rights Reserved.
009*/
010package mondrian.olap.fun;
011
012import mondrian.calc.*;
013import mondrian.calc.impl.*;
014import mondrian.mdx.ResolvedFunCall;
015import mondrian.olap.*;
016import mondrian.olap.Role.RollupPolicy;
017import mondrian.rolap.RolapAggregator;
018import mondrian.rolap.RolapEvaluator;
019
020import org.eigenbase.util.property.IntegerProperty;
021
022import java.util.*;
023
024/**
025 * Definition of the <code>AGGREGATE</code> MDX function.
026 *
027 * @author jhyde
028 * @since 2005/8/14
029 */
030public class AggregateFunDef extends AbstractAggregateFunDef {
031
032    private static final String TIMING_NAME =
033        AggregateFunDef.class.getSimpleName();
034
035    static final ReflectiveMultiResolver resolver =
036        new ReflectiveMultiResolver(
037            "Aggregate", "Aggregate(<Set>[, <Numeric Expression>])",
038            "Returns a calculated value using the appropriate aggregate function, based on the context of the query.",
039            new String[]{"fnx", "fnxn"},
040            AggregateFunDef.class);
041
042    /**
043     * Creates an AggregateFunDef.
044     *
045     * @param dummyFunDef Dummy function
046     */
047    public AggregateFunDef(FunDef dummyFunDef) {
048        super(dummyFunDef);
049    }
050
051    public Calc compileCall(ResolvedFunCall call, ExpCompiler compiler) {
052        final ListCalc listCalc = compiler.compileList(call.getArg(0));
053        final Calc calc =
054            call.getArgCount() > 1
055            ? compiler.compileScalar(call.getArg(1), true)
056            : new ValueCalc(call);
057        return new AggregateCalc(call, listCalc, calc);
058    }
059
060    public static class AggregateCalc extends GenericCalc {
061        private final ListCalc listCalc;
062        private final Calc calc;
063
064        public AggregateCalc(Exp exp, ListCalc listCalc, Calc calc) {
065            super(exp, new Calc[]{listCalc, calc});
066            this.listCalc = listCalc;
067            this.calc = calc;
068        }
069
070        public Object evaluate(Evaluator evaluator) {
071            evaluator.getTiming().markStart(TIMING_NAME);
072            try {
073                TupleList list = evaluateCurrentList(listCalc, evaluator);
074                return aggregate(calc, evaluator, list);
075            } finally {
076                evaluator.getTiming().markEnd(TIMING_NAME);
077            }
078        }
079
080        /**
081         * Computes an expression for each element of a list, and aggregates
082         * the result according to the evaluation context's current aggregation
083         * strategy.
084         *
085         * @param calc Compiled expression to evaluate a scalar
086         * @param evaluator Evaluation context
087         * @param tupleList List of members or tuples
088         * @return Aggregated result
089         */
090        public static Object aggregate(
091            Calc calc,
092            Evaluator evaluator,
093            TupleList tupleList)
094        {
095            Aggregator aggregator =
096                (Aggregator) evaluator.getProperty(
097                    Property.AGGREGATION_TYPE.name, null);
098            if (aggregator == null) {
099                throw newEvalException(
100                    null,
101                    "Could not find an aggregator in the current evaluation context");
102            }
103            Aggregator rollup = aggregator.getRollup();
104            if (rollup == null) {
105                throw newEvalException(
106                    null,
107                    "Don't know how to rollup aggregator '" + aggregator + "'");
108            }
109            if (aggregator != RolapAggregator.DistinctCount) {
110                final int savepoint = evaluator.savepoint();
111                try {
112                    evaluator.setNonEmpty(false);
113                    final Object o =
114                        rollup.aggregate(
115                            evaluator, tupleList, calc);
116                    return o;
117                } finally {
118                    evaluator.restore(savepoint);
119                }
120            }
121
122            // All that follows is logic for distinct count. It's not like the
123            // other aggregators.
124            if (tupleList.size() == 0) {
125                return DoubleNull;
126            }
127
128            // Optimize the list
129            // E.g.
130            // List consists of:
131            //  (Gender.[All Gender], [Product].[All Products]),
132            //  (Gender.[F], [Product].[Drink]),
133            //  (Gender.[M], [Product].[Food])
134            // Can be optimized to:
135            //  (Gender.[All Gender], [Product].[All Products])
136            //
137            // Similar optimization can also be done for list of members.
138
139            if (evaluator instanceof RolapEvaluator
140                && ((RolapEvaluator) evaluator).getDialect()
141                .supportsUnlimitedValueList())
142            {
143                // If the DBMS does not have an upper limit on IN list
144                // predicate size, then don't attempt any list
145                // optimization, since the current algorithm is
146                // very slow.  May want to revisit this if someone
147                // improves the algorithm.
148            } else {
149                tupleList = optimizeTupleList(evaluator, tupleList, true);
150            }
151
152            // Can't aggregate distinct-count values in the same way
153            // which is used for other types of aggregations. To evaluate a
154            // distinct-count across multiple members, we need to gather
155            // the members together, then evaluate the collection of
156            // members all at once. To do this, we postpone evaluation,
157            // and create a lambda function containing the members.
158            Evaluator evaluator2 =
159                evaluator.pushAggregation(tupleList);
160            // cancel nonEmpty context
161            evaluator2.setNonEmpty(false);
162            return evaluator2.evaluateCurrent();
163        }
164
165        /**
166         * Analyzes a list of tuples and determines if the list can
167         * be safely optimized. If a member of the tuple list is on
168         * a hierarchy for which a rollup policy of PARTIAL is set,
169         * it is not safe to optimize that list.
170         */
171        private static boolean canOptimize(
172            Evaluator evaluator,
173            TupleList tupleList)
174        {
175            // If members of this hierarchy are controlled by a role which
176            // enforces a rollup policy of partial, we cannot safely
177            // optimize the tuples list as it might end up rolling up to
178            // the parent while not all children are actually accessible.
179            for (List<Member> tupleMembers : tupleList) {
180                for (Member member : tupleMembers) {
181                    final RollupPolicy policy =
182                        evaluator.getSchemaReader().getRole()
183                            .getAccessDetails(member.getHierarchy())
184                                .getRollupPolicy();
185                    if (policy == RollupPolicy.PARTIAL) {
186                        return false;
187                    }
188                }
189            }
190            return true;
191        }
192
193        public static TupleList optimizeTupleList(
194            Evaluator evaluator, TupleList tupleList, boolean checkSize)
195        {
196            if (!canOptimize(evaluator, tupleList)) {
197                return tupleList;
198            }
199
200            // FIXME: We remove overlapping tuple entries only to pass
201            // AggregationOnDistinctCountMeasuresTest
202            // .testOptimizeListWithTuplesOfLength3 on Access. Without
203            // the optimization, we generate a statement 7000
204            // characters long and Access gives "Query is too complex".
205            // The optimization is expensive, so we only want to do it
206            // if the DBMS can't execute the query otherwise.
207            if (false) {
208                tupleList = removeOverlappingTupleEntries(tupleList);
209            }
210            tupleList =
211                optimizeChildren(
212                    tupleList,
213                    evaluator.getSchemaReader(),
214                    evaluator.getMeasureCube());
215            if (checkSize) {
216                checkIfAggregationSizeIsTooLarge(tupleList);
217            }
218            return tupleList;
219        }
220
221        /**
222         * In case of distinct count aggregation if a tuple which is a super
223         * set of other tuples in the set exists then the child tuples can be
224         * ignored.
225         *
226         * <p>For example. A list consisting of:
227         *  (Gender.[All Gender], [Product].[All Products]),
228         *  (Gender.[F], [Product].[Drink]),
229         *  (Gender.[M], [Product].[Food])
230         * Can be optimized to:
231         *  (Gender.[All Gender], [Product].[All Products])
232         *
233         * @param list List of tuples
234         */
235        public static TupleList removeOverlappingTupleEntries(
236            TupleList list)
237        {
238            TupleList trimmedList = list.cloneList(list.size());
239            Member[] tuple1 = new Member[list.getArity()];
240            Member[] tuple2 = new Member[list.getArity()];
241            final TupleCursor cursor1 = list.tupleCursor();
242            while (cursor1.forward()) {
243                cursor1.currentToArray(tuple1, 0);
244                if (trimmedList.isEmpty()) {
245                    trimmedList.addTuple(tuple1);
246                } else {
247                    boolean ignore = false;
248                    final TupleIterator iterator = trimmedList.tupleIterator();
249                    while (iterator.forward()) {
250                        iterator.currentToArray(tuple2, 0);
251                        if (isSuperSet(tuple1, tuple2)) {
252                            iterator.remove();
253                        } else if (isSuperSet(tuple2, tuple1)
254                            || isEqual(tuple1, tuple2))
255                        {
256                            ignore = true;
257                            break;
258                        }
259                    }
260                    if (!ignore) {
261                        trimmedList.addTuple(tuple1);
262                    }
263                }
264            }
265            return trimmedList;
266        }
267
268        /**
269         * Returns whether tuple1 is a superset of tuple2.
270         *
271         * @param tuple1 First tuple
272         * @param tuple2 Second tuple
273         * @return boolean Whether tuple1 is a superset of tuple2
274         */
275        public static boolean isSuperSet(Member[] tuple1, Member[] tuple2) {
276            int parentLevelCount = 0;
277            for (int i = 0; i < tuple1.length; i++) {
278                Member member1 = tuple1[i];
279                Member member2 = tuple2[i];
280
281                if (!member2.isChildOrEqualTo(member1)) {
282                    return false;
283                }
284                if (member1.getLevel().getDepth()
285                    < member2.getLevel().getDepth())
286                {
287                    parentLevelCount++;
288                }
289            }
290            return parentLevelCount > 0;
291        }
292
293        private static void checkIfAggregationSizeIsTooLarge(List list) {
294            final IntegerProperty property =
295                MondrianProperties.instance().MaxConstraints;
296            final int maxConstraints = property.get();
297            if (list.size() > maxConstraints) {
298                throw newEvalException(
299                    null,
300                    "Aggregation is not supported over a list"
301                    + " with more than " + maxConstraints + " predicates"
302                    + " (see property " + property.getPath() + ")");
303            }
304        }
305
306        public boolean dependsOn(Hierarchy hierarchy) {
307            if (hierarchy.getDimension().isMeasures()) {
308                return true;
309            }
310            return anyDependsButFirst(getCalcs(), hierarchy);
311        }
312
313        /**
314         * In distinct Count aggregation, if tuple list is a result
315         * m.children * n.children then it can be optimized to m * n
316         *
317         * <p>
318         * E.g.
319         * List consist of:
320         *  (Gender.[F], [Store].[USA]),
321         *  (Gender.[F], [Store].[USA].[OR]),
322         *  (Gender.[F], [Store].[USA].[CA]),
323         *  (Gender.[F], [Store].[USA].[WA]),
324         *  (Gender.[F], [Store].[CANADA])
325         *  (Gender.[M], [Store].[USA]),
326         *  (Gender.[M], [Store].[USA].[OR]),
327         *  (Gender.[M], [Store].[USA].[CA]),
328         *  (Gender.[M], [Store].[USA].[WA]),
329         *  (Gender.[M], [Store].[CANADA])
330         * Can be optimized to:
331         *  (Gender.[All Gender], [Store].[USA])
332         *  (Gender.[All Gender], [Store].[CANADA])
333         *
334         *
335         * @param tuples Tuples
336         * @param reader Schema reader
337         * @param baseCubeForMeasure Cube
338         * @return xxxx
339         */
340        public static TupleList optimizeChildren(
341            TupleList tuples,
342            SchemaReader reader,
343            Cube baseCubeForMeasure)
344        {
345            Map<Member, Integer>[] membersOccurencesInTuple =
346                membersVersusOccurencesInTuple(tuples);
347            int tupleLength = tuples.getArity();
348
349            //noinspection unchecked
350            Set<Member>[] sets = new Set[tupleLength];
351            boolean optimized = false;
352            for (int i = 0; i < tupleLength; i++) {
353                if (areOccurencesEqual(membersOccurencesInTuple[i].values())) {
354                    Set<Member> members = membersOccurencesInTuple[i].keySet();
355                    int originalSize = members.size();
356                    sets[i] =
357                        optimizeMemberSet(
358                            new LinkedHashSet<Member>(members),
359                            reader,
360                            baseCubeForMeasure);
361                    if (sets[i].size() != originalSize) {
362                        optimized = true;
363                    }
364                } else {
365                    sets[i] =
366                        new LinkedHashSet<Member>(
367                            membersOccurencesInTuple[i].keySet());
368                }
369            }
370            if (optimized) {
371                return crossProd(sets);
372            }
373            return tuples;
374        }
375
376        /**
377         * Finds member occurrences in tuple and generates a map of Members
378         * versus their occurrences in tuples.
379         *
380         * @param tupleList List of tuples
381         * @return Map of the number of occurrences of each member in a tuple
382         */
383        public static Map<Member, Integer>[] membersVersusOccurencesInTuple(
384            TupleList tupleList)
385        {
386            int tupleLength = tupleList.getArity();
387            //noinspection unchecked
388            Map<Member, Integer>[] counters = new Map[tupleLength];
389            for (int i = 0; i < counters.length; i++) {
390                counters[i] = new LinkedHashMap<Member, Integer>();
391            }
392            for (List<Member> tuple : tupleList) {
393                for (int i = 0; i < tuple.size(); i++) {
394                    Member member = tuple.get(i);
395                    Map<Member, Integer> map = counters[i];
396                    if (map.containsKey(member)) {
397                        Integer count = map.get(member);
398                        map.put(member, ++count);
399                    } else {
400                        map.put(member, 1);
401                    }
402                }
403            }
404            return counters;
405        }
406
407        private static Set<Member> optimizeMemberSet(
408            Set<Member> members,
409            SchemaReader reader,
410            Cube baseCubeForMeasure)
411        {
412            boolean didOptimize;
413            Set<Member> membersToBeOptimized = new LinkedHashSet<Member>();
414            Set<Member> optimizedMembers = new LinkedHashSet<Member>();
415            while (members.size() > 0) {
416                Iterator<Member> iterator = members.iterator();
417                Member first = iterator.next();
418                if (first.isAll()) {
419                    optimizedMembers.clear();
420                    optimizedMembers.add(first);
421                    return optimizedMembers;
422                }
423                membersToBeOptimized.add(first);
424                iterator.remove();
425
426                Member firstParentMember = first.getParentMember();
427                while (iterator.hasNext()) {
428                    Member current =  iterator.next();
429                    if (current.isAll()) {
430                        optimizedMembers.clear();
431                        optimizedMembers.add(current);
432                        return optimizedMembers;
433                    }
434
435                    Member currentParentMember = current.getParentMember();
436                    if (firstParentMember == null
437                        && currentParentMember == null
438                        || (firstParentMember != null
439                        && firstParentMember.equals(currentParentMember)))
440                    {
441                        membersToBeOptimized.add(current);
442                        iterator.remove();
443                    }
444                }
445
446                int childCountOfParent = -1;
447                if (firstParentMember != null) {
448                    childCountOfParent =
449                        getChildCount(firstParentMember, reader);
450                }
451                if (childCountOfParent != -1
452                    && membersToBeOptimized.size() == childCountOfParent
453                    && canOptimize(firstParentMember, baseCubeForMeasure))
454                {
455                    optimizedMembers.add(firstParentMember);
456                    didOptimize = true;
457                } else {
458                    optimizedMembers.addAll(membersToBeOptimized);
459                    didOptimize = false;
460                }
461                membersToBeOptimized.clear();
462
463                if (members.size() == 0 && didOptimize) {
464                    Set temp = members;
465                    members = optimizedMembers;
466                    optimizedMembers = temp;
467                }
468            }
469            return optimizedMembers;
470        }
471
472        /**
473         * Returns whether tuples are equal. They must have the same length.
474         *
475         * @param tuple1 First tuple
476         * @param tuple2 Second tuple
477         * @return whether tuples are equal
478         */
479        private static boolean isEqual(Member[] tuple1, Member[] tuple2) {
480            for (int i = 0; i < tuple1.length; i++) {
481                if (!tuple1[i].getUniqueName().equals(
482                        tuple2[i].getUniqueName()))
483                {
484                    return false;
485                }
486            }
487            return true;
488        }
489
490        private static boolean canOptimize(
491            Member parentMember,
492            Cube baseCube)
493        {
494            return dimensionJoinsToBaseCube(
495                parentMember.getDimension(), baseCube)
496                || !parentMember.isAll();
497        }
498
499        private static TupleList crossProd(Set<Member>[] sets) {
500            final List<TupleList> tupleLists = new ArrayList<TupleList>();
501            for (Set<Member> set : sets) {
502                tupleLists.add(
503                    new UnaryTupleList(
504                        new ArrayList<Member>(set)));
505            }
506            if (tupleLists.size() == 1) {
507                return tupleLists.get(0);
508            }
509            return CrossJoinFunDef.mutableCrossJoin(tupleLists);
510        }
511
512        private static boolean dimensionJoinsToBaseCube(
513            Dimension dimension,
514            Cube baseCube)
515        {
516            HashSet<Dimension> dimensions = new HashSet<Dimension>();
517            dimensions.add(dimension);
518            return baseCube.nonJoiningDimensions(dimensions).size() == 0;
519        }
520
521        private static int getChildCount(
522            Member parentMember,
523            SchemaReader reader)
524        {
525            int childrenCountFromCache =
526                reader.getChildrenCountFromCache(parentMember);
527            if (childrenCountFromCache != -1) {
528                return childrenCountFromCache;
529            }
530            return reader.getMemberChildren(parentMember).size();
531        }
532    }
533}
534
535// End AggregateFunDef.java