* Tom Lane <tgl@sss.pgh.pa.us> [01.03.2005 21:07]:
> Hmm, you seem to be envisioning that these are actually lists, not
> arrays --- that is, to find the N'th page in a list requires traversing
> list links starting at the first page. That doesn't sound workable.
> If you can't access all the entries in roughly constant time then the
> thing is going to have problems with big tables.
Bitmaps are arays, you're right. But they are only accessed either when data
is inserted and gets added to the end (there're direct pointers to the last
page in each bitmap in the list of values), or during index scan. Scanning
index implies visiting all pages that forms the bitmap.
After scanning the bitmaps (and performing all logical operations as
requested), we end up with bit positions and need to return CTID from the
list, that resides in the given position in the list-of-CTIDs (yes, it's
actually one huge array, that occupies many pages).
List-of-CTIDs is organized into extents, each extent contains a known number
of pages and all pages for the extent are allocated sequentially. ID of the
first page of each extent is stored in the metapage. Also, it is known at
compile time how many CTIDs can be stored into one page. Given all that, it is
possible to compute ID of the page and CTID offset inside that page by CTID
offset, obtained at bitmap scan step.
Each extent has 2,4,8,16,32,etc. pages, so the metapage has enough space to
store an array of ID's for the first page of each extent.
Updating list-of-CTIDs is also "cheap" operation, as direct reference to the
last page in the list-of-CTIDs is stored in metapage.
The only list, that have drawbacks you've mentioned, is list-of-values. But,
as it contains only attributes' related data and pointers to start page of
corresponding bitmap, there won't be many pages in this list.
Maybe, there are some more insufficiencies I've missed?
--
Victor Y. Yegorov
