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