Re: [HACKERS] Implementing Bitmap Indexes
On Sat, 29 Jan 2005 18:46:44 +, Mike Rylander <[EMAIL PROTECTED]> wrote : > For on-disk bitmap indexes, yes. I don't see any reason this couldn't > be done with GiST, perhaps even as a generalization of the index stuff > in the int_array contrib module. I was thinking about playing with the core source of PostgreSQL and creating patches, GiST as I read has some limitations that I want to overcome. Speaking about my idea - I was thinking about implementing on-disk indexes, not in memory. I think having both of them would be great :-) -- **Pawel Niewiadomski**, new()foo-baz.com, http://new.foo-baz.com/ Virtual Qmail (http://v-q.foo-baz.com), qmail-patches (http://q-p.foo-baz.com) ---(end of broadcast)--- TIP 4: Don't 'kill -9' the postmaster
Re: [HACKERS] Implementing Bitmap Indexes
On Sat, Jan 29, 2005 at 01:56:12PM +0200, Victor Y. Yegorov wrote: > 2) Queries, like "where A = 1" or "where A != 2" will require only 1 scan of > the index, while "where A < 3" will require 2 stages: 1st create a > list of > values lesser then 3, 2nd --- do OR of all bitmaps for that values. > For high cardinality attributes, this can take a lot of time; > > 3) Each bitmap is only a bitmap, so there should be an array of > corresponding > ctids pointers. Maybe, some more arrays (pages, don't know). > > For 2)nd --- there are techniques, allowing better performance for "A < 3" > queries via increased storage space (see here for details: > http://delab.csd.auth.gr/papers/ADBIS03mmnm.pdf) and increased reaction time > for simple queries. I don't know, if they should be implemented, may later. Sorry if this is in the PDF but I didn't want to read 17 pages to find out... for the example where 1 >= A >= 4, couldn't you just do NOT (A >= 3)? Granted, in this example it wouldn't matter, but it would be faster to do this if you asked for A < 4. One downside is that you'd also have to consider the NULL bitmap, if the field is nullable. -- Jim C. Nasby, Database Consultant [EMAIL PROTECTED] Give your computer some brain candy! www.distributed.net Team #1828 Windows: "Where do you want to go today?" Linux: "Where do you want to go tomorrow?" FreeBSD: "Are you guys coming, or what?" ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [HACKERS] Implementing Bitmap Indexes
On Sun, 30 Jan 2005 12:15:20 +1100, Neil Conway <[EMAIL PROTECTED]> wrote:
> It might _work_, I just don't see the point. Given an attribute of a
> heap relation that has N distinct values and T tuples, you need to store
>
> - N bitmaps, each of T bits (before compression)
> - T ctids
> - a way to map from a bit in one of the bitmaps to a heap tuple
> - a way to decide which bitmap(s) to use for a given index scan
>
> I don't see why it's a win to organize this data in a tree. Why not
> store the ctids in a simple array? You then know that bit K of any
> bitmap refers to entry K of the ctid array. You'd also need some meta
> data to figure out which bitmap to use for a given scankey, but it
> should be pretty easy to do that efficiently.
OK, I think it just clicked. I was seeing a tree for the initial
lookup to find the right bitmaps to scan. Does that seem like to much
overhead for the first step?
So, pick the bitmap(s) based on the key, scan the bitmaps and combine
them based on the WHERE condition combination type, and as you find
matching bits you toss the ctids into a "matching" array. Then it's a
fast ctid scan. That it? I'm very interested in this after reading a
bit (heh he) about bitmap indexes. Here's how I'm visualizing it now:
For a query like "SELECT * FROM table WHERE a IN (1,3)" ...
Index on "table.a" looks like:
bitmaps
1 | 001001001001000
2 | 1001011
3 | 010110100010110
ctids
1 | {2,5,8,11}
2 | {0,7,9,14}
3 | {1,3,4,6,10,12,13}
The index scan would do bitwise a OR on bitmaps 1 and 3, find the
possition of the "1"s, jump to those possitions in the ctid array, and
bounce to the heap for the value.
--
Mike Rylander
[EMAIL PROTECTED]
GPLS -- PINES Development
Database Developer
http://open-ils.org
---(end of broadcast)---
TIP 6: Have you searched our list archives?
http://archives.postgresql.org
Re: [HACKERS] Implementing Bitmap Indexes
Mike Rylander wrote: For the initial example where the index is implemented as a set of unique keys from the table and a bitmap for each key this would look a unique index, but with an extra datum at at each index node to hold the bitmap for that key. If implemented that way an augmented B-Tree structure would work fine. At least that's how I would imagine an on-disk bitmap index would work. It might _work_, I just don't see the point. Given an attribute of a heap relation that has N distinct values and T tuples, you need to store - N bitmaps, each of T bits (before compression) - T ctids - a way to map from a bit in one of the bitmaps to a heap tuple - a way to decide which bitmap(s) to use for a given index scan I don't see why it's a win to organize this data in a tree. Why not store the ctids in a simple array? You then know that bit K of any bitmap refers to entry K of the ctid array. You'd also need some meta data to figure out which bitmap to use for a given scankey, but it should be pretty easy to do that efficiently. -Neil ---(end of broadcast)--- TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
Re: [HACKERS] Implementing Bitmap Indexes
On Sun, 30 Jan 2005 11:07:59 +1100, Neil Conway <[EMAIL PROTECTED]> wrote: > Mike Rylander wrote: > > For on-disk bitmap indexes, yes. I don't see any reason this couldn't > > be done with GiST > > It might be possible to do it with GiST, but GiST is designed for > implementing tree-structured indexes; I don't think it's the right tool > for the job. For the initial example where the index is implemented as a set of unique keys from the table and a bitmap for each key this would look a unique index, but with an extra datum at at each index node to hold the bitmap for that key. If implemented that way an augmented B-Tree structure would work fine. At least that's how I would imagine an on-disk bitmap index would work. I suppose that would make the index much more efficient for high-cardinality values, no? -- Mike Rylander [EMAIL PROTECTED] GPLS -- PINES Development Database Developer http://open-ils.org ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] Implementing Bitmap Indexes
Mike Rylander wrote: For on-disk bitmap indexes, yes. I don't see any reason this couldn't be done with GiST It might be possible to do it with GiST, but GiST is designed for implementing tree-structured indexes; I don't think it's the right tool for the job. -Neil ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [HACKERS] Implementing Bitmap Indexes
Mike Rylander <[EMAIL PROTECTED]> writes: > As a side note, wouldn't the in-memory bitmaps pretty much kill the > need for multicolumn indexes? It seems that they would be able to > join index scans on the same table, and then there would be no need > for industrial strength cross-column correlation stats. No, because the ability to do it is not the same as the ability to predict in advance how many rows will result. regards, tom lane ---(end of broadcast)--- TIP 5: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] Implementing Bitmap Indexes
* Dawid Kuroczko <[EMAIL PROTECTED]> [29.01.2005 21:25]: > With in-memory bitmap, the search would start with index a, all > matching rows would form the bitmap; then the second search > would go through b index, forming another bitmap. Which then > would be ANDed with previous bitmap. Not only matching rows will form a bitmap, all rows should. And the physical order of rows in the table is important to form bitmap. -- Victor Y. Yegorov ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [HACKERS] Implementing Bitmap Indexes
On Sat, 29 Jan 2005 21:54:39 +0200, Victor Yegorov <[EMAIL PROTECTED]> wrote: > * Dawid Kuroczko <[EMAIL PROTECTED]> [29.01.2005 21:25]: > > > With in-memory bitmap, the search would start with index a, all > > matching rows would form the bitmap; then the second search > > would go through b index, forming another bitmap. Which then > > would be ANDed with previous bitmap. > > Not only matching rows will form a bitmap, all rows should. > > And the physical order of rows in the table is important to form bitmap. My mistake -- when I said "all matching rows would form the bitmap" I meant "all matching rows would form '1's in the bitmap". :) Gotta work on clarity of my messages. Regards, Dawid ---(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
Re: [HACKERS] Implementing Bitmap Indexes
On Sat, 29 Jan 2005 18:46:44 +, Mike Rylander <[EMAIL PROTECTED]> wrote: > As a side note, wouldn't the in-memory bitmaps pretty much kill the > need for multicolumn indexes? It seems that they would be able to > join index scans on the same table, and then there would be no need > for industrial strength cross-column correlation stats. The planner > would be able to choose a multi index scan based on multiple single > column stat entries and completely sidestep the need for precalculated > cross-column correlations. Am I getting that right? I'm not too sure of that. Lets imagine big table with two columns, a and b. If we use multicolumn index (a,b), the search must go through a tree, find a value, and from there find b value. With in-memory bitmap, the search would start with index a, all matching rows would form the bitmap; then the second search would go through b index, forming another bitmap. Which then would be ANDed with previous bitmap. If I am correct, in case of in-memory bitmap PostgreSQL would have to read more index tuples (the less unique values, the more tuples to read) which in majority of cases would mean more work than multicolumn index. However in-memory bitmap would speed up many other cases (think: OR), but multicolumn indexes are there to stay. :) Regards, Dawid ---(end of broadcast)--- TIP 9: the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] Implementing Bitmap Indexes
On Sat, 29 Jan 2005 19:41:20 +0200, Victor Y. Yegorov <[EMAIL PROTECTED]> wrote: > * Paweï Niewiadomski <[EMAIL PROTECTED]> [29.01.2005 17:45]: > > > I'd like to implement bitmap indexes and want your comments. Here is > > > an essence of what I've found regarding bitmaps for the last month. > > > > Do you think it would be possible to work on it as a team? > > Yes, why not. > > But everything depends on the community, may bitmaps will be realized as a > contrib or pgfoundry module. The only thing --- I don't know, if that is > possible for indexes. For on-disk bitmap indexes, yes. I don't see any reason this couldn't be done with GiST, perhaps even as a generalization of the index stuff in the int_array contrib module. But the bitmaps that Tom as been advocating, the ones used to join two index scans, will require a new planner Op. As a side note, wouldn't the in-memory bitmaps pretty much kill the need for multicolumn indexes? It seems that they would be able to join index scans on the same table, and then there would be no need for industrial strength cross-column correlation stats. The planner would be able to choose a multi index scan based on multiple single column stat entries and completely sidestep the need for precalculated cross-column correlations. Am I getting that right? -- Mike Rylander [EMAIL PROTECTED] GPLS -- PINES Development Database Developer http://open-ils.org ---(end of broadcast)--- TIP 6: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] Implementing Bitmap Indexes
* Paweï Niewiadomski <[EMAIL PROTECTED]> [29.01.2005 17:45]: > > I'd like to implement bitmap indexes and want your comments. Here is > > an essence of what I've found regarding bitmaps for the last month. > > Do you think it would be possible to work on it as a team? Yes, why not. But everything depends on the community, may bitmaps will be realized as a contrib or pgfoundry module. The only thing --- I don't know, if that is possible for indexes. -- Victor Y. Yegorov ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [HACKERS] Implementing Bitmap Indexes
* Tom Lane <[EMAIL PROTECTED]> [29.01.2005 18:24]: > "Victor Y. Yegorov" <[EMAIL PROTECTED]> writes: > > I remember, Tom Lane suggested on-disk bitmaps > > I have suggested no such thing, and in fact believe that the sort of > index structure you are proposing would be of very little use. Why? I thought they would be useful for data warehouse databases. Maybe I said something "the wrong way", but what I'm trying to implement is exactly what is said about in the first link you've posted below: http://archives.postgresql.org/pgsql-hackers/2004-10/msg00439.php Or am I misunderstanding the point? > What I've been hoping to look into is *in memory* bitmaps used as an > interface between index scans and the subsequent heap lookups. Sorry, that was what I've been speaking of. Anyway, bitmap indexes API could be used for in-memory bitmaps you're speaking of. -- Victor Y. Yegorov ---(end of broadcast)--- TIP 8: explain analyze is your friend
Re: [HACKERS] Implementing Bitmap Indexes
"Victor Y. Yegorov" <[EMAIL PROTECTED]> writes: > I remember, Tom Lane suggested on-disk bitmaps I have suggested no such thing, and in fact believe that the sort of index structure you are proposing would be of very little use. What I've been hoping to look into is *in memory* bitmaps used as an interface between index scans and the subsequent heap lookups. See eg this thread: http://archives.postgresql.org/pgsql-hackers/2004-10/msg00439.php particularly http://archives.postgresql.org/pgsql-hackers/2004-10/msg00668.php regards, tom lane ---(end of broadcast)--- TIP 8: explain analyze is your friend
