1*7c478bd9Sstevel@tonic-gate /*-
2*7c478bd9Sstevel@tonic-gate * See the file LICENSE for redistribution information.
3*7c478bd9Sstevel@tonic-gate *
4*7c478bd9Sstevel@tonic-gate * Copyright (c) 1998
5*7c478bd9Sstevel@tonic-gate * Sleepycat Software. All rights reserved.
6*7c478bd9Sstevel@tonic-gate */
7*7c478bd9Sstevel@tonic-gate
8*7c478bd9Sstevel@tonic-gate #include "config.h"
9*7c478bd9Sstevel@tonic-gate
10*7c478bd9Sstevel@tonic-gate #ifndef lint
11*7c478bd9Sstevel@tonic-gate static const char sccsid[] = "@(#)db_join.c 10.10 (Sleepycat) 10/9/98";
12*7c478bd9Sstevel@tonic-gate #endif /* not lint */
13*7c478bd9Sstevel@tonic-gate
14*7c478bd9Sstevel@tonic-gate #ifndef NO_SYSTEM_INCLUDES
15*7c478bd9Sstevel@tonic-gate #include <sys/types.h>
16*7c478bd9Sstevel@tonic-gate
17*7c478bd9Sstevel@tonic-gate #include <errno.h>
18*7c478bd9Sstevel@tonic-gate #include <string.h>
19*7c478bd9Sstevel@tonic-gate #endif
20*7c478bd9Sstevel@tonic-gate
21*7c478bd9Sstevel@tonic-gate #include "db_int.h"
22*7c478bd9Sstevel@tonic-gate #include "db_page.h"
23*7c478bd9Sstevel@tonic-gate #include "db_join.h"
24*7c478bd9Sstevel@tonic-gate #include "db_am.h"
25*7c478bd9Sstevel@tonic-gate #include "common_ext.h"
26*7c478bd9Sstevel@tonic-gate
27*7c478bd9Sstevel@tonic-gate static int __db_join_close __P((DBC *));
28*7c478bd9Sstevel@tonic-gate static int __db_join_del __P((DBC *, u_int32_t));
29*7c478bd9Sstevel@tonic-gate static int __db_join_get __P((DBC *, DBT *, DBT *, u_int32_t));
30*7c478bd9Sstevel@tonic-gate static int __db_join_put __P((DBC *, DBT *, DBT *, u_int32_t));
31*7c478bd9Sstevel@tonic-gate
32*7c478bd9Sstevel@tonic-gate /*
33*7c478bd9Sstevel@tonic-gate * This is the duplicate-assisted join functionality. Right now we're
34*7c478bd9Sstevel@tonic-gate * going to write it such that we return one item at a time, although
35*7c478bd9Sstevel@tonic-gate * I think we may need to optimize it to return them all at once.
36*7c478bd9Sstevel@tonic-gate * It should be easier to get it working this way, and I believe that
37*7c478bd9Sstevel@tonic-gate * changing it should be fairly straightforward.
38*7c478bd9Sstevel@tonic-gate *
39*7c478bd9Sstevel@tonic-gate * XXX
40*7c478bd9Sstevel@tonic-gate * Right now we do not maintain the number of duplicates so we do
41*7c478bd9Sstevel@tonic-gate * not optimize the join. If the caller does, then best performance
42*7c478bd9Sstevel@tonic-gate * will be achieved by putting the cursor with the smallest cardinality
43*7c478bd9Sstevel@tonic-gate * first.
44*7c478bd9Sstevel@tonic-gate *
45*7c478bd9Sstevel@tonic-gate * The first cursor moves sequentially through the duplicate set while
46*7c478bd9Sstevel@tonic-gate * the others search explicitly for the duplicate in question.
47*7c478bd9Sstevel@tonic-gate *
48*7c478bd9Sstevel@tonic-gate */
49*7c478bd9Sstevel@tonic-gate
50*7c478bd9Sstevel@tonic-gate /*
51*7c478bd9Sstevel@tonic-gate * __db_join --
52*7c478bd9Sstevel@tonic-gate * This is the interface to the duplicate-assisted join functionality.
53*7c478bd9Sstevel@tonic-gate * In the same way that cursors mark a position in a database, a cursor
54*7c478bd9Sstevel@tonic-gate * can mark a position in a join. While most cursors are created by the
55*7c478bd9Sstevel@tonic-gate * cursor method of a DB, join cursors are created through an explicit
56*7c478bd9Sstevel@tonic-gate * call to DB->join.
57*7c478bd9Sstevel@tonic-gate *
58*7c478bd9Sstevel@tonic-gate * The curslist is an array of existing, intialized cursors and primary
59*7c478bd9Sstevel@tonic-gate * is the DB of the primary file. The data item that joins all the
60*7c478bd9Sstevel@tonic-gate * cursors in the curslist is used as the key into the primary and that
61*7c478bd9Sstevel@tonic-gate * key and data are returned. When no more items are left in the join
62*7c478bd9Sstevel@tonic-gate * set, the c_next operation off the join cursor will return DB_NOTFOUND.
63*7c478bd9Sstevel@tonic-gate *
64*7c478bd9Sstevel@tonic-gate * PUBLIC: int __db_join __P((DB *, DBC **, u_int32_t, DBC **));
65*7c478bd9Sstevel@tonic-gate */
66*7c478bd9Sstevel@tonic-gate int
__db_join(primary,curslist,flags,dbcp)67*7c478bd9Sstevel@tonic-gate __db_join(primary, curslist, flags, dbcp)
68*7c478bd9Sstevel@tonic-gate DB *primary;
69*7c478bd9Sstevel@tonic-gate DBC **curslist, **dbcp;
70*7c478bd9Sstevel@tonic-gate u_int32_t flags;
71*7c478bd9Sstevel@tonic-gate {
72*7c478bd9Sstevel@tonic-gate DBC *dbc;
73*7c478bd9Sstevel@tonic-gate JOIN_CURSOR *jc;
74*7c478bd9Sstevel@tonic-gate int i, ret;
75*7c478bd9Sstevel@tonic-gate
76*7c478bd9Sstevel@tonic-gate DB_PANIC_CHECK(primary);
77*7c478bd9Sstevel@tonic-gate
78*7c478bd9Sstevel@tonic-gate if ((ret = __db_joinchk(primary, flags)) != 0)
79*7c478bd9Sstevel@tonic-gate return (ret);
80*7c478bd9Sstevel@tonic-gate
81*7c478bd9Sstevel@tonic-gate if (curslist == NULL || curslist[0] == NULL)
82*7c478bd9Sstevel@tonic-gate return (EINVAL);
83*7c478bd9Sstevel@tonic-gate
84*7c478bd9Sstevel@tonic-gate dbc = NULL;
85*7c478bd9Sstevel@tonic-gate jc = NULL;
86*7c478bd9Sstevel@tonic-gate
87*7c478bd9Sstevel@tonic-gate if ((ret = __os_calloc(1, sizeof(DBC), &dbc)) != 0)
88*7c478bd9Sstevel@tonic-gate goto err;
89*7c478bd9Sstevel@tonic-gate
90*7c478bd9Sstevel@tonic-gate if ((ret = __os_calloc(1, sizeof(JOIN_CURSOR), &jc)) != 0)
91*7c478bd9Sstevel@tonic-gate goto err;
92*7c478bd9Sstevel@tonic-gate
93*7c478bd9Sstevel@tonic-gate if ((ret = __os_malloc(256, NULL, &jc->j_key.data)) != 0)
94*7c478bd9Sstevel@tonic-gate goto err;
95*7c478bd9Sstevel@tonic-gate jc->j_key.ulen = 256;
96*7c478bd9Sstevel@tonic-gate F_SET(&jc->j_key, DB_DBT_USERMEM);
97*7c478bd9Sstevel@tonic-gate
98*7c478bd9Sstevel@tonic-gate for (jc->j_curslist = curslist;
99*7c478bd9Sstevel@tonic-gate *jc->j_curslist != NULL; jc->j_curslist++)
100*7c478bd9Sstevel@tonic-gate ;
101*7c478bd9Sstevel@tonic-gate if ((ret = __os_calloc((jc->j_curslist - curslist + 1),
102*7c478bd9Sstevel@tonic-gate sizeof(DBC *), &jc->j_curslist)) != 0)
103*7c478bd9Sstevel@tonic-gate goto err;
104*7c478bd9Sstevel@tonic-gate for (i = 0; curslist[i] != NULL; i++) {
105*7c478bd9Sstevel@tonic-gate if (i != 0)
106*7c478bd9Sstevel@tonic-gate F_SET(curslist[i], DBC_KEYSET);
107*7c478bd9Sstevel@tonic-gate jc->j_curslist[i] = curslist[i];
108*7c478bd9Sstevel@tonic-gate }
109*7c478bd9Sstevel@tonic-gate
110*7c478bd9Sstevel@tonic-gate dbc->c_close = __db_join_close;
111*7c478bd9Sstevel@tonic-gate dbc->c_del = __db_join_del;
112*7c478bd9Sstevel@tonic-gate dbc->c_get = __db_join_get;
113*7c478bd9Sstevel@tonic-gate dbc->c_put = __db_join_put;
114*7c478bd9Sstevel@tonic-gate dbc->internal = jc;
115*7c478bd9Sstevel@tonic-gate dbc->dbp = primary;
116*7c478bd9Sstevel@tonic-gate jc->j_init = 1;
117*7c478bd9Sstevel@tonic-gate jc->j_primary = primary;
118*7c478bd9Sstevel@tonic-gate
119*7c478bd9Sstevel@tonic-gate *dbcp = dbc;
120*7c478bd9Sstevel@tonic-gate
121*7c478bd9Sstevel@tonic-gate return (0);
122*7c478bd9Sstevel@tonic-gate
123*7c478bd9Sstevel@tonic-gate err: if (jc != NULL) {
124*7c478bd9Sstevel@tonic-gate if (jc->j_curslist != NULL)
125*7c478bd9Sstevel@tonic-gate __os_free(jc->j_curslist,
126*7c478bd9Sstevel@tonic-gate (jc->j_curslist - curslist + 1) * sizeof(DBC *));
127*7c478bd9Sstevel@tonic-gate __os_free(jc, sizeof(JOIN_CURSOR));
128*7c478bd9Sstevel@tonic-gate }
129*7c478bd9Sstevel@tonic-gate if (dbc != NULL)
130*7c478bd9Sstevel@tonic-gate __os_free(dbc, sizeof(DBC));
131*7c478bd9Sstevel@tonic-gate return (ret);
132*7c478bd9Sstevel@tonic-gate }
133*7c478bd9Sstevel@tonic-gate
134*7c478bd9Sstevel@tonic-gate static int
__db_join_put(dbc,key,data,flags)135*7c478bd9Sstevel@tonic-gate __db_join_put(dbc, key, data, flags)
136*7c478bd9Sstevel@tonic-gate DBC *dbc;
137*7c478bd9Sstevel@tonic-gate DBT *key;
138*7c478bd9Sstevel@tonic-gate DBT *data;
139*7c478bd9Sstevel@tonic-gate u_int32_t flags;
140*7c478bd9Sstevel@tonic-gate {
141*7c478bd9Sstevel@tonic-gate DB_PANIC_CHECK(dbc->dbp);
142*7c478bd9Sstevel@tonic-gate
143*7c478bd9Sstevel@tonic-gate COMPQUIET(key, NULL);
144*7c478bd9Sstevel@tonic-gate COMPQUIET(data, NULL);
145*7c478bd9Sstevel@tonic-gate COMPQUIET(flags, 0);
146*7c478bd9Sstevel@tonic-gate return (EINVAL);
147*7c478bd9Sstevel@tonic-gate }
148*7c478bd9Sstevel@tonic-gate
149*7c478bd9Sstevel@tonic-gate static int
__db_join_del(dbc,flags)150*7c478bd9Sstevel@tonic-gate __db_join_del(dbc, flags)
151*7c478bd9Sstevel@tonic-gate DBC *dbc;
152*7c478bd9Sstevel@tonic-gate u_int32_t flags;
153*7c478bd9Sstevel@tonic-gate {
154*7c478bd9Sstevel@tonic-gate DB_PANIC_CHECK(dbc->dbp);
155*7c478bd9Sstevel@tonic-gate
156*7c478bd9Sstevel@tonic-gate COMPQUIET(flags, 0);
157*7c478bd9Sstevel@tonic-gate return (EINVAL);
158*7c478bd9Sstevel@tonic-gate }
159*7c478bd9Sstevel@tonic-gate
160*7c478bd9Sstevel@tonic-gate static int
__db_join_get(dbc,key,data,flags)161*7c478bd9Sstevel@tonic-gate __db_join_get(dbc, key, data, flags)
162*7c478bd9Sstevel@tonic-gate DBC *dbc;
163*7c478bd9Sstevel@tonic-gate DBT *key, *data;
164*7c478bd9Sstevel@tonic-gate u_int32_t flags;
165*7c478bd9Sstevel@tonic-gate {
166*7c478bd9Sstevel@tonic-gate DB *dbp;
167*7c478bd9Sstevel@tonic-gate DBC **cpp;
168*7c478bd9Sstevel@tonic-gate JOIN_CURSOR *jc;
169*7c478bd9Sstevel@tonic-gate int ret;
170*7c478bd9Sstevel@tonic-gate u_int32_t operation;
171*7c478bd9Sstevel@tonic-gate
172*7c478bd9Sstevel@tonic-gate dbp = dbc->dbp;
173*7c478bd9Sstevel@tonic-gate
174*7c478bd9Sstevel@tonic-gate DB_PANIC_CHECK(dbp);
175*7c478bd9Sstevel@tonic-gate
176*7c478bd9Sstevel@tonic-gate operation = LF_ISSET(DB_OPFLAGS_MASK);
177*7c478bd9Sstevel@tonic-gate if (operation != 0 && operation != DB_JOIN_ITEM)
178*7c478bd9Sstevel@tonic-gate return (__db_ferr(dbp->dbenv, "DBcursor->c_get", 0));
179*7c478bd9Sstevel@tonic-gate
180*7c478bd9Sstevel@tonic-gate LF_CLR(DB_OPFLAGS_MASK);
181*7c478bd9Sstevel@tonic-gate if ((ret =
182*7c478bd9Sstevel@tonic-gate __db_fchk(dbp->dbenv, "DBcursor->c_get", flags, DB_RMW)) != 0)
183*7c478bd9Sstevel@tonic-gate return (ret);
184*7c478bd9Sstevel@tonic-gate
185*7c478bd9Sstevel@tonic-gate jc = (JOIN_CURSOR *)dbc->internal;
186*7c478bd9Sstevel@tonic-gate retry:
187*7c478bd9Sstevel@tonic-gate ret = jc->j_curslist[0]->c_get(jc->j_curslist[0],
188*7c478bd9Sstevel@tonic-gate &jc->j_key, key, jc->j_init ? DB_CURRENT : DB_NEXT_DUP);
189*7c478bd9Sstevel@tonic-gate
190*7c478bd9Sstevel@tonic-gate if (ret == ENOMEM) {
191*7c478bd9Sstevel@tonic-gate jc->j_key.ulen <<= 1;
192*7c478bd9Sstevel@tonic-gate if ((ret = __os_realloc(&jc->j_key.data, jc->j_key.ulen)) != 0)
193*7c478bd9Sstevel@tonic-gate return (ret);
194*7c478bd9Sstevel@tonic-gate goto retry;
195*7c478bd9Sstevel@tonic-gate }
196*7c478bd9Sstevel@tonic-gate if (ret != 0)
197*7c478bd9Sstevel@tonic-gate return (ret);
198*7c478bd9Sstevel@tonic-gate
199*7c478bd9Sstevel@tonic-gate jc->j_init = 0;
200*7c478bd9Sstevel@tonic-gate do {
201*7c478bd9Sstevel@tonic-gate /*
202*7c478bd9Sstevel@tonic-gate * We have the first element; now look for it in the
203*7c478bd9Sstevel@tonic-gate * other cursors.
204*7c478bd9Sstevel@tonic-gate */
205*7c478bd9Sstevel@tonic-gate for (cpp = jc->j_curslist + 1; *cpp != NULL; cpp++) {
206*7c478bd9Sstevel@tonic-gate retry2: if ((ret = ((*cpp)->c_get)(*cpp,
207*7c478bd9Sstevel@tonic-gate &jc->j_key, key, DB_GET_BOTH)) == DB_NOTFOUND)
208*7c478bd9Sstevel@tonic-gate break;
209*7c478bd9Sstevel@tonic-gate if (ret == ENOMEM) {
210*7c478bd9Sstevel@tonic-gate jc->j_key.ulen <<= 1;
211*7c478bd9Sstevel@tonic-gate if ((ret = __os_realloc(&jc->j_key.data,
212*7c478bd9Sstevel@tonic-gate jc->j_key.ulen)) != 0)
213*7c478bd9Sstevel@tonic-gate return (ret);
214*7c478bd9Sstevel@tonic-gate goto retry2;
215*7c478bd9Sstevel@tonic-gate }
216*7c478bd9Sstevel@tonic-gate if (F_ISSET(*cpp, DBC_KEYSET)) {
217*7c478bd9Sstevel@tonic-gate F_CLR(*cpp, DBC_KEYSET);
218*7c478bd9Sstevel@tonic-gate F_SET(*cpp, DBC_CONTINUE);
219*7c478bd9Sstevel@tonic-gate }
220*7c478bd9Sstevel@tonic-gate }
221*7c478bd9Sstevel@tonic-gate
222*7c478bd9Sstevel@tonic-gate /*
223*7c478bd9Sstevel@tonic-gate * If we got out of here with ret != 0, then we failed to
224*7c478bd9Sstevel@tonic-gate * find the duplicate in one of the files, so we go on to
225*7c478bd9Sstevel@tonic-gate * the next item in the outermost relation. If ret was
226*7c478bd9Sstevel@tonic-gate * equal to 0, then we've got something to return.
227*7c478bd9Sstevel@tonic-gate */
228*7c478bd9Sstevel@tonic-gate if (ret == 0)
229*7c478bd9Sstevel@tonic-gate break;
230*7c478bd9Sstevel@tonic-gate } while ((ret = jc->j_curslist[0]->c_get(jc->j_curslist[0],
231*7c478bd9Sstevel@tonic-gate &jc->j_key, key, DB_NEXT_DUP)) == 0);
232*7c478bd9Sstevel@tonic-gate
233*7c478bd9Sstevel@tonic-gate /*
234*7c478bd9Sstevel@tonic-gate * If ret != 0 here, we've exhausted the first file. Otherwise,
235*7c478bd9Sstevel@tonic-gate * key and data are set and we need to do the lookup on the
236*7c478bd9Sstevel@tonic-gate * primary.
237*7c478bd9Sstevel@tonic-gate */
238*7c478bd9Sstevel@tonic-gate if (ret != 0)
239*7c478bd9Sstevel@tonic-gate return (ret);
240*7c478bd9Sstevel@tonic-gate
241*7c478bd9Sstevel@tonic-gate if (operation == DB_JOIN_ITEM)
242*7c478bd9Sstevel@tonic-gate return (0);
243*7c478bd9Sstevel@tonic-gate else
244*7c478bd9Sstevel@tonic-gate return ((jc->j_primary->get)(jc->j_primary,
245*7c478bd9Sstevel@tonic-gate jc->j_curslist[0]->txn, key, data, 0));
246*7c478bd9Sstevel@tonic-gate }
247*7c478bd9Sstevel@tonic-gate
248*7c478bd9Sstevel@tonic-gate static int
__db_join_close(dbc)249*7c478bd9Sstevel@tonic-gate __db_join_close(dbc)
250*7c478bd9Sstevel@tonic-gate DBC *dbc;
251*7c478bd9Sstevel@tonic-gate {
252*7c478bd9Sstevel@tonic-gate JOIN_CURSOR *jc;
253*7c478bd9Sstevel@tonic-gate int i;
254*7c478bd9Sstevel@tonic-gate
255*7c478bd9Sstevel@tonic-gate DB_PANIC_CHECK(dbc->dbp);
256*7c478bd9Sstevel@tonic-gate
257*7c478bd9Sstevel@tonic-gate jc = (JOIN_CURSOR *)dbc->internal;
258*7c478bd9Sstevel@tonic-gate
259*7c478bd9Sstevel@tonic-gate /*
260*7c478bd9Sstevel@tonic-gate * Clear the optimization flag in the cursors.
261*7c478bd9Sstevel@tonic-gate */
262*7c478bd9Sstevel@tonic-gate for (i = 0; jc->j_curslist[i] != NULL; i++)
263*7c478bd9Sstevel@tonic-gate F_CLR(jc->j_curslist[i], DBC_CONTINUE | DBC_KEYSET);
264*7c478bd9Sstevel@tonic-gate
265*7c478bd9Sstevel@tonic-gate __os_free(jc->j_curslist, 0);
266*7c478bd9Sstevel@tonic-gate __os_free(jc->j_key.data, jc->j_key.ulen);
267*7c478bd9Sstevel@tonic-gate __os_free(jc, sizeof(JOIN_CURSOR));
268*7c478bd9Sstevel@tonic-gate __os_free(dbc, sizeof(DBC));
269*7c478bd9Sstevel@tonic-gate
270*7c478bd9Sstevel@tonic-gate return (0);
271*7c478bd9Sstevel@tonic-gate }
272