Обсуждение: Queries with conditions using bitand operator

Hi,
I have table "ARTICLE" containing a String a field "STATUS" that
represents a number in binary format (for ex: 10011101).
My application issues queries with where conditions that uses BITAND
operator on this field (for ex: select * from article where status & 4 = 4).
Thus i'm facing performance problemes with these select queries: the
queries are too slow.
Since i'm using the BITAND operator in my conditions, creating an index
on the status filed is useless
  and since the second operator variable (status & 4 = 4; status & 8 =
8; status & 16 = 16...) a functional index is also usless (because a
functional index require the use of a function that accept only table
column as input parameter: constants are not accepted).
So is there a way to enhance the performance of these queries?
Thanks,
Elias

On 07/13/2010 06:48 AM, Elias Ghanem wrote:
> Hi,
> I have table "ARTICLE" containing a String a field "STATUS" that represents a number in binary format (for ex:
10011101).
> My application issues queries with where conditions that uses BITAND operator on this field (for ex: select * from
articlewhere status & 4 = 4). 
> Thus i'm facing performance problemes with these select queries: the queries are too slow.
> Since i'm using the BITAND operator in my conditions, creating an index on the status filed is useless
> and since the second operator variable (status & 4 = 4; status & 8 = 8; status & 16 = 16...) a functional index is
alsousless (because a functional index require the use of a function that accept only table column as input parameter:
constantsare not accepted). 
> So is there a way to enhance the performance of these queries?
> Thanks,
> Elias
>

How many flags are there?  If its not too many you could make a separate column for each... but then that would be lots
ofindexes too... 

One other thought I had was to make it a text column, turn the flags into words (space separated) and use full text
indexes.

I played around with int's and string's but I couldnt find a way using the & operator.

-Andy

On 07/13/2010 04:48 AM, Elias Ghanem wrote:
> Hi,
> I have table "ARTICLE" containing a String a field "STATUS" that
> represents a number in binary format (for ex: 10011101).
> My application issues queries with where conditions that uses BITAND
> operator on this field (for ex: select * from article where status & 4 =
> 4).
> Thus i'm facing performance problemes with these select queries: the
> queries are too slow.
> Since i'm using the BITAND operator in my conditions, creating an index
> on the status filed is useless
>  and since the second operator variable (status & 4 = 4; status & 8 = 8;
> status & 16 = 16...) a functional index is also usless (because a
> functional index require the use of a function that accept only table
> column as input parameter: constants are not accepted).
> So is there a way to enhance the performance of these queries?

You haven't given a lot of info to help us help you, but would something
along these lines be useful to you?

drop table if exists testbit;
create table testbit(
 id serial primary key,
 article text,
 status int
);

insert into testbit (article, status) select 'article ' ||
generate_series::text, generate_series % 256 from
generate_series(1,1000000);

create index idx1 on testbit(article) where status & 1 = 1;
create index idx2 on testbit(article) where status & 2 = 2;
create index idx4 on testbit(article) where status & 4 = 4;
create index idx8 on testbit(article) where status & 8 = 8;
create index idx16 on testbit(article) where status & 16 = 16;
create index idx32 on testbit(article) where status & 512 = 512;

update testbit set status = status + 512 where id in (42, 4242, 424242);
explain analyze select * from testbit where status & 512 = 512;
                          QUERY PLAN
------------------------------------------------------------------
 Index Scan using idx32 on testbit  (cost=0.00..4712.62 rows=5000
                width=22) (actual time=0.080..0.085 rows=3 loops=1)
 Total runtime: 0.170 ms


HTH,

Joe

--
Joe Conway
credativ LLC: http://www.credativ.us
Linux, PostgreSQL, and general Open Source
Training, Service, Consulting, & Support

One of the possibilities would be to decompose your bitmap into an
array of base integers and then create a GIN (or GIST) index on that
array (intarray contrib package). This would make sense if your
articles are distributed relatively equally and if do not do big ORDER
BY and then LIMIT/OFFSET queries, that usually will need to sort the
results gotten from the GIN index.
As your are also probably doing some tsearch queries on the articles,
you can actually build combined (tverctor, intarray) GIN/GIST index to
optimize your searches.

A simple function, that can help you stripping your bitmap integer to
array of positions could look like:

-- DROP FUNCTION utils.bitmap_to_position_intarray(bitmap integer);

CREATE OR REPLACE FUNCTION utils.bitmap_to_position_intarray(bitmap
integer)
  RETURNS integer[] AS
$BODY$
-- test
-- select utils.bitmap_to_position_intarray(5);
-- test performance
-- select utils.bitmap_to_position_intarray(s.i) from
generate_series(1, 10000) as s(i);
--

SELECT ARRAY(
  SELECT s.i + 1 -- here we do +1 to make the position of the first
bit 1
    FROM generate_series(0, 31) as s(i)
   WHERE $1 & ( 1 << s.i ) > 0
  );
$BODY$
  LANGUAGE SQL IMMUTABLE STRICT;

You can create a GIN index directly using this function over your
bitmap field and then using array set operations will make the planner
to use the GIN index (more information about these indexes here:
http://www.postgresql.org/docs/8.4/interactive/textsearch-indexes.html):

CREATE INDEX idx_article_status_gin ON article USING
gin( (utils.bitmap_to_position_intarray(STATUS) ) );

and then you can do:

SELECT * FROM article WHERE utils.bitmap_to_position_intarray(STATUS)
&& ARRAY[1,5];

or

SELECT * FROM article WHERE utils.bitmap_to_position_intarray(STATUS)
&& utils.bitmap_to_position_intarray(5);

Have a look on the possible array set operations in
http://www.postgresql.org/docs/8.4/interactive/intarray.html.

Otherwise a solution from Jeo Conway to create separate indexes for
each bit also is worth to be looked up. This has actually drawbacks,
that you cannot look up combinations of bits efficiently. As an
advantage in the example from Jeo, you can efficiently do ORDER BY
article (or any other field, that you add into these limited
indexes).