pg.ddx.io pgsql-performance@postgresql.org mailing list archive
help / color / mirror / Atom feedencourging bitmap AND
6+ messages / 4 participants
[nested] [flat]
* encourging bitmap AND
@ 2010-12-23 20:06 Ben <midfield@gmail.com>
2010-12-23 20:52 ` Re: encourging bitmap AND Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 1 reply; 6+ messages in thread
From: Ben @ 2010-12-23 20:06 UTC (permalink / raw)
To: pgsql-performance
hello --
i have a schema similar to the following
create table foo (
id integer not null,
val integer not null,
s integer not null,
e integer not null
);
create index foo_s_idx on foo using btree (s);
create index foo_e_idx on foo using btree (e);
i want to do queries like
select * from foo where 150 between s and e;
this usually gives me index or bitmap scans on one of the indices, plus a filter for the other condition. this is not terribly efficient as the table is large (billions of rows), but there should only be a few thousand rows with s < k < e for any k. the data is id, value, interval (s, e), with s < e, and e - s is "small".
i am experimenting and would like to see the effect of using a bitmap index "AND" scan using both indices. as far as i can tell, there are no easy ways to force or encourage this -- there are no switches like enable_seqscan and such which force the use of bitmap AND, and i don't know how to tell the query planner about the structure of the data (i don't think this is adequately captured in any of the statistics it generates, i would need multi-column statistics.)
any clues?
best regards, ben
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: encourging bitmap AND
2010-12-23 20:06 encourging bitmap AND Ben <midfield@gmail.com>
@ 2010-12-23 20:52 ` Tom Lane <tgl@sss.pgh.pa.us>
2010-12-23 21:01 ` Re: encourging bitmap AND Ben <midfield@gmail.com>
2010-12-26 06:50 ` Re: encourging bitmap AND Marti Raudsepp <marti@juffo.org>
0 siblings, 2 replies; 6+ messages in thread
From: Tom Lane @ 2010-12-23 20:52 UTC (permalink / raw)
To: Ben <midfield@gmail.com>; +Cc: pgsql-performance
Ben <midfield@gmail.com> writes:
> i have a schema similar to the following
> create index foo_s_idx on foo using btree (s);
> create index foo_e_idx on foo using btree (e);
> i want to do queries like
> select * from foo where 150 between s and e;
That index structure is really entirely unsuited to what you want to do,
so it's not surprising that the planner isn't impressed with the idea of
a bitmap AND.
I'd suggest setting up something involving a gist index over an
interval-ish datatype. The PERIOD datatype that Jeff Davis is fooling
with would do what you want --- see
http://pgfoundry.org/projects/temporal
http://thoughts.j-davis.com/2009/11/08/temporal-keys-part-2/
If you don't want any add-on parts involved, you could fake it by using
a box or possibly lseg.
regards, tom lane
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: encourging bitmap AND
2010-12-23 20:06 encourging bitmap AND Ben <midfield@gmail.com>
2010-12-23 20:52 ` Re: encourging bitmap AND Tom Lane <tgl@sss.pgh.pa.us>
@ 2010-12-23 21:01 ` Ben <midfield@gmail.com>
1 sibling, 0 replies; 6+ messages in thread
From: Ben @ 2010-12-23 21:01 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: pgsql-performance
On Dec 23, 2010, at 12:52 PM, Tom Lane wrote:
> Ben <midfield@gmail.com> writes:
>> i have a schema similar to the following
>
>> create index foo_s_idx on foo using btree (s);
>> create index foo_e_idx on foo using btree (e);
>
>> i want to do queries like
>
>> select * from foo where 150 between s and e;
>
> That index structure is really entirely unsuited to what you want to do,
> so it's not surprising that the planner isn't impressed with the idea of
> a bitmap AND.
>
> I'd suggest setting up something involving a gist index over an
> interval-ish datatype. The PERIOD datatype that Jeff Davis is fooling
> with would do what you want --- see
> http://pgfoundry.org/projects/temporal
> http://thoughts.j-davis.com/2009/11/08/temporal-keys-part-2/
> If you don't want any add-on parts involved, you could fake it by using
> a box or possibly lseg.
Thanks for the quick response. I've already played a lot with the PERIOD datatype and GIST, it works pretty good, but I found that the lack of statistics and real selectivity functions hurt me. I was experimenting with the two column setup as an alternative, but if you think this is a dead end I'll look elsewhere.
Best regards, Ben
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: encourging bitmap AND
2010-12-23 20:06 encourging bitmap AND Ben <midfield@gmail.com>
2010-12-23 20:52 ` Re: encourging bitmap AND Tom Lane <tgl@sss.pgh.pa.us>
@ 2010-12-26 06:50 ` Marti Raudsepp <marti@juffo.org>
2010-12-26 17:24 ` Re: encourging bitmap AND Tom Lane <tgl@sss.pgh.pa.us>
1 sibling, 1 reply; 6+ messages in thread
From: Marti Raudsepp @ 2010-12-26 06:50 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Ben <midfield@gmail.com>; pgsql-performance
On Thu, Dec 23, 2010 at 22:52, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> Ben <midfield@gmail.com> writes:
>> i have a schema similar to the following
>
>> create index foo_s_idx on foo using btree (s);
>> create index foo_e_idx on foo using btree (e);
>
>> i want to do queries like
>
>> select * from foo where 150 between s and e;
>
> That index structure is really entirely unsuited to what you want to do,
> so it's not surprising that the planner isn't impressed with the idea of
> a bitmap AND.
Why is it unsuited for this query? It expands to (150 < s AND 150 > e)
which should work nicely with bitmap AND as far as I can tell.
Regards,
Marti
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: encourging bitmap AND
2010-12-23 20:06 encourging bitmap AND Ben <midfield@gmail.com>
2010-12-23 20:52 ` Re: encourging bitmap AND Tom Lane <tgl@sss.pgh.pa.us>
2010-12-26 06:50 ` Re: encourging bitmap AND Marti Raudsepp <marti@juffo.org>
@ 2010-12-26 17:24 ` Tom Lane <tgl@sss.pgh.pa.us>
2011-01-02 21:00 ` Re: encourging bitmap AND Jim Nasby <jim@nasby.net>
0 siblings, 1 reply; 6+ messages in thread
From: Tom Lane @ 2010-12-26 17:24 UTC (permalink / raw)
To: Marti Raudsepp <marti@juffo.org>; +Cc: Ben <midfield@gmail.com>; pgsql-performance
Marti Raudsepp <marti@juffo.org> writes:
> On Thu, Dec 23, 2010 at 22:52, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> That index structure is really entirely unsuited to what you want to do,
>> so it's not surprising that the planner isn't impressed with the idea of
>> a bitmap AND.
> Why is it unsuited for this query? It expands to (150 < s AND 150 > e)
> which should work nicely with bitmap AND as far as I can tell.
Well, maybe for small values of "nicely". If you do it like that, then
on average each indexscan will scan about half of its index and return a
bitmap representing about half the rows in the table. That's an
expensive indexscan, and an expensive bitmap-AND operation, even if the
final number of rows out of the AND is small. Plus you're at serious
risk that the bitmaps will become lossy, which degrades the performance
of the final bitmap heapscan.
If you're doing interval queries enough to worry about having an index
for them, you really want an indexing structure that is designed to do
interval queries efficiently.
regards, tom lane
^ permalink raw reply [nested|flat] 6+ messages in thread
* Re: encourging bitmap AND
2010-12-23 20:06 encourging bitmap AND Ben <midfield@gmail.com>
2010-12-23 20:52 ` Re: encourging bitmap AND Tom Lane <tgl@sss.pgh.pa.us>
2010-12-26 06:50 ` Re: encourging bitmap AND Marti Raudsepp <marti@juffo.org>
2010-12-26 17:24 ` Re: encourging bitmap AND Tom Lane <tgl@sss.pgh.pa.us>
@ 2011-01-02 21:00 ` Jim Nasby <jim@nasby.net>
0 siblings, 0 replies; 6+ messages in thread
From: Jim Nasby @ 2011-01-02 21:00 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; Jeff Davis <pgsql@j-davis.com>; +Cc: Marti Raudsepp <marti@juffo.org>; Ben <midfield@gmail.com>; pgsql-performance
On Dec 26, 2010, at 11:24 AM, Tom Lane wrote:
> If you're doing interval queries enough to worry about having an index
> for them, you really want an indexing structure that is designed to do
> interval queries efficiently.
BTW, one way to accomplish that is to transform your data into geometric shapes and then index them accordingly. Prior to the work Jeff Davis has done on time intervals it was common to treat time as points and ranges as lines or boxes. While we no longer need to play those games for time, I don't think there's an equivalent for non-time datatypes.
--
Jim C. Nasby, Database Architect jim@nasby.net
512.569.9461 (cell) http://jim.nasby.net
^ permalink raw reply [nested|flat] 6+ messages in thread
end of thread, other threads:[~2011-01-02 21:00 UTC | newest]
Thread overview: 6+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2010-12-23 20:06 encourging bitmap AND Ben <midfield@gmail.com>
2010-12-23 20:52 ` Tom Lane <tgl@sss.pgh.pa.us>
2010-12-23 21:01 ` Ben <midfield@gmail.com>
2010-12-26 06:50 ` Marti Raudsepp <marti@juffo.org>
2010-12-26 17:24 ` Tom Lane <tgl@sss.pgh.pa.us>
2011-01-02 21:00 ` Jim Nasby <jim@nasby.net>
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox