From 015860846ba771392700f962e38953ab320e0387 Mon Sep 17 00:00:00 2001
From: Matthew Swift <matthew.swift@forgerock.com>
Date: Wed, 28 Oct 2015 13:47:09 +0000
Subject: [PATCH] OPENDJ-2328: Optimize UUID equality matching rule indexing
---
opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDOrderingMatchingRuleImpl.java | 92 +----------------
opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDEqualityMatchingRuleImpl.java | 189 +++++++++++++++++++++++--------------
opendj-sdk/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java | 2
3 files changed, 125 insertions(+), 158 deletions(-)
diff --git a/opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDEqualityMatchingRuleImpl.java b/opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDEqualityMatchingRuleImpl.java
index 26f4743..10bd517 100644
--- a/opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDEqualityMatchingRuleImpl.java
+++ b/opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDEqualityMatchingRuleImpl.java
@@ -29,104 +29,145 @@
import static com.forgerock.opendj.ldap.CoreMessages.WARN_ATTR_SYNTAX_UUID_EXPECTED_DASH;
import static com.forgerock.opendj.ldap.CoreMessages.WARN_ATTR_SYNTAX_UUID_EXPECTED_HEX;
import static com.forgerock.opendj.ldap.CoreMessages.WARN_ATTR_SYNTAX_UUID_INVALID_LENGTH;
-import static org.forgerock.opendj.ldap.schema.SchemaConstants.*;
+import static org.forgerock.opendj.ldap.schema.SchemaConstants.EMR_UUID_NAME;
-import org.forgerock.i18n.LocalizableMessage;
+import java.util.Collection;
+import java.util.Collections;
+
+import org.forgerock.opendj.ldap.Assertion;
import org.forgerock.opendj.ldap.ByteSequence;
+import org.forgerock.opendj.ldap.ByteSequenceReader;
import org.forgerock.opendj.ldap.ByteString;
+import org.forgerock.opendj.ldap.ByteStringBuilder;
+import org.forgerock.opendj.ldap.ConditionResult;
import org.forgerock.opendj.ldap.DecodeException;
+import org.forgerock.opendj.ldap.spi.IndexQueryFactory;
+import org.forgerock.opendj.ldap.spi.Indexer;
+import org.forgerock.opendj.ldap.spi.IndexingOptions;
/**
* This class defines the uuidMatch matching rule defined in RFC 4530. It will
* be used as the default equality matching rule for the UUID syntax.
*/
-final class UUIDEqualityMatchingRuleImpl extends AbstractEqualityMatchingRuleImpl {
-
- UUIDEqualityMatchingRuleImpl() {
- super(EMR_UUID_NAME);
- }
-
- public ByteString normalizeAttributeValue(final Schema schema, final ByteSequence value)
- throws DecodeException {
- if (value.length() != 36) {
- final LocalizableMessage message =
- WARN_ATTR_SYNTAX_UUID_INVALID_LENGTH.get(value.toString(), value.length());
- throw DecodeException.error(message);
+final class UUIDEqualityMatchingRuleImpl extends AbstractMatchingRuleImpl {
+ /**
+ * An optimized hash based indexer which stores a 4 byte hash of the UUID. Mix the bytes using XOR similar
+ * to UUID.hashCode(): 128 down to 64 then 32.
+ */
+ private static final Collection<? extends Indexer> INDEXERS = Collections.singleton(new Indexer() {
+ @Override
+ public void createKeys(Schema schema, ByteSequence value, Collection<ByteString> keys) throws DecodeException {
+ keys.add(hash(normalize(value)));
}
- final StringBuilder builder = new StringBuilder(36);
- char c;
+ @Override
+ public String keyToHumanReadableString(ByteSequence key) {
+ return key.toByteString().toHexString();
+ }
+
+ @Override
+ public String getIndexID() {
+ return EMR_UUID_NAME;
+ }
+ });
+
+ UUIDEqualityMatchingRuleImpl() {
+ // Nothing to do.
+ }
+
+ @Override
+ public ByteString normalizeAttributeValue(final Schema schema, final ByteSequence value) throws DecodeException {
+ return normalize(value).toByteString();
+ }
+
+ @Override
+ public Assertion getAssertion(final Schema schema, final ByteSequence assertionValue) throws DecodeException {
+ final ByteString normalizedAssertionValue = normalizeAttributeValue(schema, assertionValue);
+ return new Assertion() {
+ @Override
+ public ConditionResult matches(final ByteSequence normalizedAttributeValue) {
+ return ConditionResult.valueOf(normalizedAssertionValue.equals(normalizedAttributeValue));
+ }
+
+ @Override
+ public <T> T createIndexQuery(final IndexQueryFactory<T> factory) throws DecodeException {
+ return factory.createExactMatchQuery(EMR_UUID_NAME, hash(normalizedAssertionValue));
+ }
+ };
+ }
+
+ @Override
+ public Collection<? extends Indexer> createIndexers(final IndexingOptions options) {
+ return INDEXERS;
+ }
+
+ // Package private so that it can be reused by ordering matching rule.
+ static ByteSequence normalize(final ByteSequence value) throws DecodeException {
+ if (value.length() != 36) {
+ throw DecodeException.error(WARN_ATTR_SYNTAX_UUID_INVALID_LENGTH.get(value, value.length()));
+ }
+ final ByteStringBuilder builder = new ByteStringBuilder(16);
for (int i = 0; i < 36; i++) {
- // The 9th, 14th, 19th, and 24th characters must be dashes. All
- // others must be hex. Convert all uppercase hex characters to
- // lowercase.
- c = (char) value.byteAt(i);
+ // The 9th, 14th, 19th, and 24th characters must be dashes. All others must be hex.
switch (i) {
case 8:
case 13:
case 18:
case 23:
+ final char c = (char) value.byteAt(i);
if (c != '-') {
- final LocalizableMessage message =
- WARN_ATTR_SYNTAX_UUID_EXPECTED_DASH.get(value.toString(), i, String
- .valueOf(c));
- throw DecodeException.error(message);
+ throw DecodeException.error(WARN_ATTR_SYNTAX_UUID_EXPECTED_DASH.get(value, i, c));
}
- builder.append(c);
break;
default:
- switch (c) {
- case '0':
- case '1':
- case '2':
- case '3':
- case '4':
- case '5':
- case '6':
- case '7':
- case '8':
- case '9':
- case 'a':
- case 'b':
- case 'c':
- case 'd':
- case 'e':
- case 'f':
- // These are all fine.
- builder.append(c);
- break;
- case 'A':
- builder.append('a');
- break;
- case 'B':
- builder.append('b');
- break;
- case 'C':
- builder.append('c');
- break;
- case 'D':
- builder.append('d');
- break;
- case 'E':
- builder.append('e');
- break;
- case 'F':
- builder.append('f');
- break;
- default:
- final LocalizableMessage message =
- WARN_ATTR_SYNTAX_UUID_EXPECTED_HEX.get(value.toString(), i, String
- .valueOf(value.byteAt(i)));
- throw DecodeException.error(message);
- }
+ final int high4Bits = decodeHexByte(value, i++);
+ final int low4Bits = decodeHexByte(value, i);
+ builder.append((byte) ((high4Bits << 4) | low4Bits));
+ break;
}
}
-
- return ByteString.valueOf(builder);
+ return builder;
}
- @Override
- public String keyToHumanReadableString(ByteSequence key) {
- return key.toString();
+ private static int decodeHexByte(final ByteSequence value, final int i) throws DecodeException {
+ final char c = (char) value.byteAt(i);
+ switch (c) {
+ case '0':
+ case '1':
+ case '2':
+ case '3':
+ case '4':
+ case '5':
+ case '6':
+ case '7':
+ case '8':
+ case '9':
+ return c - '0';
+ case 'a':
+ case 'b':
+ case 'c':
+ case 'd':
+ case 'e':
+ case 'f':
+ return c - 'a' + 10;
+ case 'A':
+ case 'B':
+ case 'C':
+ case 'D':
+ case 'E':
+ case 'F':
+ return c - 'A' + 10;
+ default:
+ throw DecodeException.error(WARN_ATTR_SYNTAX_UUID_EXPECTED_HEX.get(value, i, c));
+ }
+ }
+
+ private static ByteString hash(final ByteSequence normalizeAttributeValue) {
+ final ByteSequenceReader uuid128Bytes = normalizeAttributeValue.asReader();
+ final long uuidHigh64 = uuid128Bytes.getLong();
+ final long uuidLow64 = uuid128Bytes.getLong();
+ final long uuid64 = uuidHigh64 ^ uuidLow64;
+ final int hash32 = ((int) (uuid64 >> 32)) ^ (int) uuid64;
+ return ByteString.valueOf(hash32);
}
}
diff --git a/opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDOrderingMatchingRuleImpl.java b/opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDOrderingMatchingRuleImpl.java
index 8532b34..5aaefe6 100644
--- a/opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDOrderingMatchingRuleImpl.java
+++ b/opendj-sdk/opendj-core/src/main/java/org/forgerock/opendj/ldap/schema/UUIDOrderingMatchingRuleImpl.java
@@ -26,12 +26,8 @@
*/
package org.forgerock.opendj.ldap.schema;
-import static com.forgerock.opendj.ldap.CoreMessages.WARN_ATTR_SYNTAX_UUID_EXPECTED_DASH;
-import static com.forgerock.opendj.ldap.CoreMessages.WARN_ATTR_SYNTAX_UUID_EXPECTED_HEX;
-import static com.forgerock.opendj.ldap.CoreMessages.WARN_ATTR_SYNTAX_UUID_INVALID_LENGTH;
import static org.forgerock.opendj.ldap.schema.SchemaConstants.*;
-import org.forgerock.i18n.LocalizableMessage;
import org.forgerock.opendj.ldap.ByteSequence;
import org.forgerock.opendj.ldap.ByteString;
import org.forgerock.opendj.ldap.DecodeException;
@@ -41,88 +37,18 @@
* This will be the default ordering matching rule for the UUID syntax.
*/
final class UUIDOrderingMatchingRuleImpl extends AbstractOrderingMatchingRuleImpl {
-
UUIDOrderingMatchingRuleImpl() {
- // Reusing equality index since OPENDJ-1864
- super(EMR_UUID_NAME);
+ // Don't re-use equality matching rule index because it is hash based.
+ super(OMR_UUID_NAME);
}
- public ByteString normalizeAttributeValue(final Schema schema, final ByteSequence value)
- throws DecodeException {
- if (value.length() != 36) {
- final LocalizableMessage message =
- WARN_ATTR_SYNTAX_UUID_INVALID_LENGTH.get(value.toString(), value.length());
- throw DecodeException.error(message);
- }
+ @Override
+ public ByteString normalizeAttributeValue(final Schema schema, final ByteSequence value) throws DecodeException {
+ return UUIDEqualityMatchingRuleImpl.normalize(value).toByteString();
+ }
- final StringBuilder builder = new StringBuilder(36);
- char c;
- for (int i = 0; i < 36; i++) {
- // The 9th, 14th, 19th, and 24th characters must be dashes. All
- // others must be hex. Convert all uppercase hex characters to
- // lowercase.
- c = (char) value.byteAt(i);
- switch (i) {
- case 8:
- case 13:
- case 18:
- case 23:
- if (c != '-') {
- final LocalizableMessage message =
- WARN_ATTR_SYNTAX_UUID_EXPECTED_DASH.get(value.toString(), i, String
- .valueOf(c));
- throw DecodeException.error(message);
- }
- builder.append(c);
- break;
- default:
- switch (c) {
- case '0':
- case '1':
- case '2':
- case '3':
- case '4':
- case '5':
- case '6':
- case '7':
- case '8':
- case '9':
- case 'a':
- case 'b':
- case 'c':
- case 'd':
- case 'e':
- case 'f':
- // These are all fine.
- builder.append(c);
- break;
- case 'A':
- builder.append('a');
- break;
- case 'B':
- builder.append('b');
- break;
- case 'C':
- builder.append('c');
- break;
- case 'D':
- builder.append('d');
- break;
- case 'E':
- builder.append('e');
- break;
- case 'F':
- builder.append('f');
- break;
- default:
- final LocalizableMessage message =
- WARN_ATTR_SYNTAX_UUID_EXPECTED_HEX.get(value.toString(), i, String
- .valueOf(value.byteAt(i)));
- throw DecodeException.error(message);
- }
- }
- }
-
- return ByteString.valueOf(builder);
+ @Override
+ public String keyToHumanReadableString(ByteSequence key) {
+ return key.toString();
}
}
diff --git a/opendj-sdk/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java b/opendj-sdk/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java
index f2d9200..e08bc70 100644
--- a/opendj-sdk/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java
+++ b/opendj-sdk/opendj-core/src/test/java/org/forgerock/opendj/ldap/DNTestCase.java
@@ -1127,7 +1127,7 @@
{ "governingStructureRule=256,dc=com", "dc=com,governingstructurerule=%82%01%00" },
// uuid
{ "entryUUID=597ae2f6-16a6-1027-98f4-d28b5365dc14,dc=com",
- "dc=com,entryuuid=597ae2f6-16a6-1027-98f4-d28b5365dc14" },
+ "dc=com,entryuuid=%59%7A%E2%F6%16%A6%10%27%98%F4%D2%8B%53%65%DC%14" },
// characters unescaped by URL encoding (-, _, ., ~)
{ "dc=example\\2Dtest,dc=com", "dc=com,dc=example-test" },
{ "dc=example\\5Ftest,dc=com", "dc=com,dc=example_test" },
--
Gitblit v1.10.0