>>>>> "Greg" == Greg Stark <gsstark@mit.edu> writes:
Greg> I think you're talking about situations like "where x = ? or Greg> y = ?" or "where x = ? and y = ?"
Greg> When both `x' and `y' are indexed. It's possible to do the Greg> index lookup, gather a list of tid pointers
insome Greg> efficient format like a bit vector, and apply the and/or and Greg> any other clauses.
Yes, Index ANDing/ORing are useful whether or not the list of tids are
in an efficient format. Especially ORing for performing disjunctions.
Greg> Oracle can do this, and it's useful in some cases when you Greg> have DSS-style where all the indexes have
poorselectivity Greg> but using enough of them together gets you a reasonable Greg> number of records.
I guess this is the piece where "variant indexes" is useful -
essentially when you have a large number of matches for a given key.
I'm not sure how useful it is in practice - I've only read the
original research paper.
Greg> I think this is different from what he meant, but yes, Greg> bitmap indexes might be an interesting project.
Likehash
You're right .. a sorted TLF is really something quite simple that can
make quite a difference in accessing a non-clustered index. I believe
this is something all the commercial guys do. Sorting the Tids before
fetching 'em buys you buffer cache locality. When there are large
numbers of hits, it also buys you sequential scans where the file
system prefetcher can help. The additional overhead you pay is the
sorting cost.
--
Pip-pip
Sailesh
http://www.cs.berkeley.edu/~sailesh
