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