Re: Fast bitwise search

From: Connor McDonald <connor_mcdonald_at_yahoo.com>
Date: Thu, 03 Jun 2004 21:37:30 +0800
Message-ID: <40BF299A.3B9F@yahoo.com>

Richard Kuhler wrote:
>
> Connor McDonald wrote:
> > Richard Kuhler wrote:
> >
> >>kuntz.1507173_at_bloglines.com wrote:
> >>
> >>>we have a large table that contains a bitmask field:
> >>>MASK NUMBER(19)
> >>>
> >>>The application then performs a query that includes BITAND(MASK, ?) > 0
> >>>condition.
> >>>
> >>>Is there any way to use an index for this condition. I was thinking
> >>>about bitmap indexes for this but could not figure out how to use them
> >>>here.
> >>
> >>Why in the world would you bundle data up into a column like that? I
> >>can't imagine why the correct solution isn't to break those bits out
> >>into individual columns with descriptive names so people can actually
> >>see what information is stored there. Then you could use bitmap indexes
> >>on them if performance dictated it (keeping in mind the problems they
> >>create).
> >>
> >>--
> >>Richard Kuhler
> >
> >
> > Lets says its 20 attributes, each being boolean. A b-tree index isn't
> > going to help since the cardinality is so low.
>
> That's an over simplification. Especially with a bitmask where you are
> looking for rows with bits set. What if only 1 row in a 100 million row
> table has the attribute value you are looking for? Even if you forget
> about histograms, you can use a null-or-set design to create an index
> that will just have the rows that have the attribute set.
>
> > So you might indeed be up for a full scan no matter what, at which
> > point, a bit mask in a single column may indeed be the best way to go
>
> Sure, but should we design a data model purely so it gives the best
> performance possible? When does usability come into the equation?
>
> --
> Richard Kuhler

Fine for a single predicate, but once its any combination of:

and col1 = ...
and col3 = ...
and col4 = ...
and col17 = ...

and col21 = ...
and col37 = ...
etc
etc
etc

then thats a lot of candidate indexes to be considered

-- 
Connor McDonald
Co-author: "Mastering Oracle PL/SQL - Practical Solutions"
ISBN: 1590592174

web: http://www.oracledba.co.uk
web: http://www.oaktable.net
email: connor_mcdonald_at_yahoo.com

Coming Soon! "Oracle Insight - Tales of the OakTable"

"GIVE a man a fish and he will eat for a day. But TEACH him how to fish,
and...he will sit in a boat and drink beer all day"

------------------------------------------------------------

Received on Thu Jun 03 2004 - 08:37:30 CDT