* Tom Lane <[EMAIL PROTECTED]> [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 ---------------------------(end of broadcast)--------------------------- TIP 6: Have you searched our list archives? http://archives.postgresql.org