001: /**
002: * Copyright (C) 2006 NetMind Consulting Bt.
003: *
004: * This library is free software; you can redistribute it and/or
005: * modify it under the terms of the GNU Lesser General Public
006: * License as published by the Free Software Foundation; either
007: * version 3 of the License, or (at your option) any later version.
008: *
009: * This library is distributed in the hope that it will be useful,
010: * but WITHOUT ANY WARRANTY; without even the implied warranty of
011: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
012: * Lesser General Public License for more details.
013: *
014: * You should have received a copy of the GNU Lesser General Public
015: * License along with this library; if not, write to the Free Software
016: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
017: */package hu.netmind.persistence;
018:
019: import hu.netmind.persistence.parser.*;
020: import java.util.*;
021: import org.apache.log4j.Logger;
022:
023: /**
024: * This list is a lazy-loading list. It receives a query statement, and
025: * if an item is queried, the list runs the approriate search statement
026: * and loads the referred item (and a given neighbourhood).
027: * @author Brautigam Robert
028: * @version Revision: $Revision$
029: */
030: public class LazyList extends AbstractList {
031: private static Logger logger = Logger.getLogger(LazyList.class);
032: public static int BATCH_SIZE = 30;
033: public static int BATCH_SIZE_LINEARMULTIPLIER = 3;
034: public static int BATCH_SIZE_MAX = 2500;
035: public static int MAX_JOINS = 16;
036:
037: private StoreContext context;
038: private Map unmarshalledObjects;
039: private QueryStatementList stmts;
040: private LazyListHooks hooks;
041:
042: private List list;
043: private boolean hasNext = false;
044: private long[] stmtOffsets;
045: private int offset = 0;
046: private boolean initialized;
047: private int linearCount = 0;
048: private int linearLastIndex = -1;
049:
050: LazyList(StoreContext context, QueryStatementList stmts,
051: Map unmarshalledObjects) {
052: this .context = context;
053: this .stmts = stmts;
054: this .unmarshalledObjects = unmarshalledObjects;
055: this .initialized = false;
056: list = null;
057: }
058:
059: StoreContext getContext() {
060: return context;
061: }
062:
063: List getStmts() {
064: return stmts;
065: }
066:
067: /**
068: * Get the object on the given.
069: */
070: public Object get(int index) {
071: initialize();
072: updateList(index);
073: return list.get(index - offset);
074: }
075:
076: /**
077: * Calculate the offset of a given statement.
078: */
079: public long getStmtOffset(int index) {
080: // Initialize
081: if (stmtOffsets == null) {
082: stmtOffsets = new long[stmts.size() + 1];
083: stmtOffsets[0] = 0;
084: for (int i = 0; i < stmts.size(); i++)
085: stmtOffsets[i + 1] = -1;
086: }
087: // Calculate
088: if (logger.isDebugEnabled())
089: logger.debug("calculating size for stmt index: " + index
090: + "/" + stmts.size());
091: if (stmtOffsets[index] < 0) {
092: for (int i = 0; i < index; i++) {
093: if (stmtOffsets[i + 1] >= 0)
094: continue;
095: SearchResult result = context.getStore().find(
096: (QueryStatement) stmts.get(i),
097: new Limits(0, 0, -1), null);
098: stmtOffsets[i + 1] = stmtOffsets[i]
099: + result.getResultSize();
100: }
101: }
102: // Return
103: logger.debug("returning size: " + stmtOffsets[index]);
104: return stmtOffsets[index];
105: }
106:
107: /**
108: * Get the predicted size from database. This value <strong>never</strong
109: * changes.
110: */
111: public int size() {
112: initialize();
113: return (int) getStmtOffset(stmts.size());
114: }
115:
116: void refresh() {
117: list = null;
118: stmtOffsets = null;
119: offset = 0;
120: linearLastIndex = -1;
121: linearCount = 0;
122: hasNext = false;
123: }
124:
125: /**
126: * Try to load the entries around the given index.
127: */
128: private void updateList(int index) {
129: // Initialize lazy list
130: initialize();
131: // Keep track of linear iterations
132: if (index == linearLastIndex + 1)
133: linearCount++;
134: else
135: linearCount = 0;
136: linearLastIndex = index;
137: // Check bounds
138: if (index < 0)
139: throw new ArrayIndexOutOfBoundsException(
140: "lazy list index given was: " + index
141: + ", thats < 0 and illegal.");
142: if ((list != null) && (index < offset + list.size())
143: && (index >= offset))
144: return; // List has the desired item
145: // Determine whether the update will get the next page linearly
146: boolean nextPage = false;
147: if (list != null)
148: nextPage = (index == offset + list.size());
149: // Determine the startindex and size of the current select
150: int batchSize = BATCH_SIZE;
151: if (list != null)
152: batchSize = list.size();
153: if (linearCount >= batchSize)
154: batchSize = batchSize * BATCH_SIZE_LINEARMULTIPLIER;
155: else
156: batchSize = BATCH_SIZE;
157: if (batchSize > BATCH_SIZE_MAX)
158: batchSize = BATCH_SIZE_MAX;
159: int startIndex = 0;
160: if (index < offset)
161: startIndex = (index / batchSize) * batchSize;
162: else
163: startIndex = index;
164: if (startIndex < 0)
165: startIndex = 0;
166: if (logger.isDebugEnabled())
167: logger.debug("list index: " + index + ", startindex: "
168: + startIndex + ", batchsize: " + batchSize
169: + ", linearcount was: " + linearCount);
170: linearCount = 0;
171: linearLastIndex = index;
172: // Determine the statement to use for given index
173: HashMap session = new HashMap();
174: getStmtOffset(0); // Initialize offsets
175: int stmtIndex = 0;
176: long realOffset = 0;
177: if (hooks != null)
178: stmtIndex = hooks.preIndexing(session, startIndex);
179: if (stmtIndex < 0) {
180: stmtIndex = 0;
181: while ((stmtIndex < stmts.size())
182: && (stmtOffsets[stmtIndex] >= 0)
183: && (stmtOffsets[stmtIndex + 1] >= 0)
184: && (stmtOffsets[stmtIndex + 1] <= startIndex)) {
185: realOffset = stmtOffsets[stmtIndex];
186: stmtIndex++;
187: }
188: }
189: if (stmtIndex >= stmts.size())
190: throw new ArrayIndexOutOfBoundsException(
191: "Tried to reach index: " + index
192: + ", but that was not available.");
193: if (logger.isDebugEnabled())
194: logger.debug("asked index is: " + index + ", real offset: "
195: + realOffset + ", stmt index: " + stmtIndex
196: + ", start index: " + startIndex);
197: // Now load the result set, which is possibly distributed in multiple
198: // queries.
199: offset = startIndex;
200: List previousList = new Vector();
201: if (nextPage)
202: previousList = new Vector(list);
203: list = new Vector(batchSize);
204: // Load the already unmarshalled objects. Load until
205: // list vector is full, or out of result entries. Note: we load
206: // plus one entry, so we know, that there is a next entry.
207: boolean override = false;
208: while ((stmtIndex < stmts.size())
209: && ((list.size() < batchSize) || (override))) {
210: if (logger.isDebugEnabled())
211: logger.debug("lazy list statement iteration: "
212: + stmtIndex + ", size: " + stmts.size());
213: override = false;
214: // Get the query, and optimize it
215: QueryStatement stmt = (QueryStatement) stmts.get(stmtIndex);
216: Limits limits = new Limits(
217: (int) (startIndex - stmtOffsets[stmtIndex]),
218: batchSize + 1 - list.size(), 0);
219: if (limits.getOffset() < 0)
220: limits.setOffset(0);
221: if (stmt.getAllLeftTableTerms().size() > MAX_JOINS) {
222: // Modify limits, so it does not select more rows than left
223: // table terms. This ensures, that the select will not contain
224: // more left table terms.
225: if (limits.getLimit() > MAX_JOINS) {
226: limits.setLimit(MAX_JOINS + 1);
227: batchSize = list.size() + MAX_JOINS;
228: }
229: // If there are many left table terms, then optimize this select
230: // locally. This means, eliminate all left table terms, which will
231: // not be used.
232: stmt = optimizeLocalStatement(stmt, limits);
233: }
234: // Make query
235: if (hooks != null)
236: stmt = hooks.preSelect(session, stmt, previousList,
237: limits, new Limits(offset, batchSize + 1, 0));
238: SearchResult result = context.getStore().find(stmt, limits,
239: unmarshalledObjects);
240: // Set for next iteration
241: startIndex += result.getResult().size();
242: list.addAll(result.getResult());
243: if (hooks != null)
244: override = hooks.postSelect(session, list, new Limits(
245: offset, batchSize + 1, 0));
246: // Postoperation adjustments
247: if (list.size() > batchSize) {
248: // This means, that the list contained enough items for
249: // the query, which means return only the exact results.
250: // This size can not be determined now.
251: list = list.subList(0, batchSize);
252: hasNext = true;
253: } else {
254: hasNext = false;
255: // Compute statement length if the length is not yet known
256: if (stmtOffsets[stmtIndex + 1] < 0) {
257: if (list.size() == 0) {
258: // There is no result. This can be caused by two things:
259: // - This statement is really 0 length
260: // - Statement interval ends before this start index is reached,
261: // but may contain items.
262: // Let's just calculate the sizes up until now
263: getStmtOffset(stmtIndex + 1);
264: } else if (list.size() <= batchSize) {
265: // This means, that the list does not contain enough items,
266: // so the size can be exactly determined.
267: stmtOffsets[stmtIndex + 1] = startIndex;
268: }
269: }
270: }
271: // Decrease cycle invariant function (in english: increase index)
272: stmtIndex++;
273: }
274: if (logger.isDebugEnabled())
275: logger.debug("updated list, size is: " + list.size()
276: + ", index was: " + index);
277: }
278:
279: private void initialize() {
280: if (initialized)
281: return;
282: initialized = true;
283: // If not yet queried, and the number of statements is big,
284: // then do a pre-select, to determine which statements will be
285: // used anyway, and drop those statements, which will have no
286: // results.
287: if (stmts.size() > 2)
288: optimizeStatements();
289: }
290:
291: private Set getUsedTables(SearchResult result) {
292: HashSet usedTableNames = new HashSet();
293: for (int i = 0; i < result.getResult().size(); i++) {
294: String tableName = (String) ((Map) result.getResult()
295: .get(i)).get("object_table");
296: ClassEntry entry = context.getClassTracker()
297: .getTableClassInfo(tableName).getSourceEntry();
298: if (logger.isDebugEnabled())
299: logger
300: .debug("lazy list optimalization detected class in list: "
301: + entry);
302: while ((entry != null) && (entry.isStorable())) {
303: // Insert it's table name into the set
304: String usedTableName = context.getClassTracker()
305: .getClassInfo(entry).getTableName(entry);
306: usedTableNames.add(usedTableName);
307: // Goto super
308: entry = entry.getSuperEntry();
309: }
310: }
311: return usedTableNames;
312: }
313:
314: private QueryStatement optimizeLocalStatement(QueryStatement stmt,
315: Limits limits) {
316: logger.debug("executing local optimization");
317: if (stmt.getMode() != QueryStatement.MODE_FIND)
318: return stmt;
319: // First, copy the statement, so it won't affect later use
320: QueryStatement copyStmt = stmt.deepCopy();
321: // Then modify the statement to select only the tables the statement
322: // reaches with the given limits. (So remove all left terms for now)
323: copyStmt.setMode(QueryStatement.MODE_VIEW);
324: TableTerm selectTerm = (TableTerm) copyStmt.getSelectTerms()
325: .get(0);
326: logger.debug("local optimization detects "
327: + selectTerm.getLeftTableTerms().size()
328: + " left table terms.");
329: for (int i = 0; i < selectTerm.getLeftTableTerms().size(); i++) {
330: TableTerm leftTerm = (TableTerm) selectTerm
331: .getLeftTableTerms().get(i);
332: copyStmt.removeLeftTableTerm(leftTerm);
333: }
334: selectTerm.getLeftTableTerms().clear();
335: selectTerm.getLeftTableTerms().add(
336: new TableTerm("persistence_object_ids", null));
337: copyStmt.setStaticRepresentation(copyStmt
338: .getStaticRepresentation()
339: + "LazyModifiedForTableSet");
340: // Execute query
341: SearchResult result = context.getStore().find(copyStmt, limits,
342: null);
343: // Get all the tables this query will reach
344: Set usedTableNames = getUsedTables(result);
345: // Remove all left table terms from the original statement which are
346: // not used.
347: copyStmt = stmt.deepCopy();
348: selectTerm = (TableTerm) copyStmt.getSelectTerms().get(0);
349: Iterator leftTermIterator = selectTerm.getLeftTableTerms()
350: .iterator();
351: while (leftTermIterator.hasNext()) {
352: TableTerm leftTerm = (TableTerm) leftTermIterator.next();
353: if (!usedTableNames.contains(leftTerm.getTableName())) {
354: leftTermIterator.remove();
355: copyStmt.removeLeftTableTerm(leftTerm);
356: }
357: }
358: copyStmt.setStaticRepresentation(null);
359: return copyStmt;
360: }
361:
362: private void optimizeStatements() {
363: logger.debug("executing optimizing statement");
364: // First, select all classes which can be selected with the
365: // given statement. To do this, we modify the 'all ids' statement:
366: // - to select only tablenames
367: // - do not order by anything
368: QueryStatement allIds = stmts.getAllIdsStatement();
369: if (allIds.getMode() != QueryStatement.MODE_FIND)
370: return;
371: TableTerm selectTerm = (TableTerm) allIds.getSelectTerms().get(
372: 0);
373: allIds.setSelectTerms(new Vector());
374: allIds.getSelectTerms().add(
375: new ReferenceTerm(selectTerm, "object_table"));
376: allIds.setOrderByList(null);
377: allIds.setMode(QueryStatement.MODE_VIEW);
378: allIds.setStaticRepresentation(allIds.getStaticRepresentation()
379: + "LazyModifiedForTableSet");
380: // Execute statement
381: SearchResult result = context.getStore().find(allIds, null,
382: null);
383: // Now assemble each and every table name that will be used by the
384: // main selects. These are not only those returned by previous select,
385: // but all 'supertables' of them also.
386: Set usedTableNames = getUsedTables(result);
387: if (logger.isDebugEnabled())
388: logger.debug("determined, that used tables are: "
389: + usedTableNames);
390: // Now go through all statements, and determine whether they will be
391: // used or not. If a statement has a main select term which is not
392: // used, then delete the whole statement. Check the left terms too,
393: // and remove all non-used left terms.
394: Iterator stmtIterator = stmts.iterator();
395: while (stmtIterator.hasNext()) {
396: QueryStatement stmt = (QueryStatement) stmtIterator.next();
397: // Check main term
398: TableTerm mainTerm = (TableTerm) stmt.getSelectTerms().get(
399: 0);
400: if (!usedTableNames.contains(mainTerm.getTableName())) {
401: // Main term is not used, so remove
402: stmtIterator.remove();
403: if (logger.isDebugEnabled())
404: logger.debug("removing statement with main term: "
405: + mainTerm);
406: } else {
407: // Main term is used, but check it's left terms
408: Iterator leftTermIterator = mainTerm
409: .getLeftTableTerms().iterator();
410: while (leftTermIterator.hasNext()) {
411: TableTerm leftTerm = (TableTerm) leftTermIterator
412: .next();
413: if (!usedTableNames.contains(leftTerm
414: .getTableName())) {
415: // Left term will not be used ever, so remove it, but
416: // don't forget the expressions for this left term.
417: leftTermIterator.remove();
418: stmt.removeLeftTableTerm(leftTerm);
419: if (logger.isDebugEnabled())
420: logger
421: .debug("removing left table '"
422: + leftTerm
423: + "' from statement with main term: "
424: + mainTerm);
425: }
426: }
427: }
428: }
429: }
430:
431: public Iterator iterator() {
432: return listIterator();
433: }
434:
435: public ListIterator listIterator() {
436: return new LazyListIterator();
437: }
438:
439: public String toString() {
440: return super .toString();
441: }
442:
443: /**
444: * This internal iterator avoids using size() method for
445: * optimized iteration.
446: */
447: public class LazyListIterator implements ListIterator {
448: public int currentIndex = 0;
449: public boolean currentHasNext = false;
450:
451: public LazyListIterator() {
452: // Pre-read if there is a first item
453: currentIndex = 0;
454: if (list == null) {
455: try {
456: get(currentIndex);
457: currentHasNext = true;
458: } catch (ArrayIndexOutOfBoundsException e) {
459: currentHasNext = false;
460: }
461: } else {
462: currentHasNext = offset + list.size() > 0;
463: }
464: }
465:
466: public void add(Object o) {
467: throw new UnsupportedOperationException(
468: "LazyList does not support addition.");
469: }
470:
471: public boolean hasNext() {
472: return currentHasNext;
473: }
474:
475: public boolean hasPrevious() {
476: return currentIndex > 0; // All items have previous except first
477: }
478:
479: public Object next() {
480: Object result = get(currentIndex);
481: currentIndex++;
482: if (currentIndex < offset + list.size())
483: currentHasNext = true;
484: else
485: currentHasNext = hasNext;
486: return result;
487: }
488:
489: public int nextIndex() {
490: return currentIndex;
491: }
492:
493: public Object previous() {
494: Object result = get(currentIndex - 1);
495: currentIndex--;
496: currentHasNext = true;
497: return result;
498: }
499:
500: public int previousIndex() {
501: return currentIndex - 1;
502: }
503:
504: public void remove() {
505: throw new UnsupportedOperationException(
506: "LazyList does not support remove.");
507: }
508:
509: public void set(Object o) {
510: throw new UnsupportedOperationException(
511: "LazyList does not support set.");
512: }
513: }
514:
515: public LazyListHooks getHooks() {
516: return hooks;
517: }
518:
519: public void setHooks(LazyListHooks hooks) {
520: this .hooks = hooks;
521: }
522:
523: static {
524: try {
525: ResourceBundle config = ResourceBundle
526: .getBundle("beankeeper");
527: BATCH_SIZE = Integer.valueOf(
528: config.getString("list.batch_size")).intValue();
529: BATCH_SIZE_LINEARMULTIPLIER = Integer
530: .valueOf(
531: config
532: .getString("list.batch_size_linearmultiplier"))
533: .intValue();
534: BATCH_SIZE_MAX = Integer.valueOf(
535: config.getString("list.batch_size_max")).intValue();
536: MAX_JOINS = Integer.valueOf(
537: config.getString("list.max_joins")).intValue();
538: } catch (Exception e) {
539: logger
540: .error(
541: "could not read configuration file, using hardcoded defaults.",
542: e);
543: }
544: }
545: }
|