On Tue, 19 Oct 2004, Josh Berkus wrote: > Tom, > > > I've been taking "bitmap" to be a rather handwavy way of saying "a > > compact representation of sets of CTIDs that is readily amenable to > > being ANDed and ORed with other sets". > > Well, actually I think we're talking about two different features: > > 1) a way to use more than one index per operation; > 2) a more compact and thus faster index representation
For those interested, how this generally works is that for every distinct value in the column being indexed, a bitmap of unique row identifiers (ie, tids) is created. With compression, this can greatly reduce the size of indexes on a large number of rows with a small number of distinct values (a situation in which we're highly likely to use seq scan index of index in Postgres). For qualifications like: bitmapcol1 AND/OR bitmapcol2, we can use bitmap and/or respectively. Of course, this is all in theory. Bitmap indexes can suffer concurrency issues, depending on the granularity of locking. > You gave the impression that (1) could be implemented with regular BTree > indexes in an earlier e-mail. Would that be very hard to do? > > > The whole thing starts to look like a self-adaptive > > interpolation between our present indexscan and seqscan techniques, > > which takes a lot of pressure off the planner to correctly guess the > > number of matching rows in advance. > > This would be way cool. I think there's a lot of be gained by the technique above as an alternative to our current access methods. Its just a feeling however, I haven't prototyped this. Thanks, Gavin ---------------------------(end of broadcast)--------------------------- TIP 3: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly