23ce92c0026c6677697cde79cc7f6176536748b9 2499 |
|
27-Jul-2007 |
boli |
These set of changes implement VLV and filter capability to OpenDS:
- A VLV index is defined by a name, base DN, search filter, search scope, sort order. A search request must match these parameters exactly to
use the VLV index.
- A VLV index made up of the entry IDs matching the definition criteria (above) and the corresponding attribute values that are part of the sort
order in the sort order. This information is broken up into blocks of sorted sets. The block size can be configured through admin framework.
Default block size is 4000. In the database, the sorted set is stored with the following format:
4 byte set size | entry IDs of 8 bytes each ... | attribute values of 16 bytes each ...
- Each sorted set is keyed by the entry ID and attribute values of the largest entry in the sorted set. A special comparator (VLVKeyComparator)
is used to sort the keys in the database in the order of the specified sort order.
- When entries are added to the VLV index, its sort values are extracted and inserted into the sorted set whose key (also the largest entry in
the set) is the smallest key that represents a entry that is greater or equal to the entry being inserted. If the sorted set exceeds the block
size, it is divided in two and stored back into the database with the new key. In this implementation, a sorted set's key is never changed after
it is created.
- On importing from LDIF, each entry's sort values and ID is written out to a intermediate file in order. These files are later merged and
inserted into the database.
- Index rebuild and verify also works with VLV indexes. The verify job ensures that all the entries stored in the VLV index is in the correct
order.
- With this implementation, once a VLV index is created, it can not be changed without a rebuild. The server will NOT warn the user if
the index
has changed offline. Until a rebuild is done, it can return incorrect results. This should be fixed later.
- Performance wise, modify, add, and delete performance will be degraded if the entry matches the indexing criteria. Searches not using the VLV
index should not see any notable performance degradation. If the block size is set too big, there is a potential that a large number of updates
will result in some JE lock timeouts since the few sorted sets are hotly contested. However, if the block size is too small, searches using the
VLV control with offsets could be slow since there are more records to look through. This area need further investigation to determine the
optimal default value.
Fix for issue 38 |