001: package com.quadcap.sql;
002:
003: /* Copyright 1999 - 2003 Quadcap Software. All rights reserved.
004: *
005: * This software is distributed under the Quadcap Free Software License.
006: * This software may be used or modified for any purpose, personal or
007: * commercial. Open Source redistributions are permitted. Commercial
008: * redistribution of larger works derived from, or works which bundle
009: * this software requires a "Commercial Redistribution License"; see
010: * http://www.quadcap.com/purchase.
011: *
012: * Redistributions qualify as "Open Source" under one of the following terms:
013: *
014: * Redistributions are made at no charge beyond the reasonable cost of
015: * materials and delivery.
016: *
017: * Redistributions are accompanied by a copy of the Source Code or by an
018: * irrevocable offer to provide a copy of the Source Code for up to three
019: * years at the cost of materials and delivery. Such redistributions
020: * must allow further use, modification, and redistribution of the Source
021: * Code under substantially the same terms as this license.
022: *
023: * Redistributions of source code must retain the copyright notices as they
024: * appear in each source code file, these license terms, and the
025: * disclaimer/limitation of liability set forth as paragraph 6 below.
026: *
027: * Redistributions in binary form must reproduce this Copyright Notice,
028: * these license terms, and the disclaimer/limitation of liability set
029: * forth as paragraph 6 below, in the documentation and/or other materials
030: * provided with the distribution.
031: *
032: * The Software is provided on an "AS IS" basis. No warranty is
033: * provided that the Software is free of defects, or fit for a
034: * particular purpose.
035: *
036: * Limitation of Liability. Quadcap Software shall not be liable
037: * for any damages suffered by the Licensee or any third party resulting
038: * from use of the Software.
039: */
040:
041: import java.io.ByteArrayOutputStream;
042: import java.io.Externalizable;
043: import java.io.IOException;
044: import java.io.ObjectInput;
045: import java.io.ObjectOutput;
046:
047: import java.util.BitSet;
048: import java.util.Enumeration;
049: import java.util.Hashtable;
050: import java.util.Vector;
051:
052: import java.sql.SQLException;
053:
054: import com.quadcap.sql.file.BlockFile;
055: import com.quadcap.sql.file.ByteUtil;
056: import com.quadcap.sql.file.PageManager;
057: import com.quadcap.sql.file.RandomAccess;
058:
059: import com.quadcap.sql.io.ObjectOutputStream;
060:
061: import com.quadcap.sql.index.BCursor;
062: import com.quadcap.sql.index.Btree;
063: import com.quadcap.sql.index.Comparator;
064:
065: import com.quadcap.sql.types.Value;
066: import com.quadcap.sql.types.ValueBoolean;
067: import com.quadcap.sql.types.ValueInteger;
068: import com.quadcap.sql.types.Type;
069:
070: import com.quadcap.util.Debug;
071: import com.quadcap.util.Util;
072:
073: /**
074: * Cursor implementing <b>INNER JOIN</b> using nested loops (optimized using
075: * the inner index)
076: *
077: * @author Stan Bailes
078: */
079: public class JoinInnerCursor extends JoinCursor {
080: Database db;
081: BlockFile file;
082: BlockFile tempFile;
083:
084: /** The join columns in the outer table. */
085: int[] caCols;
086:
087: /** The current join key. */
088: byte[] caKey;
089:
090: /** Cache number of columns in inner table. */
091: int cbCnt;
092:
093: /** The join columns in the inner table. */
094: int[] cbCols;
095:
096: /** Map inner, non-join-key columns from join cursor to inner cursor pos */
097: int[] cbMap;
098:
099: /** Map outer columns from join cursor to outer cursor pos */
100: int[] caMap;
101:
102: /** If the inner is really a table, or null if it's a view. */
103: Table cbTable;
104:
105: /** If there's an index on the join columns of the inner table */
106: IndexConstraint cbIndex;
107:
108: /** Either the index from above, or a temporary one we create. */
109: Btree index;
110:
111: /** Did we make 'index', or were the columns already indexed? */
112: boolean tempIndex;
113:
114: /** Did we make create new (temporary) rows for the inner index? */
115: boolean mustFreeRows = false;
116:
117: BCursor cbKeys;
118:
119: /** Used to compare the inner and outer join keys. */
120: Comparator compare;
121:
122: /** Temporary used to build keys for inner table index */
123: MapRow mapRow;
124:
125: /**
126: * Constructor takes a whole shitload of parameters.
127: *
128: * @param session my execution session context (transaction, etc)
129: * @param ca the outer join cursor
130: * @param caCols the join columns in the outer cursor
131: * @param cb the inner join cursor
132: * @param cbCols the join columns in the inner cursor
133: * @param where the ON/WHERE predicate expression
134: * @param tuple the format we're supposed to return
135: * @param row A mapping between the inner/outer rows and the join row
136: * @param left Include non-matching outer rows with nulls for inner
137: * @param inner Include matching rows
138: * @param flip Left is Right, Right is Left
139: */
140: public JoinInnerCursor(Session session, Cursor outer, Cursor ca,
141: int[] caCols, Cursor cb, int[] cbCols, Expression where,
142: Tuple tuple, JoinMapRow row, boolean left, boolean inner)
143: throws SQLException {
144: super (session, outer, ca, cb, where, tuple, row, left, inner);
145: this .db = session.getDatabase();
146: this .file = db.getFile();
147: try {
148: this .tempFile = db.getTempFile();
149: } catch (IOException e) {
150: throw DbException.wrapThrowable(e);
151: }
152: this .caCols = caCols;
153: this .cbCnt = cb.getColumnCount();
154: this .cbCols = cbCols;
155: this .cbIndex = findIndex(cb, cbCols);
156: this .compare = new Key(cbCols.length);
157:
158: int joinCnt = cbCols.length;
159:
160: }
161:
162: final IndexConstraint findIndex(Cursor r, int[] cols)
163: throws SQLException {
164: IndexConstraint ret = null;
165: BitSet b = null;
166: this .cbTable = r.getTable();
167: if (this .cbTable == null) {
168: return null;
169: }
170: final int num = cbTable.getNumConstraints();
171: for (int ci = 0; ci < num; ci++) {
172: Constraint c = cbTable.getConstraint(ci);
173: if (!(c instanceof IndexConstraint))
174: continue;
175: int[] ccols = c.getColumns();
176: if (cols.length != ccols.length)
177: continue;
178: if (b == null)
179: b = intArrayToBitSet(cols);
180: boolean match = true;
181: for (int i = 0; i < ccols.length; i++) {
182: if (!b.get(ccols[i])) {
183: match = false;
184: break;
185: }
186: }
187: if (match)
188: ret = (IndexConstraint) c;
189: }
190: return ret;
191: }
192:
193: final static BitSet intArrayToBitSet(int[] a) {
194: BitSet b = new BitSet();
195: for (int i = 0; i < a.length; i++) {
196: b.set(a[i]);
197: }
198: return b;
199: }
200:
201: final byte[] makeInnerKey(Cursor cursor, Row row, long rowId)
202: throws IOException, SQLException {
203: return Key.makeKey(cursor, row, cbCols, rowId, true);
204: }
205:
206: final byte[] makeOuterKey(Cursor cursor, Row row)
207: throws IOException, SQLException {
208: if (cbIndex != null) {
209: mapRow.setRow(row);
210: return cbIndex.makeKey(session, mapRow, Long.MIN_VALUE);
211: }
212: return Key.makeKey(cursor, row, caCols, Long.MIN_VALUE, true);
213: }
214:
215: protected void bfirst() throws SQLException {
216: try {
217: row.setB(null);
218: if (index == null) {
219: this .index = makeInnerIndex();
220: this .rb = new LazyRow(cbCnt);
221: }
222: caKey = makeOuterKey(ca, ra);
223: if (cbKeys == null)
224: cbKeys = index.getCursor(false);
225: cbKeys.seek(caKey);
226: } catch (IOException e) {
227: throw DbException.wrapThrowable(e);
228: }
229: }
230:
231: final protected boolean bnext() throws SQLException {
232: try {
233: boolean ret = false;
234:
235: while (!ret && cbKeys.next()) {
236: byte[] cbKey = cbKeys.getKeyBuf();
237: int len = cbKeys.getKeyLen();
238: if (compare.compare(caKey, 0, caKey.length, cbKey, 0,
239: len) != 0) {
240: break;
241: }
242: long rowId = cbKeys.getValAsLong();
243: boolean isTemp = cbTable == null;
244: db.getRow(rowId, (LazyRow) rb, isTemp);
245: row.setB(rb);
246: //Debug.println("bnext: rb = " + rb + ", row = " + row);
247: ret = true;
248: }
249: if (!ret)
250: row.setB(null);
251: return ret;
252: } catch (IOException ex) {
253: throw DbException.wrapThrowable(ex);
254: }
255: }
256:
257: final void makeTemporaryIndexForTable() throws IOException,
258: SQLException {
259: //#ifdef DEBUG
260: if (Trace.bit(17)) {
261: StringBuffer sb = new StringBuffer();
262: for (int i = 0; i < cbCols.length; i++) {
263: if (i > 0)
264: sb.append(", ");
265: sb.append(cb.getColumn(cbCols[i]).getName());
266: }
267: Debug.println("Make Temporary Index for " + cb.getName()
268: + " (" + sb + ")");
269: }
270: //#endif
271: Comparator tempCompare = new Key(cbCols.length + 1);
272: index = session.makeTempTree(tempCompare);
273: while (cb.next()) {
274: long rowId = cb.getRowId();
275: Row r = cb.getRow();
276: byte[] key = makeInnerKey(cb, r, rowId);
277: index.set(key, session.getBuf8(rowId));
278: }
279: }
280:
281: final void makeTemporaryIndexForView() throws IOException,
282: SQLException {
283: Comparator tempCompare = new Key(cbCols.length + 1);
284: index = session.makeTempTree(tempCompare);
285: int cnt = 0;
286: mustFreeRows = true;
287: while (cb.next()) {
288: Row r = cb.getRow();
289: byte[] key = makeInnerKey(cb, r, cnt++);
290: long rowId = session.getDatabase().putRow(session,
291: tempFile, cb, r);
292: index.set(key, session.getBuf8(rowId));
293: }
294: }
295:
296: final Btree makeInnerIndex() throws IOException, SQLException {
297: if (cbTable != null) {
298: if (cbIndex != null) {
299: int[] map = new int[cb.getColumnCount() + 1];
300: for (int i = 0; i < cbCols.length; i++) {
301: int ic = cbCols[i];
302: int oc = caCols[i];
303: map[ic] = oc;
304: }
305: mapRow = new MapRow(map, 1);
306: index = cbIndex.getIndex(db);
307: } else {
308: makeTemporaryIndexForTable();
309: tempIndex = true;
310: }
311: } else {
312: makeTemporaryIndexForView();
313: tempIndex = true;
314: }
315: return index;
316: }
317:
318: public void freeRows(Btree index, BlockFile file)
319: throws IOException {
320: BCursor c = index.getCursor();
321: try {
322: while (c.next()) {
323: long rowId = c.getValAsLong();
324: db.removeRow(file, rowId);
325: }
326: } finally {
327: c.release();
328: }
329: }
330:
331: public void close() throws SQLException {
332: try {
333: super .close();
334: } finally {
335: try {
336: if (cbKeys != null)
337: cbKeys.release();
338: } finally {
339: try {
340: cbKeys = null;
341: if (tempIndex && mustFreeRows) {
342: freeRows(index, tempFile);
343: }
344: } catch (IOException e2) {
345: throw DbException.wrapThrowable(e2);
346: } finally {
347: try {
348: mustFreeRows = false;
349: if (tempIndex) {
350: index.free();
351: session.getDatabase().releaseTempFile();
352: }
353: } catch (IOException e3) {
354: throw DbException.wrapThrowable(e3);
355: } finally {
356: index = null;
357: if (tempFile != null) {
358: session.getDatabase().releaseTempFile();
359: tempFile = null;
360: }
361: tempIndex = false;
362: }
363: }
364: }
365: }
366: }
367: }
|