[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: back-bdb IDL limitations

Jonghyuk Choi wrote:


The proposed scheme can increase the size of IDLs for attribute indices (esp. substring indices). If neighboring indices in an IDL are spaced with large intervals, the proposed scheme can either 1) double the storage required to represent an ID in the IDL (because lo/hi are needed instead of a single ID), or 2) cause IDs of many irrelevant entries to be included in the IDL.

Rather coincidentally, I've also prepared patches to optimize indexing performance.

The first one is targeting to accelerate slapadd based on the observation that IDs are added in a monotonically ascending order during slapadd. Instead of writing to the index database upon addition of every single ID, slapadd can be made to buffer multiple IDs to make an ID cluster and writes the cluster as a single unit.

An IDL for an index hash will look like the following:

Header consisting of NOID and # of IDs in the IDL
ID cluster 1
ID cluster 2
ID cluster 3
...
ID cluster N

The header and ID clusters are keyed with the same hash value and they are sorted in an ascending order (NOID is treated as the smallest in the dup function). As a result, the number of writes to the index databases can be reduced by the factor of the cluster size. For example, if the cluster size is 1024, the number of writes to the index database can be reduced by up to 1024 and this significantly improves the performance of slapadd.

That sounds pretty good. Also sounds somewhat like extending the IDLcache to have writeback behavior instead of its current writethru mode.

If the IDs in an IDL are rather contiguous, the range optimization you suggested can help. Otherwise, it won't be able to buy us much. I suspect this be the case for the subtree indices for general ldifs (by the term general, I mean not specially sorted for a naming attribute, for example, ou) and substring indices.

For non-tool mode addition (ldapadd), if the currently added ID is the greatest of all IDs in the IDL, it is added as a single ID stored as the end data for the index key. If the currently added ID is not the greatest, then it is added into the ID cluster it belongs (where lo <= ID <= hi holds). If the size of the cluster becomes larger than the max cluster size, it is split into half. To delete an ID from an IDL, the corresponding ID cluster need be located. The cluster will be read, modified, and written in order to remove the ID from the cluster.

This begins to sound like back-ldbm IDblocks. Shuffling IDs from one chunk to another was definitely error-prone there. Certainly it can be done right, just need to be careful about it.

The second one is targeting to accelerate the overall index database performance by using a bit-map to represent IDLs. The compaction achieved by using a bit map instead of using a pointer ID can result in the reduced number of data items for an index key in the index database. This in turn leads to the improved btree search performance. A bit map structure called the segment bit-map can be used for this purpose. A segment bit-map consists of a pointer and a bit map. For example, let's assume that a segment bit-map is 32 bits long of which 24 bits are assigned to the pointer and 8 bits are to the bit map. The pointer represents the 8-bit aligned position of the bit map in the entire ID space while the bit map represents the indexing status for 8 contiguous indices whose position is determined by the pointer. In this example, the segment bit-map can cover indices for (2**24) * 8 entries (128M entries). As a concrete example, a segment bit-map having its pointer field of 2 and its bit map field of 0xA5 tells that the IDs 16, 18, 21, 23 are the indexed entries. We can have multiple of them to represent an entire IDL in the same way we had multiple IDs to represent an IDL. If we use 64 bit long segment bit-maps, then we can increase the coverage that a single segment bit-map can provide and can increase the number of indexed entries. For example if we assign 32 bits to the pointer field and 32 bits to the bit map field, a 64 bit segment bit-map can store indexing values for 32 contiguous entries and it can support up to 128G entries.

This is definitely an improvement over the current scheme, but it still suffers from a hard size limit in a given IDL size. For our current default of 64K words per IDL, using 32 bit maps restricts us to a total of 512K entries in one IDL. Using 64 bit maps only extends that to 1M entries. To be able to approach the limits you describe will still require much larger IDLs than we currently use. Otherwise we're still stuck falling back to ranges when the IDL gets full.

I think this bit-mapped approach provides more workable solution than the range ID solution for the case where IDs in an IDL are rather contiguous. A 32 bit segment bit map covers 8 entries having contiguous IDs without increasing storage requirement and with the ability of pinpointing the exact indexing status of the 8 entries in the contigous range. On the other hand, the range ID consumes double the storage, but it cannot pinpoint the indexing status of the indiviual entries in the range once it is scaled. A 64 bit segment bit map covers 32 entries having contigous IDs with the same amount of storage as in the range ID scheme, but it can provide exact indexing for those 32 entries unlike the range ID approach with scaling.

The bitmap scheme definitely has great appeal. But it only provides a factor-of-8 increase in range over the current scheme, and that just isn't enough. Nor do I think that increasing the size definitions of the IDLs is viable. Whatever size you pick, it will be a hard limit beyond which performance will be radically degraded (because the IDL is necessarily converted to a range anyway at that point). Using scaled ranges as I describe does lose some exactness but it is a much more graceful degradation, and continues to offer some value no matter how large the database gets.

Your point about sparseness of e.g. substring indexes is certainly important. But I believe it's an acceptable tradeoff. In the current scheme, after a slot gets full (at 64K entries), adding another element to it converts the whole thing to a range and then all detail is lost. In the scheme I propose, a slot gets full two times sooner (at 32K ranges, 32K entries worst case) but rescaling only loses a small amount of detail. Also it's possible that the IDL will operate at its 32K limit for a long time without any loss of detail, if the individual ranges naturally grow to overlap and coalesce.

--
 -- Howard Chu
 Chief Architect, Symas Corp.       Director, Highland Sun
 http://www.symas.com               http://highlandsun.com/hyc
 Symas: Premier OpenSource Development and Support