001: /*
002: * $Id: GroupedRowIterator.java,v 1.23 2005/12/20 18:32:41 ahimanikya Exp $
003: * =======================================================================
004: * Copyright (c) 2003-2005 Axion Development Team. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * 1. Redistributions of source code must retain the above
011: * copyright notice, this list of conditions and the following
012: * disclaimer.
013: *
014: * 2. Redistributions in binary form must reproduce the above copyright
015: * notice, this list of conditions and the following disclaimer in
016: * the documentation and/or other materials provided with the
017: * distribution.
018: *
019: * 3. The names "Tigris", "Axion", nor the names of its contributors may
020: * not be used to endorse or promote products derived from this
021: * software without specific prior written permission.
022: *
023: * 4. Products derived from this software may not be called "Axion", nor
024: * may "Tigris" or "Axion" appear in their names without specific prior
025: * written permission.
026: *
027: * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
028: * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
029: * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
030: * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
031: * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
032: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
033: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
034: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
035: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
036: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
037: * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
038: * =======================================================================
039: */
040:
041: package org.axiondb.engine.rowiterators;
042:
043: import java.util.ArrayList;
044: import java.util.Collections;
045: import java.util.HashMap;
046: import java.util.Iterator;
047: import java.util.List;
048: import java.util.Map;
049: import java.util.SortedMap;
050: import java.util.TreeMap;
051:
052: import org.axiondb.AxionException;
053: import org.axiondb.Literal;
054: import org.axiondb.OrderNode;
055: import org.axiondb.Row;
056: import org.axiondb.RowComparator;
057: import org.axiondb.RowDecorator;
058: import org.axiondb.RowIterator;
059: import org.axiondb.Selectable;
060: import org.axiondb.engine.rows.SimpleRow;
061: import org.axiondb.engine.visitors.FindAggregateFunctionVisitor;
062: import org.axiondb.functions.AggregateFunction;
063: import org.axiondb.functions.ConcreteFunction;
064: import org.axiondb.util.ComparatorChain;
065:
066: /**
067: * Processes a "raw" iterator to implement GROUP BY functionality.
068: *
069: * @version $Revision: 1.23 $ $Date: 2005/12/20 18:32:41 $
070: * @author Rahul Dwivedi
071: * @author Rod Waldhoff
072: * @author Ahimanikya Satapathy
073: * @author Girish Patil
074: * @author Jonathan Giron
075: */
076: public class GroupedRowIterator extends DelegatingRowIterator {
077:
078: public GroupedRowIterator(boolean sort, RowIterator rows,
079: Map fieldMap, List groupBy, List selected,
080: Selectable having, Selectable where, List orderBy)
081: throws AxionException {
082: super (null);
083:
084: _colIdToFieldMap = fieldMap;
085: _groupByCols = groupBy;
086: _selected = selected;
087: _having = having;
088: _where = where;
089: _orderByNodes = orderBy;
090: _aggrFnValueCache = new HashMap(_selected.size());
091:
092: SortedMap groupedRowMap = null;
093: // If rows are not sorted then we need to sort them
094: if (!isEmptyGroupBy() && sort) {
095: groupedRowMap = doSort(rows);
096: }
097:
098: // Determine in advance whether elements of Selectable list is an aggregate
099: // function, so that we don't have to determines while making row for each group.
100: // Keep the last element of the array reserved for having clause.
101: _isAggregateFunction = new boolean[_selected.size() + 1];
102: for (int i = 0, I = _selected.size(); i < I; i++) {
103: _isAggregateFunction[i] = isAggregateFunction(_selected
104: .get(i));
105: }
106: _isAggregateFunction[_selected.size()] = isAggregateFunction(_having);
107:
108: List grList = null;
109: if (groupedRowMap == null) {
110: grList = makeGroupRows(rows);
111: } else {
112: grList = makeGroupRows(groupedRowMap);
113: }
114: setDelegate(new ListRowIterator(grList));
115: }
116:
117: public GroupedRowIterator(RowIterator rows, Map fieldMap,
118: List groupBy, List selected, Selectable having, List orderBy)
119: throws AxionException {
120: this (true, rows, fieldMap, groupBy, selected, having, null,
121: orderBy);
122: }
123:
124: /** Not supported in the base implementation. */
125: public void add(Row row) throws AxionException {
126: throw new UnsupportedOperationException();
127: }
128:
129: /** Not supported in the base implementation. */
130: public void set(Row row) throws AxionException {
131: throw new UnsupportedOperationException();
132: }
133:
134: /** Not supported in the base implementation. */
135: public void remove() throws AxionException {
136: throw new UnsupportedOperationException();
137: }
138:
139: public String toString() {
140: StringBuffer buf = new StringBuffer(20);
141: buf.append("Grouped(").append(
142: _groupByCols == null ? "" : _groupByCols.toString());
143: if (_having != null) {
144: buf.append("; having=").append(_having).append(";");
145: }
146: buf.append("preSorted=").append(_preSorted).append(")");
147: return buf.toString();
148: }
149:
150: // Returns true if the HAVING node evaluates to true
151: private boolean acceptable(RowIterator currGroupRowIter,
152: RowDecorator dec) throws AxionException {
153: if (_having == null) {
154: return true;
155: }
156:
157: if (_isAggregateFunction[_selected.size()]) {
158: Object val = evaluateAggregateFunction(dec,
159: (ConcreteFunction) _having, currGroupRowIter);
160: return ((Boolean) val).booleanValue();
161: }
162:
163: // ISO/IEC 9075-2:2003, Section 7.10, General Rule 1 - clause is applied if having condition
164: // evaluates to true; null evaluation thus maps to false.
165: Boolean result = (Boolean) _having.evaluate(dec);
166: return (result == null) ? false : result.booleanValue();
167: }
168:
169: private void addToCurrentGroup(RowDecorator dec, Row row,
170: List currGroup) throws AxionException {
171: if (_where == null) {
172: currGroup.add(row);
173: return;
174: }
175:
176: // Else add to current group if WHERE node is null or evaluates to true
177: dec.setRow(row);
178:
179: Boolean result = (Boolean) _where.evaluate(dec);
180: if (result != null && result.booleanValue()) {
181: currGroup.add(row);
182: }
183: }
184:
185: // Collect rows for each group, groups will be maintained in natual sort order.
186: private SortedMap doSort(RowIterator rows) throws AxionException {
187: ComparatorChain sortChain = generateOrderChain();
188: SortedMap groupedRows = new TreeMap(sortChain);
189: RowDecorator dec = new RowDecorator(_colIdToFieldMap);
190: while (rows.hasNext()) {
191: Row row = rows.next();
192: List currGroup = (List) groupedRows.get(row);
193: if (currGroup == null) {
194: currGroup = new ArrayList();
195: groupedRows.put(row, currGroup);
196: }
197: addToCurrentGroup(dec, row, currGroup);
198: }
199: _preSorted = false;
200: return groupedRows;
201: }
202:
203: private Object evaluateAggregateFunction(RowDecorator dec,
204: ConcreteFunction fn, RowIterator rows)
205: throws AxionException {
206: if (fn instanceof AggregateFunction) {
207: rows.reset();
208: AggregateFunction vfn = (AggregateFunction) fn;
209: Object val = _aggrFnValueCache.get(vfn);
210: if (val == null) {
211: val = vfn.evaluate(new RowIteratorRowDecoratorIterator(
212: rows, dec));
213: _aggrFnValueCache.put(vfn, val);
214: }
215: return val;
216: } else {
217: // Aggregate function might have been nested with another aggregate or scalar
218: // function
219: List fnArgs = new ArrayList(fn.getArgumentCount());
220: for (int i = 0, I = fn.getArgumentCount(); i < I; i++) {
221: Object arg = fn.getArgument(i);
222: fnArgs.add(i, arg); // Keep original selectables
223: if (arg instanceof ConcreteFunction) {
224: ConcreteFunction innerFn = (ConcreteFunction) arg;
225: Object val = evaluateAggregateFunction(dec,
226: innerFn, rows);
227: fn.setArgument(i, new Literal(val,
228: ((ConcreteFunction) arg).getDataType()));
229: }
230: }
231:
232: if (dec.getRow() == null) {
233: dec.setRow(rows.first());
234: }
235: Object val = fn.evaluate(dec);
236: for (int i = 0, I = fn.getArgumentCount(); i < I; i++) {
237: fn.setArgument(i, (Selectable) fnArgs.get(i)); // Reset func argument
238: }
239: return val;
240: }
241: }
242:
243: private ComparatorChain generateOrderChain() {
244: ComparatorChain chain = new ComparatorChain();
245: for (int i = 0, I = _groupByCols.size(); i < I; i++) {
246: Selectable sel = (Selectable) _groupByCols.get(i);
247: if (isDescending(sel, _orderByNodes)) {
248: chain.setReverseSort(i);
249: }
250: chain.addComparator(new RowComparator(sel,
251: new RowDecorator(_colIdToFieldMap)));
252: }
253: return chain;
254: }
255:
256: private boolean isAggregateFunction(Object sel) {
257: if (sel instanceof ConcreteFunction) {
258: FindAggregateFunctionVisitor findAggr = new FindAggregateFunctionVisitor();
259: findAggr.visit((Selectable) sel); // Check for aggregate functions
260: if (findAggr.foundAggregateFunction()) {
261: return true;
262: }
263: }
264: return false;
265: }
266:
267: private boolean isDescending(Selectable sel, List orderNodes) {
268: if (null != orderNodes && null != sel) {
269: for (Iterator iter = orderNodes.iterator(); iter.hasNext();) {
270: OrderNode node = (OrderNode) (iter.next());
271: if (node.getSelectable().equals(sel)) {
272: return node.isDescending();
273: }
274: }
275: }
276: return false;
277: }
278:
279: private boolean isEmptyGroupBy() {
280: return (_groupByCols == null || _groupByCols.isEmpty());
281: }
282:
283: private Row makeGroupRow(List currGroup, RowDecorator dec, Row row)
284: throws AxionException {
285: List myCurrGroup = new ArrayList(currGroup);
286: RowIterator currGroupRowIter = new ListRowIterator(myCurrGroup);
287:
288: dec.setRow(row);
289: _aggrFnValueCache.clear();
290: if (acceptable(currGroupRowIter, dec)) {
291: return makeGroupRow(currGroupRowIter, dec);
292: }
293: return null;
294: }
295:
296: private Row makeGroupRow(RowIterator currGroupRowIter,
297: RowDecorator dec) throws AxionException {
298: SimpleRow rowOut = new SimpleRow(_selected.size());
299: for (int i = 0, I = _selected.size(); i < I; i++) {
300: if (_isAggregateFunction[i]) {
301: rowOut.set(i, evaluateAggregateFunction(dec,
302: (ConcreteFunction) _selected.get(i),
303: currGroupRowIter));
304: } else {
305: rowOut.set(i, ((Selectable) _selected.get(i))
306: .evaluate(dec));
307: }
308: }
309: return rowOut;
310: }
311:
312: // This assumes rows are sorted.
313: private List makeGroupRows(RowIterator rows) throws AxionException {
314: if (_groupByCols != null && !_groupByCols.isEmpty()
315: && !rows.hasNext()) {
316: return Collections.EMPTY_LIST;
317: }
318:
319: List comparators = new ArrayList();
320: if (_groupByCols != null && !_groupByCols.isEmpty()) {
321: RowDecorator dec = new RowDecorator(_colIdToFieldMap);
322: for (int i = 0, I = _groupByCols.size(); i < I; i++) {
323: comparators.add(new RowComparator(
324: (Selectable) _groupByCols.get(i), dec));
325: }
326: }
327:
328: List groupedRows = new ArrayList();
329: ArrayList currGroup = new ArrayList();
330: RowDecorator dec = new RowDecorator(_colIdToFieldMap);
331:
332: Row lastRow = null;
333: if (rows.hasNext() && !comparators.isEmpty()) {
334: lastRow = rows.next();
335: addToCurrentGroup(dec, lastRow, currGroup);
336: while (rows.hasNext()) {
337: Row row = rows.next();
338: for (int i = 0, I = comparators.size(); i < I
339: && !currGroup.isEmpty(); i++) {
340: RowComparator comp = (RowComparator) comparators
341: .get(i);
342:
343: // Once we have a group we can apply group by aggregate function
344: if (comp.compare(lastRow, row) != 0) {
345: Row groupdRow = makeGroupRow(currGroup, dec,
346: lastRow);
347: if (groupdRow != null) {
348: groupedRows.add(groupdRow);
349: }
350: currGroup.clear();
351: break;
352: }
353: }
354: addToCurrentGroup(dec, row, currGroup);
355: lastRow = row;
356: }
357: // Make group row if any pending group exists.
358: Row groupdRow = makeGroupRow(currGroup, dec, lastRow);
359: if (groupdRow != null) {
360: groupedRows.add(groupdRow);
361: }
362: } else {
363: groupedRows.add(makeGroupRow(rows, dec));
364: }
365:
366: return groupedRows;
367: }
368:
369: private List makeGroupRows(SortedMap groupedRowMap)
370: throws AxionException {
371: if (_groupByCols != null && groupedRowMap.isEmpty()) {
372: return Collections.EMPTY_LIST;
373: }
374:
375: List groupedRows = new ArrayList();
376: List currGroup = new ArrayList();
377: RowDecorator dec = new RowDecorator(_colIdToFieldMap);
378:
379: Iterator iter = groupedRowMap.values().iterator();
380: while (iter.hasNext()) {
381: currGroup = (List) iter.next();
382: Row groupdRow = makeGroupRow(currGroup, dec,
383: (Row) currGroup.get(0));
384: if (groupdRow != null) {
385: groupedRows.add(groupdRow);
386: }
387: }
388: return groupedRows;
389: }
390:
391: private Map _aggrFnValueCache;
392: private Map _colIdToFieldMap;
393: private List _groupByCols;
394: private Selectable _having;
395: private boolean[] _isAggregateFunction;
396: private List _orderByNodes;
397: private List _selected;
398: private Selectable _where;
399: private boolean _preSorted = true;
400: }
|