From fdc0450db25021eddcc65d032fd3fd8ca5976928 Mon Sep 17 00:00:00 2001 From: Derrell Lipman Date: Wed, 22 Jun 2005 02:39:07 +0000 Subject: r7828: Although there is still plenty to do, ldb_sqlite3 now passes the set of tests in tests/test-sqlite3.sh (tests/test-generic.sh). There are lots of optimizations still TBD, and some things are REALLY slow right now (e.g. each add() operation takes 1/3 - 1/2 second) but it's ready for interested parties to poke it and prod it and see how (un)reasonable it is. Play away. Still to be implemented or improved: - tdb specials (@MODULES, @SUBCLASSES, etc.) - all DNs are case-folded in their entirty right now (since doing otherwise would require @ATTRIBUTES to be implemented) - speed improvements and optimizations. I am quite confident that the excessively slow add() operation can be much improved, and other areas can be somewhat improved. (This used to be commit 1dd865005594671e7effe06fb088fa97fa08de0b) --- source4/lib/ldb/ldb_sqlite3/schema | 367 +++++++++++++++++++++++++++---------- 1 file changed, 272 insertions(+), 95 deletions(-) (limited to 'source4/lib/ldb/ldb_sqlite3/schema') diff --git a/source4/lib/ldb/ldb_sqlite3/schema b/source4/lib/ldb/ldb_sqlite3/schema index c44351c543..08dc50de08 100644 --- a/source4/lib/ldb/ldb_sqlite3/schema +++ b/source4/lib/ldb/ldb_sqlite3/schema @@ -12,130 +12,160 @@ SELECT 'LDB' AS database_type, '1.0' AS version; - -- ------------------------------------------------------ - -- Schema - /* - * The entry table holds the information about an entry. This - * table is used to obtain the EID of the entry and to support - * scope="one" and scope="base". The parent and child table - * is included in the entry table since all the other - * attributes are dependent on EID. + * Get the next USN value with: + * BEGIN EXCLUSIVE; + * UPDATE usn SET value = value + 1; + * SELECT value FROM usn; + * COMMIT; */ - CREATE TABLE ldb_entry + CREATE TABLE usn ( - -- Unique identifier of this LDB entry - eid INTEGER PRIMARY KEY, - - -- Unique identifier of the parent LDB entry - peid INTEGER REFERENCES ldb_entry, - - -- Distinguished name of this entry - dn TEXT, - - -- Time when the entry was created - create_timestamp INTEGER, - - -- Time when the entry was last modified - modify_timestamp INTEGER + value INTEGER ); - - /* - * The purpose of the descendant table is to support the - * subtree search feature. For each LDB entry with a unique - * ID (AEID), this table contains the unique identifiers - * (DEID) of the descendant entries. - * - * For evern entry in the directory, a row exists in this - * table for each of its ancestors including itself. The size - * of the table depends on the depth of each entry. In the - * worst case, if all the entries were at the same depth, the - * number of rows in the table is O(nm) where n is the number - * of nodes in the directory and m is the depth of the tree. - */ - CREATE TABLE ldb_descendants + CREATE TABLE ldb_object ( - -- The unique identifier of the ancestor LDB entry - aeid INTEGER REFERENCES ldb_entry, - - -- The unique identifier of the descendant LDB entry - deid INTEGER REFERENCES ldb_entry - ); - - - CREATE TABLE ldb_object_classes - ( - -- Object classes are inserted into this table to track - -- their class hierarchy. 'top' is the top-level class - -- of which all other classes are subclasses. - class_name TEXT PRIMARY KEY, - - -- tree_key tracks the position of the class in - -- the hierarchy - tree_key TEXT UNIQUE + /* tree_key is auto-generated by the insert trigger */ + tree_key TEXT PRIMARY KEY, + + parent_tree_key TEXT, + dn TEXT, + + attr_name TEXT REFERENCES ldb_attributes, + attr_value TEXT, + + /* + * object_type can take on these values (to date): + * 1: object is a node of a DN + * 2: object is an attribute/value pair of its parent DN + */ + object_type INTEGER, + + /* + * if object_type is 1, the node can have children. + * this tracks the maximum previously assigned child + * number so we can generate a new unique tree key for + * a new child object. note that this is always incremented, + * so if children are deleted, this will not represent + * the _number_ of children. + */ + max_child_num INTEGER, + + /* + * Automatically maintained meta-data (a gift for metze) + */ + object_guid TEXT UNIQUE, + timestamp INTEGER, -- originating_time + invoke_id TEXT, -- GUID: originating_invocation_id + usn INTEGER, -- hyper: originating_usn + + /* do not allow duplicate name/value pairs */ + UNIQUE (parent_tree_key, attr_name, attr_value, object_type) ); - /* - * We keep a full listing of attribute/value pairs here - */ - CREATE TABLE ldb_attribute_values + CREATE TABLE ldb_attributes ( - eid INTEGER REFERENCES ldb_entry, - - attr_name TEXT, -- see ldb_attr_ATTRIBUTE_NAME + attr_name TEXT PRIMARY KEY, + parent_tree_key TEXT, - attr_value TEXT - ); + objectclass_p BOOLEAN DEFAULT 0, + case_insensitive_p BOOLEAN DEFAULT 0, + wildcard_p BOOLEAN DEFAULT 0, + hidden_p BOOLEAN DEFAULT 0, + integer_p BOOLEAN DEFAULT 0, - /* - * There is one attribute table per searchable attribute. - */ -/* - CREATE TABLE ldb_attr_ATTRIBUTE_NAME - ( - -- The unique identifier of the LDB entry - eid INTEGER REFERENCES ldb_entry, - - -- Normalized attribute value - attr_value TEXT + /* tree_key is auto-generated by the insert trigger */ + tree_key TEXT, -- null if not a object/sub class + -- level 1 if an objectclass + -- level 1-n if a subclass + max_child_num INTEGER ); -*/ - -- ------------------------------------------------------ - -- Indexes + CREATE INDEX ldb_object_dn_idx + ON ldb_object (dn); + + CREATE INDEX ldb_attributes_tree_key_ids + ON ldb_attributes (tree_key); -- ------------------------------------------------------ - -- Triggers - CREATE TRIGGER ldb_entry_insert_tr + /* Gifts for metze. Automatically updated meta-data */ + CREATE TRIGGER ldb_object_insert_tr AFTER INSERT - ON ldb_entry + ON ldb_object FOR EACH ROW BEGIN - UPDATE ldb_entry - SET create_timestamp = strftime('%s', 'now'), - modify_timestamp = strftime('%s', 'now') - WHERE eid = new.eid; + UPDATE ldb_object + SET max_child_num = max_child_num + 1 + WHERE tree_key = new.parent_tree_key; + UPDATE usn SET value = value + 1; + UPDATE ldb_object + SET tree_key = + (SELECT + new.tree_key || + base160(SELECT max_child_num + FROM ldb_object + WHERE tree_key = + new.parent_tree_key)); + max_child_num = 0, + object_guid = random_guid(), + timestamp = strftime('%s', 'now'), + usn = (SELECT value FROM usn); + WHERE tree_key = new.tree_key; END; - CREATE TRIGGER ldb_entry_update_tr + CREATE TRIGGER ldb_object_update_tr AFTER UPDATE - ON ldb_entry + ON ldb_object FOR EACH ROW BEGIN - UPDATE ldb_entry - SET modify_timestamp = strftime('%s', 'now') - WHERE eid = old.eid; + UPDATE usn SET value = value + 1; + UPDATE ldb_object + SET timestamp = strftime('%s', 'now'), + usn = (SELECT value FROM usn); + WHERE tree_key = new.tree_key; END; + CREATE TRIGGER ldb_attributes_insert_tr + AFTER INSERT + ON ldb_attributes + FOR EACH ROW + BEGIN + UPDATE ldb_attributes + SET max_child_num = max_child_num + 1 + WHERE tree_key = new.parent_tree_key; + UPDATE ldb_attributes + SET tree_key = + (SELECT + new.tree_key || + base160(SELECT max_child_num + FROM ldb_attributes + WHERE tree_key = + new.parent_tree_key)); + max_child_num = 0 + WHERE tree_key = new.tree_key; + END; + + -- ------------------------------------------------------ - -- Table initialization - /* We need an implicit 'top' level object class */ + /* Initialize usn */ + INSERT INTO usn (value) VALUES (0); + + /* Create root object */ + INSERT INTO ldb_object + (tree_key, parent_tree_key, + dn, + object_type, max_child_num) + VALUES ('', NULL, + '', + 1, 0); + + /* We need an implicit "top" level object class */ INSERT INTO ldb_attributes (attr_name, parent_tree_key) SELECT 'top', ''; @@ -146,13 +176,58 @@ -- ------------------------------------------------------ -/*** TESTS ***/ - /* * dn: o=University of Michigan,c=US * objectclass: organization * objectclass: domainRelatedObject */ +-- newDN +BEGIN; + +INSERT OR IGNORE INTO ldb_object + (parent_tree_key + dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('', + 'c=US', + 'c', 'US', 1, 0); + +INSERT INTO ldb_object + (parent_tree_key, + dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('0001', + 'o=University of Michigan,c=US', + 'o', 'University of Michigan', 1, 0); + +-- newObjectClass +INSERT OR IGNORE INTO ldb_attributes + (attr_name, parent_tree_key, objectclass_p) + VALUES + ('objectclass', '', 1); + +INSERT INTO ldb_object + (parent_tree_key, + dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('00010001', + NULL, + 'objectclass', 'organization', 2, 0); + +INSERT OR IGNORE INTO ldb_attributes + (attr_name, parent_tree_key, objectclass_p) + VALUES + ('objectclass', '', 1); + +INSERT INTO ldb_object + (parent_tree_key, + dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('00010001', + NULL, + 'objectclass', 'domainRelatedObject', 2, 0); + +COMMIT; /* @@ -164,6 +239,48 @@ * seeAlso: * telephonenumber: +1 313 764-1817 */ +-- addAttrValuePair +BEGIN; + +INSERT INTO ldb_object + (parent_tree_key, dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('00010001', NULL, + 'l', 'Ann Arbor, Michigan', 2, 0); + +INSERT INTO ldb_object + (parent_tree_key, dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('00010001', NULL, + 'st', 'Michigan', 2, 0); + +INSERT INTO ldb_object + (parent_tree_key, dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('00010001', NULL, + 'o', 'University of Michigan', 2, 0); + +INSERT INTO ldb_object + (parent_tree_key, dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('00010001', NULL, + 'o', 'UMICH', 2, 0); + +INSERT INTO ldb_object + (parent_tree_key, dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('00010001', NULL, + 'seeAlso', '', 2, 0); + +INSERT INTO ldb_object + (parent_tree_key, dn, + attr_name, attr_value, object_type, max_child_num) + VALUES ('00010001', NULL, + 'telephonenumber', '+1 313 764-1817', 2, 0); + +COMMIT; + +-- ---------------------------------------------------------------------- /* * dn: @ATTRIBUTES @@ -172,6 +289,44 @@ * ou: CASE_INSENSITIVE * dn: CASE_INSENSITIVE */ +-- newAttribute + +BEGIN; + +INSERT OR IGNORE INTO ldb_attributes + (attr_name, parent_tree_key, objectclass_p) + VALUES + ('uid', '', 0); + +UPDATE ldb_attributes + SET case_insensitive_p = 1, + wildcard_p = 1, + hidden_p = 0, + integer_p = 0 + WHERE attr_name = 'uid' + +UPDATE ldb_attributes + SET case_insensitive_p = 1, + wildcard_p = 0, + hidden_p = 0, + integer_p = 0 + WHERE attr_name = 'cn' + +UPDATE ldb_attributes + SET case_insensitive_p = 1, + wildcard_p = 0, + hidden_p = 0, + integer_p = 0 + WHERE attr_name = 'ou' + +UPDATE ldb_attributes + SET case_insensitive_p = 1, + wildcard_p = 0, + hidden_p = 0, + integer_p = 0 + WHERE attr_name = 'dn' + +-- ---------------------------------------------------------------------- /* * dn: @SUBCLASSES @@ -184,3 +339,25 @@ * organizationalPerson: OpenLDAPperson * user: computer */ +-- insertSubclass + +/* NOT YET UPDATED!!! * + + +INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key) + SELECT 'domain', /* next_tree_key('top') */ '00010001'; +INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key) + SELECT 'person', /* next_tree_key('top') */ '00010002'; +INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key) + SELECT 'domainDNS', /* next_tree_key('domain') */ '000100010001'; +INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key) + SELECT 'organizationalPerson', /* next_tree_key('person') */ '000100020001'; +INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key) + SELECT 'fooPerson', /* next_tree_key('person') */ '000100020002'; +INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key) + SELECT 'user', /* next_tree_key('organizationalPerson') */ '0001000200010001'; +INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key) + SELECT 'OpenLDAPperson', /* next_tree_key('organizationPerson') */ '0001000200010002'; +INSERT OR REPLACE INTO ldb_object_classes (class_name, tree_key) + SELECT 'computer', /* next_tree_key('user') */ '0001000200010001'; + -- cgit