1 /*- 2 * See the file LICENSE for redistribution information. 3 * 4 * Copyright (c) 2002, 2014 Oracle and/or its affiliates. All rights reserved. 5 * 6 */ 7 8 package com.sleepycat.je.test; 9 10 import static org.junit.Assert.assertEquals; 11 import static org.junit.Assert.assertSame; 12 import static org.junit.Assert.assertTrue; 13 14 import java.util.ArrayList; 15 import java.util.List; 16 17 import org.junit.Test; 18 import org.junit.runner.RunWith; 19 import org.junit.runners.Parameterized; 20 import org.junit.runners.Parameterized.Parameters; 21 22 import com.sleepycat.je.Cursor; 23 import com.sleepycat.je.CursorConfig; 24 import com.sleepycat.je.Database; 25 import com.sleepycat.je.DatabaseConfig; 26 import com.sleepycat.je.DatabaseEntry; 27 import com.sleepycat.je.DatabaseException; 28 import com.sleepycat.je.DbInternal; 29 import com.sleepycat.je.EnvironmentConfig; 30 import com.sleepycat.je.JoinConfig; 31 import com.sleepycat.je.JoinCursor; 32 import com.sleepycat.je.LockMode; 33 import com.sleepycat.je.OperationStatus; 34 import com.sleepycat.je.SecondaryConfig; 35 import com.sleepycat.je.SecondaryCursor; 36 import com.sleepycat.je.SecondaryDatabase; 37 import com.sleepycat.je.SecondaryKeyCreator; 38 import com.sleepycat.je.Transaction; 39 import com.sleepycat.je.util.TestUtils; 40 41 @RunWith(Parameterized.class) 42 public class JoinTest extends MultiKeyTxnTestCase { 43 44 /* 45 * DATA sets are pairs of arrays for each record. The first array is 46 * the record data and has three values in the 0/1/2 positions for the 47 * secondary key values with key IDs 0/1/2. second array contains a single 48 * value which is the primary key. 49 * 50 * JOIN sets are also pairs of arrays. The first array in each pair has 3 51 * values for setting the input cursors. Entries 0/1/2 in that array are 52 * for secondary keys 0/1/2. The second array is the set of primary keys 53 * that are expected to match in the join operation. 54 * 55 * A zero value for an index key means "don't index", so zero values are 56 * never used for join index keys since we wouldn't be able to successfully 57 * position the input cursor. 58 * 59 * These values are all stored as bytes, not ints, in the actual records, 60 * so all values must be within the range of a signed byte. 61 */ 62 private static final int[][][] ALL = { 63 /* Data set #1 - single match possible per record. */ 64 { 65 {1, 1, 1}, {11}, 66 {2, 2, 2}, {12}, 67 {3, 3, 3}, {13}, 68 }, { 69 {1, 1, 1}, {11}, 70 {2, 2, 2}, {12}, 71 {3, 3, 3}, {13}, 72 {1, 2, 3}, {}, 73 {1, 1, 2}, {}, 74 {3, 2, 2}, {}, 75 }, 76 /* Data set #2 - no match possible when all indices are not present 77 * (when some are zero). */ 78 { 79 {1, 1, 0}, {11}, 80 {2, 0, 2}, {12}, 81 {0, 3, 3}, {13}, 82 {3, 2, 1}, {14}, 83 }, { 84 {1, 1, 1}, {}, 85 {2, 2, 2}, {}, 86 {3, 3, 3}, {}, 87 }, 88 /* Data set #3 - one match in the presence of non-matching records 89 * (with missing/zero index keys). */ 90 { 91 {1, 0, 0}, {11}, 92 {1, 1, 0}, {12}, 93 {1, 1, 1}, {13}, 94 {0, 0, 0}, {14}, 95 }, { 96 {1, 1, 1}, {13}, 97 }, 98 /* Data set #4 - one match in the presence of non-matching records 99 * (with non-matching but non-zero values). */ 100 { 101 {1, 2, 3}, {11}, 102 {1, 1, 3}, {12}, 103 {1, 1, 1}, {13}, 104 {3, 2, 1}, {14}, 105 }, { 106 {1, 1, 1}, {13}, 107 }, 108 /* Data set #5 - two matches in the presence of non-matching records. 109 */ 110 { 111 {1, 2, 3}, {11}, 112 {1, 1, 3}, {12}, 113 {1, 1, 1}, {13}, 114 {1, 2, 3}, {14}, 115 }, { 116 {1, 2, 3}, {11, 14}, 117 }, 118 /* Data set #6 - three matches in the presence of non-matching records. 119 * Also used to verify that cursors are sorted by count: 2, 1, 0 */ 120 { 121 {1, 2, 3}, {11}, 122 {1, 1, 3}, {12}, 123 {1, 1, 1}, {13}, 124 {1, 2, 3}, {14}, 125 {1, 1, 1}, {15}, 126 {1, 0, 0}, {16}, 127 {1, 1, 0}, {17}, 128 {1, 1, 1}, {18}, 129 {0, 0, 0}, {19}, 130 {3, 2, 1}, {20}, 131 }, { 132 {1, 1, 1}, {13, 15, 18}, 133 }, 134 /* Data set #7 - three matches by themselves. */ 135 { 136 {1, 2, 3}, {11}, 137 {1, 2, 3}, {12}, 138 {1, 2, 3}, {13}, 139 }, { 140 {1, 2, 3}, {11, 12, 13}, 141 }, 142 }; 143 144 /* Used for testing the cursors are sorted by count. */ 145 private static final int CURSOR_ORDER_SET = 6; 146 private static final int[] CURSOR_ORDER = {2, 1, 0}; 147 148 private static EnvironmentConfig envConfig = TestUtils.initEnvConfig(); 149 static { 150 envConfig.setAllowCreate(true); 151 } 152 153 private static JoinConfig joinConfigNoSort = new JoinConfig(); 154 static { 155 joinConfigNoSort.setNoSort(true); 156 } 157 158 @Parameters genParams()159 public static List<Object[]> genParams() { 160 return paramsHelper(false); 161 } 162 paramsHelper(boolean rep)163 protected static List<Object[]> paramsHelper(boolean rep) { 164 final String[] txnTypes = getTxnTypes(null, rep); 165 final List<Object[]> newParams = new ArrayList<Object[]>(); 166 for (final String type : txnTypes) { 167 newParams.add(new Object[] {type, true}); 168 newParams.add(new Object[] {type, false}); 169 } 170 return newParams; 171 } 172 JoinTest(String type, boolean multiKey)173 public JoinTest(String type, boolean multiKey){ 174 super.envConfig = envConfig; 175 txnType = type; 176 useMultiKey = multiKey; 177 isTransactional = (txnType != TXN_NULL); 178 customName = ((useMultiKey) ? "multiKey" : "") + "-" + txnType; 179 } 180 181 @Test testJoin()182 public void testJoin() 183 throws DatabaseException { 184 185 for (CursorConfig config : 186 new CursorConfig[] { null, CursorConfig.READ_UNCOMMITTED }) { 187 for (boolean withData : new boolean[] { false, true }) { 188 for (int i = 0; i < ALL.length; i += 2) { 189 doJoin(ALL[i], ALL[i + 1], (i / 2) + 1, withData, config); 190 } 191 } 192 } 193 } 194 doJoin(int[][] dataSet, int[][] joinSet, int setNum, boolean withData, CursorConfig cursorConfig)195 private void doJoin(int[][] dataSet, 196 int[][] joinSet, 197 int setNum, 198 boolean withData, 199 CursorConfig cursorConfig) 200 throws DatabaseException { 201 202 String name = "Set#" + setNum; 203 Database priDb = openPrimary("pri"); 204 SecondaryDatabase secDb0 = openSecondary(priDb, "sec0", true, 0); 205 SecondaryDatabase secDb1 = openSecondary(priDb, "sec1", true, 1); 206 SecondaryDatabase secDb2 = openSecondary(priDb, "sec2", true, 2); 207 208 OperationStatus status; 209 DatabaseEntry key = new DatabaseEntry(); 210 DatabaseEntry data = new DatabaseEntry(); 211 Transaction txn; 212 txn = txnBegin(); 213 214 for (int i = 0; i < dataSet.length; i += 2) { 215 int[] vals = dataSet[i]; 216 setData(data, vals[0], vals[1], vals[2]); 217 setKey(key, dataSet[i + 1][0]); 218 status = priDb.put(txn, key, data); 219 assertEquals(name, OperationStatus.SUCCESS, status); 220 } 221 222 txnCommit(txn); 223 txn = txnBeginCursor(); 224 225 SecondaryCursor c0 = secDb0.openSecondaryCursor(txn, cursorConfig); 226 SecondaryCursor c1 = secDb1.openSecondaryCursor(txn, cursorConfig); 227 SecondaryCursor c2 = secDb2.openSecondaryCursor(txn, cursorConfig); 228 SecondaryCursor[] cursors = {c0, c1, c2}; 229 230 for (int i = 0; i < joinSet.length; i += 2) { 231 int[] indexKeys = joinSet[i]; 232 int[] priKeys = joinSet[i + 1]; 233 String prefix = name + " row=" + i; 234 for (int k = 0; k < 3; k += 1) { 235 String msg = prefix + " k=" + k + " ikey=" + indexKeys[k]; 236 setKey(key, indexKeys[k]); 237 status = cursors[k].getSearchKey(key, data, 238 LockMode.DEFAULT); 239 assertEquals(msg, OperationStatus.SUCCESS, status); 240 } 241 for (int j = 0; j < 2; j += 1) { 242 JoinConfig config = (j == 0) ? null : joinConfigNoSort; 243 JoinCursor jc = priDb.join(cursors, config); 244 assertSame(priDb, jc.getDatabase()); 245 for (int k = 0; k < priKeys.length; k += 1) { 246 String msg = prefix + " k=" + k + " pkey=" + priKeys[k]; 247 if (withData) { 248 status = jc.getNext(key, data, LockMode.DEFAULT); 249 } else { 250 status = jc.getNext(key, LockMode.DEFAULT); 251 } 252 assertEquals(msg, OperationStatus.SUCCESS, status); 253 assertEquals(msg, priKeys[k], key.getData()[0]); 254 if (withData) { 255 boolean dataFound = false; 256 for (int m = 0; m < dataSet.length; m += 2) { 257 int[] vals = dataSet[m]; 258 int priKey = dataSet[m + 1][0]; 259 if (priKey == priKeys[k]) { 260 for (int n = 0; n < 3; n += 1) { 261 assertEquals(msg, vals[n], 262 data.getData()[n]); 263 dataFound = true; 264 } 265 } 266 } 267 assertTrue(msg, dataFound); 268 } 269 } 270 String msg = prefix + " no more expected"; 271 if (withData) { 272 status = jc.getNext(key, data, LockMode.DEFAULT); 273 } else { 274 status = jc.getNext(key, LockMode.DEFAULT); 275 } 276 assertEquals(msg, OperationStatus.NOTFOUND, status); 277 278 Cursor[] sorted = DbInternal.getSortedCursors(jc); 279 assertEquals(CURSOR_ORDER.length, sorted.length); 280 if (config == joinConfigNoSort) { 281 Database db0 = sorted[0].getDatabase(); 282 Database db1 = sorted[1].getDatabase(); 283 Database db2 = sorted[2].getDatabase(); 284 assertSame(db0, secDb0); 285 assertSame(db1, secDb1); 286 assertSame(db2, secDb2); 287 } else if (setNum == CURSOR_ORDER_SET) { 288 Database db0 = sorted[CURSOR_ORDER[0]].getDatabase(); 289 Database db1 = sorted[CURSOR_ORDER[1]].getDatabase(); 290 Database db2 = sorted[CURSOR_ORDER[2]].getDatabase(); 291 assertSame(db0, secDb0); 292 assertSame(db1, secDb1); 293 assertSame(db2, secDb2); 294 } 295 jc.close(); 296 } 297 } 298 299 c0.close(); 300 c1.close(); 301 c2.close(); 302 txnCommit(txn); 303 304 secDb0.close(); 305 secDb1.close(); 306 secDb2.close(); 307 priDb.close(); 308 309 /* Remove dbs since we reuse them multiple times in a single case. */ 310 txn = txnBegin(); 311 env.removeDatabase(txn, "pri"); 312 env.removeDatabase(txn, "sec0"); 313 env.removeDatabase(txn, "sec1"); 314 env.removeDatabase(txn, "sec2"); 315 txnCommit(txn); 316 } 317 318 /** 319 * Checks that a join operation does not block writers from inserting 320 * duplicates with the same main key as the search key. Writers were being 321 * blocked before we changed join() to use READ_UNCOMMITTED when getting 322 * the duplicate count for each cursor. [#11833] 323 */ 324 @Test testWriteDuringJoin()325 public void testWriteDuringJoin() 326 throws DatabaseException { 327 328 Database priDb = openPrimary("pri"); 329 SecondaryDatabase secDb0 = openSecondary(priDb, "sec0", true, 0); 330 SecondaryDatabase secDb1 = openSecondary(priDb, "sec1", true, 1); 331 SecondaryDatabase secDb2 = openSecondary(priDb, "sec2", true, 2); 332 333 OperationStatus status; 334 DatabaseEntry key = new DatabaseEntry(); 335 DatabaseEntry data = new DatabaseEntry(); 336 Transaction txn; 337 txn = txnBegin(); 338 339 setKey(key, 13); 340 setData(data, 1, 1, 1); 341 status = priDb.put(txn, key, data); 342 assertEquals(OperationStatus.SUCCESS, status); 343 setKey(key, 14); 344 setData(data, 1, 1, 1); 345 status = priDb.put(txn, key, data); 346 assertEquals(OperationStatus.SUCCESS, status); 347 348 txnCommit(txn); 349 txn = txnBeginCursor(); 350 351 SecondaryCursor c0 = secDb0.openSecondaryCursor(txn, null); 352 SecondaryCursor c1 = secDb1.openSecondaryCursor(txn, null); 353 SecondaryCursor c2 = secDb2.openSecondaryCursor(txn, null); 354 SecondaryCursor[] cursors = {c0, c1, c2}; 355 356 for (int i = 0; i < 3; i += 1) { 357 setKey(key, 1); 358 status = cursors[i].getSearchKey(key, data, 359 LockMode.READ_UNCOMMITTED); 360 assertEquals(OperationStatus.SUCCESS, status); 361 } 362 363 /* join() will get the cursor counts. */ 364 JoinCursor jc = priDb.join(cursors, null); 365 366 /* 367 * After calling join(), try inserting dups for the same main key. 368 * Before the fix to use READ_UNCOMMITTED, this would cause a deadlock. 369 */ 370 Transaction writerTxn = txnBegin(); 371 setKey(key, 12); 372 setData(data, 1, 1, 1); 373 status = priDb.put(writerTxn, key, data); 374 assertEquals(OperationStatus.SUCCESS, status); 375 376 /* The join should retrieve two records, 13 and 14. */ 377 status = jc.getNext(key, data, LockMode.DEFAULT); 378 assertEquals(OperationStatus.SUCCESS, status); 379 assertEquals(13, key.getData()[0]); 380 status = jc.getNext(key, data, LockMode.DEFAULT); 381 assertEquals(OperationStatus.SUCCESS, status); 382 assertEquals(14, key.getData()[0]); 383 status = jc.getNext(key, data, LockMode.DEFAULT); 384 assertEquals(OperationStatus.NOTFOUND, status); 385 386 /* Try writing again after calling getNext(). */ 387 setKey(key, 11); 388 setData(data, 1, 1, 1); 389 status = priDb.put(writerTxn, key, data); 390 assertEquals(OperationStatus.SUCCESS, status); 391 txnCommit(writerTxn); 392 393 jc.close(); 394 395 c0.close(); 396 c1.close(); 397 c2.close(); 398 txnCommit(txn); 399 400 secDb0.close(); 401 secDb1.close(); 402 secDb2.close(); 403 priDb.close(); 404 } 405 openPrimary(String name)406 private Database openPrimary(String name) 407 throws DatabaseException { 408 409 DatabaseConfig dbConfig = new DatabaseConfig(); 410 dbConfig.setTransactional(isTransactional); 411 dbConfig.setAllowCreate(true); 412 413 Transaction txn = txnBegin(); 414 try { 415 return env.openDatabase(txn, name, dbConfig); 416 } finally { 417 txnCommit(txn); 418 } 419 } 420 openSecondary(Database priDb, String dbName, boolean dups, int keyId)421 private SecondaryDatabase openSecondary(Database priDb, String dbName, 422 boolean dups, int keyId) 423 throws DatabaseException { 424 425 SecondaryConfig dbConfig = new SecondaryConfig(); 426 dbConfig.setTransactional(isTransactional); 427 dbConfig.setAllowCreate(true); 428 dbConfig.setSortedDuplicates(dups); 429 if (useMultiKey) { 430 dbConfig.setMultiKeyCreator 431 (new SimpleMultiKeyCreator(new MyKeyCreator(keyId))); 432 } else { 433 dbConfig.setKeyCreator(new MyKeyCreator(keyId)); 434 } 435 436 Transaction txn = txnBegin(); 437 try { 438 return env.openSecondaryDatabase(txn, dbName, priDb, dbConfig); 439 } finally { 440 txnCommit(txn); 441 } 442 } 443 setKey(DatabaseEntry key, int priKey)444 private static void setKey(DatabaseEntry key, int priKey) { 445 446 byte[] a = new byte[1]; 447 a[0] = (byte) priKey; 448 key.setData(a); 449 } 450 setData(DatabaseEntry data, int key1, int key2, int key3)451 private static void setData(DatabaseEntry data, 452 int key1, int key2, int key3) { 453 454 byte[] a = new byte[4]; 455 a[0] = (byte) key1; 456 a[1] = (byte) key2; 457 a[2] = (byte) key3; 458 data.setData(a); 459 } 460 461 private static class MyKeyCreator implements SecondaryKeyCreator { 462 463 private final int keyId; 464 MyKeyCreator(int keyId)465 MyKeyCreator(int keyId) { 466 467 this.keyId = keyId; 468 } 469 createSecondaryKey(SecondaryDatabase secondary, DatabaseEntry key, DatabaseEntry data, DatabaseEntry result)470 public boolean createSecondaryKey(SecondaryDatabase secondary, 471 DatabaseEntry key, 472 DatabaseEntry data, 473 DatabaseEntry result) { 474 byte val = data.getData()[keyId]; 475 if (val != 0) { 476 result.setData(new byte[] { val }); 477 return true; 478 } else { 479 return false; 480 } 481 } 482 } 483 } 484