Re: [HACKERS] On-disk bitmap index patch
Tom Lane wrote: Both of these pages say up front that they are considering read-only data. Can I assume read-mostly partitions could use the read-I/O efficient indexes on update-intensive partitions of the same table could use b-tree indexes? All of my larger (90GB+) tables can have partitions that are either almost read-only (spatial data updated one state/country at a time, about quarterly) or are totally read-only (previous months and years historical data). So one of the questions that has to be answered (and the submitters have been entirely mum about) is exactly how bad is the update performance? If it's really awful that's going to constrain the use cases quite a lot, whereas merely a bit slower than btree wouldn't be such a problem. Once we have easy-to-use partitioning, would it be the case that many larger tables will have near-read-only partitions that could use I/O friendlier indexes (GIN? Hash? Bitmap?)? Any examples of a large data set that can't be partitioned into hot areas and read-mostly areas? ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] On-disk bitmap index patch
Luke Lonergan wrote: Mark, -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Sent: Friday, July 28, 2006 9:26 PM But irrefutable? Irrefutable is not true. :-) How about unrefuted. The evidence has not been refuted, and not directly discussed or discounted. BTREE can not be optimized to produce the results we've presented, the discussion about char(n) datatypes was irrelevant as we had shown results for INT, numeric and char/varchar and they were all dramatically better than BTREE. I am hopeful this discussion takes a rapid turn toward the quantitative assessment of the results. Right. People need a patch to test on their workloads, and analysis can be done after feature freeze. -- Bruce Momjian [EMAIL PROTECTED] EnterpriseDBhttp://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. + ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
Bruce, On 7/29/06 6:31 AM, Bruce Momjian [EMAIL PROTECTED] wrote: Right. People need a patch to test on their workloads, and analysis can be done after feature freeze. Fair enough. - Luke ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
On Thu, Jul 27, 2006 at 09:13:21AM -0700, Jie Zhang wrote: On 7/26/06 11:50 PM, Tom Lane [EMAIL PROTECTED] wrote: Jie Zhang [EMAIL PROTECTED] writes: On 7/26/06 10:14 PM, Tom Lane [EMAIL PROTECTED] wrote: ... A nonuniform distribution would probably mean that some of the bitmaps compress better-than-expected and others worse. I have no idea how to model that and guess what the overall result is ... The paper Optimizing Bitmap Indices With Efficient Compression by Kesheng Wu et al gave an approximate answer for this question. Assume that there are c distinct values. Let the i-th value has a probability of p_i, the number of rows r, and the word size w. then the total size of the compressed bitmap index is about (N/(w-1))(c- \sum(1-p_i)^(2w-2) - \sum(p_i)^(2w-2)), where in both \sum's, i is from 1 to c. Hm, but that's still begging the question no? It's still assuming that any one value is uniformly distributed. ISTM the cases that would break my simplistic calculation involve clustering of particular values, such that some areas of the bitmap are all-zero while other areas have lots of ones. Yes, you are right -- each value is still uniformly distributed. But this will be the worst case in terms of the size of a bitmap vector. As for how to model the size of a bitmap vector for an non-uniformly distributed value, that's a good question. I don't really know. But we do know the best case and the worse case. If the usefulness of bitmap indexes is still in doubt, could someone at Greenplum provide data from actual data warehouses from actual customers? -- Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED] Pervasive Software http://pervasive.comwork: 512-231-6117 vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461 ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] On-disk bitmap index patch
Jim, On 7/28/06 10:17 AM, Jim C. Nasby [EMAIL PROTECTED] wrote: If the usefulness of bitmap indexes is still in doubt, could someone at Greenplum provide data from actual data warehouses from actual customers? First, is anyone in doubt? - Luke ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
Luke Lonergan wrote: Jim, On 7/28/06 10:17 AM, Jim C. Nasby [EMAIL PROTECTED] wrote: If the usefulness of bitmap indexes is still in doubt, could someone at Greenplum provide data from actual data warehouses from actual customers? First, is anyone in doubt? Sure. I think we are going to have to see the final patch and have users test it with their workload to find the useful range. -- Bruce Momjian [EMAIL PROTECTED] EnterpriseDBhttp://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. + ---(end of broadcast)--- TIP 1: 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] On-disk bitmap index patch
-Original Message- From: [EMAIL PROTECTED] [mailto:pgsql-hackers- [EMAIL PROTECTED] On Behalf Of Luke Lonergan Sent: Friday, July 28, 2006 12:18 PM To: Jim C. Nasby; Jie Zhang Cc: Tom Lane; Mark Kirkwood; Josh Berkus; Gavin Sherry; pgsql- [EMAIL PROTECTED] Subject: Re: [HACKERS] On-disk bitmap index patch Jim, On 7/28/06 10:17 AM, Jim C. Nasby [EMAIL PROTECTED] wrote: If the usefulness of bitmap indexes is still in doubt, could someone at Greenplum provide data from actual data warehouses from actual customers? First, is anyone in doubt? Others have looked into the usefulness of bitmap indexes. Here is what they found: http://www.oracle.com/technology/pub/articles/sharma_indexes.html http://citeseer.ist.psu.edu/stockinger02bitmap.html Oracle, IBM, and even Microsoft[1] supports them. Probably not just to be trendy. [1] Microsoft SQL Server creates temporary bitmap indexes during some queries, though you cannot declaratively create a bitmap index. - Luke ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
Dann Corbit [EMAIL PROTECTED] writes: Others have looked into the usefulness of bitmap indexes. Here is what they found: http://www.oracle.com/technology/pub/articles/sharma_indexes.html I like this guy's style of argument: he admits a bitmap index on a unique column will be much bigger than a btree, and then airily dismisses it as not a problem. Not real convincing. http://citeseer.ist.psu.edu/stockinger02bitmap.html Both of these pages say up front that they are considering read-only data. So one of the questions that has to be answered (and the submitters have been entirely mum about) is exactly how bad is the update performance? If it's really awful that's going to constrain the use cases quite a lot, whereas merely a bit slower than btree wouldn't be such a problem. In any case, arguing that other DBs find it's a win will cut no ice with me. See adjacent discussion about hash indexes --- those *ought* to be a win, but they aren't in Postgres, for reasons that are still guesses. The translation gap between other DBs' experience and ours can be large. regards, tom lane ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
What we don't want to happen is for us to release bitmapped indexes, and find out later that btree is better in all cases. Then we have to tell people not to use bitmapped indexes until we fix it in the next major releasse. FYI, that is basically where we are right now with hash indexes. --- Tom Lane wrote: Dann Corbit [EMAIL PROTECTED] writes: Others have looked into the usefulness of bitmap indexes. Here is what they found: http://www.oracle.com/technology/pub/articles/sharma_indexes.html I like this guy's style of argument: he admits a bitmap index on a unique column will be much bigger than a btree, and then airily dismisses it as not a problem. Not real convincing. http://citeseer.ist.psu.edu/stockinger02bitmap.html Both of these pages say up front that they are considering read-only data. So one of the questions that has to be answered (and the submitters have been entirely mum about) is exactly how bad is the update performance? If it's really awful that's going to constrain the use cases quite a lot, whereas merely a bit slower than btree wouldn't be such a problem. In any case, arguing that other DBs find it's a win will cut no ice with me. See adjacent discussion about hash indexes --- those *ought* to be a win, but they aren't in Postgres, for reasons that are still guesses. The translation gap between other DBs' experience and ours can be large. regards, tom lane ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings -- Bruce Momjian [EMAIL PROTECTED] EnterpriseDBhttp://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. + ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] On-disk bitmap index patch
Bruce, On 7/28/06 1:25 PM, Bruce Momjian [EMAIL PROTECTED] wrote: What we don't want to happen is for us to release bitmapped indexes, and find out later that btree is better in all cases. Then we have to tell people not to use bitmapped indexes until we fix it in the next major releasse. FYI, that is basically where we are right now with hash indexes. On this thread people have presented results that show clear and irrefutable evidence that there are use cases where bitmap indexes outperform Btree for many datatypes on realistic problems, including the TPC-H benchmark. In many cases the bitmap indexes outperform BTREE by a factor of 50 and are a tiny fraction of the size and also take dramatically less time to build. Of the cases presented, we need to have someone specifically address them and point out why they aren't proof of bitmap index performance. So far this has not been done, rather there are some unsupported opinions about other cases that might be problematic. - Luke ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] On-disk bitmap index patch
Tom Lane wrote: Both of these pages say up front that they are considering read-only data. So one of the questions that has to be answered (and the submitters have been entirely mum about) is exactly how bad is the update performance? If it's really awful that's going to constrain the use cases quite a lot, whereas merely a bit slower than btree wouldn't be such a problem. In any case, arguing that other DBs find it's a win will cut no ice with me. See adjacent discussion about hash indexes --- those *ought* to be a win, but they aren't in Postgres, for reasons that are still guesses. The translation gap between other DBs' experience and ours can be large. Notwithstanding that, I have a couple of non-postgres data points / anecdotes on this. Back in my days as an Ingres DBA in the mid 90s, our fairly highly tuned system used hash organised tables only for small fairly static lookup-type tables (state codes, postcodes, etc). Everything that was more dynamic was done with btree indexed tables. A few years later, I was producing very large tables of email addresses using BDB. I quickly stopped using hash tables when I found that the reorganisation penalty was huge. Switching to btree worked just fine, with no sudden performance blip. This might not be directly relevant, but clearly the bucket size is. I guess what we need to demonstrate is that the better hash performance will actually persist to a scale where it is actually worth it - surely for very small tables the index method won't matter much anyway. cheers andrew ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
Ühel kenal päeval, R, 2006-07-28 kell 16:18, kirjutas Tom Lane: Dann Corbit [EMAIL PROTECTED] writes: Others have looked into the usefulness of bitmap indexes. Here is what they found: http://www.oracle.com/technology/pub/articles/sharma_indexes.html I like this guy's style of argument: he admits a bitmap index on a unique column will be much bigger than a btree, and then airily dismisses it as not a problem. Not real convincing. This problem can be easyly avoided by not creating bitmap indexes on unique columns. So I think it is ok to dismiss it. http://citeseer.ist.psu.edu/stockinger02bitmap.html Both of these pages say up front that they are considering read-only data. So one of the questions that has to be answered (and the submitters have been entirely mum about) is exactly how bad is the update performance? If it's really awful that's going to constrain the use cases quite a lot, whereas merely a bit slower than btree wouldn't be such a problem. May be. OTOH, in OLAP databases you may be better off dropping the indexes before data loading and rebuilding them after. And it has been shown that bitmap indexes build a lot faster than btrees. In any case, arguing that other DBs find it's a win will cut no ice with me. How about a more general argument. I claim that an index that is small and fits in RAM is faster than a big one that does not fit in RAM. See adjacent discussion about hash indexes --- those *ought* to be a win, but they aren't in Postgres, for reasons that are still guesses. The translation gap between other DBs' experience and ours can be large. IIRC the tests showing bitmap indexes being much faster on TPC-H were done on postgresql, no ? You pointed out that btree indexes are more bloated in this case as they store padding spaces for all CHAR(N) fields whereas bitmap index stores padding spaces only once for each distinct value. Are there any plans to start optimising btree storage model in forseeable future ? -- Hannu Krosing Database Architect Skype Technologies OÜ Akadeemia tee 21 F, Tallinn, 12618, Estonia Skype me: callto:hkrosing Get Skype for free: http://www.skype.com ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] On-disk bitmap index patch
Ühel kenal päeval, R, 2006-07-28 kell 16:25, kirjutas Bruce Momjian: What we don't want to happen is for us to release bitmapped indexes, and find out later that btree is better in all cases. Actually I'd love it if adding bitmap indexes to core pg would magically make btree several times faster for the cases where bitmap indexes are faster now :) -- Hannu Krosing Database Architect Skype Technologies OÜ Akadeemia tee 21 F, Tallinn, 12618, Estonia Skype me: callto:hkrosing Get Skype for free: http://www.skype.com ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
On Fri, Jul 28, 2006 at 02:43:23PM -0700, Luke Lonergan wrote: On 7/28/06 1:25 PM, Bruce Momjian [EMAIL PROTECTED] wrote: What we don't want to happen is for us to release bitmapped indexes, and find out later that btree is better in all cases. Then we have to tell people not to use bitmapped indexes until we fix it in the next major releasse. FYI, that is basically where we are right now with hash indexes. On this thread people have presented results that show clear and irrefutable evidence that there are use cases where bitmap indexes outperform Btree for many datatypes on realistic problems, including the TPC-H benchmark. Irrefutable is a little optimistic, don't you think? :-) There is reason to believe that a bitmap index is useful in some scenarios. We're not yet clear on what these are, whether they apply to production use scenarios, or whether b-tree could not be optimized to be better. I support you - I want to see these great things for myself. But irrefutable? Irrefutable is not true. :-) Cheers, mark -- [EMAIL PROTECTED] / [EMAIL PROTECTED] / [EMAIL PROTECTED] __ . . _ ._ . . .__. . ._. .__ . . . .__ | Neighbourhood Coder |\/| |_| |_| |/|_ |\/| | |_ | |/ |_ | | | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness bind them... http://mark.mielke.cc/ ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
Mark, -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Sent: Friday, July 28, 2006 9:26 PM But irrefutable? Irrefutable is not true. :-) How about unrefuted. The evidence has not been refuted, and not directly discussed or discounted. BTREE can not be optimized to produce the results we've presented, the discussion about char(n) datatypes was irrelevant as we had shown results for INT, numeric and char/varchar and they were all dramatically better than BTREE. I am hopeful this discussion takes a rapid turn toward the quantitative assessment of the results. - Luke ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
On 7/26/06 10:14 PM, Tom Lane [EMAIL PROTECTED] wrote: Mark Kirkwood [EMAIL PROTECTED] writes: An obvious deduction is that the TPCH dataset is much more amenable to run compression than my synthetic Zipfian data was. The interesting question is how well real datasets are run compressable, Yeah --- the back-of-the-envelope calculations I was making presupposed uniform random distribution, and we know that's often not realistic for real datasets. A nonuniform distribution would probably mean that some of the bitmaps compress better-than-expected and others worse. I have no idea how to model that and guess what the overall result is ... The paper Optimizing Bitmap Indices With Efficient Compression by Kesheng Wu et al gave an approximate answer for this question. Assume that there are c distinct values. Let the i-th value has a probability of p_i, the number of rows r, and the word size w. then the total size of the compressed bitmap index is about (N/(w-1))(c- \sum(1-p_i)^(2w-2) - \sum(p_i)^(2w-2)), where in both \sum's, i is from 1 to c. The constraint for this equation is \sum(p_i)=1. Therefore, when all p_i are equal, or the attribute has randomly distributed values, the size of the bitmap index is the largest. ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] On-disk bitmap index patch
Jie Zhang [EMAIL PROTECTED] writes: On 7/26/06 10:14 PM, Tom Lane [EMAIL PROTECTED] wrote: ... A nonuniform distribution would probably mean that some of the bitmaps compress better-than-expected and others worse. I have no idea how to model that and guess what the overall result is ... The paper Optimizing Bitmap Indices With Efficient Compression by Kesheng Wu et al gave an approximate answer for this question. Assume that there are c distinct values. Let the i-th value has a probability of p_i, the number of rows r, and the word size w. then the total size of the compressed bitmap index is about (N/(w-1))(c- \sum(1-p_i)^(2w-2) - \sum(p_i)^(2w-2)), where in both \sum's, i is from 1 to c. Hm, but that's still begging the question no? It's still assuming that any one value is uniformly distributed. ISTM the cases that would break my simplistic calculation involve clustering of particular values, such that some areas of the bitmap are all-zero while other areas have lots of ones. regards, tom lane ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] On-disk bitmap index patch
On 7/26/06 11:50 PM, Tom Lane [EMAIL PROTECTED] wrote: Jie Zhang [EMAIL PROTECTED] writes: On 7/26/06 10:14 PM, Tom Lane [EMAIL PROTECTED] wrote: ... A nonuniform distribution would probably mean that some of the bitmaps compress better-than-expected and others worse. I have no idea how to model that and guess what the overall result is ... The paper Optimizing Bitmap Indices With Efficient Compression by Kesheng Wu et al gave an approximate answer for this question. Assume that there are c distinct values. Let the i-th value has a probability of p_i, the number of rows r, and the word size w. then the total size of the compressed bitmap index is about (N/(w-1))(c- \sum(1-p_i)^(2w-2) - \sum(p_i)^(2w-2)), where in both \sum's, i is from 1 to c. Hm, but that's still begging the question no? It's still assuming that any one value is uniformly distributed. ISTM the cases that would break my simplistic calculation involve clustering of particular values, such that some areas of the bitmap are all-zero while other areas have lots of ones. Yes, you are right -- each value is still uniformly distributed. But this will be the worst case in terms of the size of a bitmap vector. As for how to model the size of a bitmap vector for an non-uniformly distributed value, that's a good question. I don't really know. But we do know the best case and the worse case. ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] On-disk bitmap index patch
I find those results moderately unconvincing, primarily because they are based on choosing the least efficient possible data representation (viz char(n)), and thus the btree indexes suffer severe and quite artificial bloat. A database schema chosen with even minimal attention The specific data was chosen in presentation, because it comes from TPC-H definition (data that everybody understands) and they were the only columns where bitmap index will be more beneficial (i.e. the columns were low cardinality ones). to PG-specific tuning would probably have btree indexes half the size. That wouldn't completely eliminate the performance differential shown, but it would bring it down into the ballpark where you have to question whether it makes sense to support another index AM. Comparison of index creation time and index size for similar cardinalities for *integer* and *numeric* data-types for b-tree and bitmap index. Benefits are seen in all the cases, index creation time, space taken by index as well as querying: Total rows in the table: 2 million Size of table in kbytes: 431976 Table definition and column cardinalities: Column | Type| Cardinality +---+--- c1 | integer | i10| integer | 10 i50| integer | 50 n10| numeric | 10 n50| numeric | 50 ctext | character varying | Note: Time in seconds and size in kbytes (as seen from select pg_relation_size()): - Column B-tree size Bitmap size B-tree time Bitmap time - i10 35056 239211.86.0 i50 35056 432810.86.4 n10 52264 265634.89.6 n50 52616 427234.311.7 - Query timings (in seconds): - Query B-tree Bitmap - select count(*) from btree_test where 4.081.61 i10=5 and i50=2 and n10=0.1 and n50=0.05; - This test case fits in memory, the benefits seen will be more if we take bigger test case. I will like to re-iterate the benefits of bitmap index: 1. Size and time to create bitmap index is less than b-tree index for low cardinality column of any data-type. 2. The gain in query performance can be attributed to Bitmap And¹ and Bitmap Or¹ operations being more efficient for bitmap indexes as compared to b-trees. Note that both bitmap and b-tree indexes use the bitmap index scan access method, however the behavior is different for each. With a b-tree index, the b-tree indexes are scanned to create a temporary in-memory bitmap index. With the Bizgres on-disk bitmap index, the bitmap scan retrieves several on-disk bitmap pages at once and provides them to the Bitmap And¹ and Bitmap Or¹ operators. The smaller size of the bitmap indexes combined with the efficiency of the And and Or operators are the reasons for the increase in query speed. Ayush ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] On-disk bitmap index patch
I wrote: ... A realistic assumption for the numbers you mention is that the bitmaps have 1-bits about 100 bits apart, which means you could get maybe 3-to-1 compression using the runlength scheme that's in there ... leaving the bitmap a factor of 20 bigger than the btree. I'm surprised no one caught me making this bogus computation. I realized this morning it's wrong: if there are 1 distinct values then on the average the 1-bits would be about 1 bits apart, not 100. At that rate there *is* substantial compression. The representation used in the bitmap patch isn't amazingly efficient for this (I wonder whether they oughtn't use 16-bit instead of 8-bit HRL_WORDs) but it still manages to get down to something like 11 bytes per 1-bit. Since each 1-bit corresponds to a btree entry, this means the bitmap does come out somewhat smaller than a btree (16 bytes per entry ignoring overhead) --- at least if overhead such as wasted space on a page doesn't kill it. Still, this isn't going to make the difference between fitting in RAM or not. For small numbers of distinct values, like less than 100, the bitmap representation looks more plausible. In that range you're down to a byte or two per entry and so there is (very roughly) a 10x storage savings over btree. I don't believe the 100x numbers that have been bandied around in this discussion, but 10x is plenty enough to be interesting. regards, tom lane ---(end of broadcast)--- TIP 1: 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] On-disk bitmap index patch
Tom Lane wrote: I'm surprised no one caught me making this bogus computation. I realized this morning it's wrong: if there are 1 distinct values then on the average the 1-bits would be about 1 bits apart, not 100. Right - I didn't think 1 was *that* bad, but was too sleepy to try working it out :-). I don't believe the 100x numbers that have been bandied around in this discussion, but 10x is plenty enough to be interesting. Yep - I have not managed to get 100x in any of my tests. However, I do see some about half that for the TPCH scale 10 dataset: tpch=# \i relsizes.sql(BTREE) relname | relpages +-- customer |41019 customer_c_custkey | 3288 customer_c_mktsegment | 5779 customer_c_nationkey | 3288 lineitem | 1535724 lineitem_l_linenumber | 131347 lineitem_l_orderkey| 131347 orders | 307567 orders_o_custkey |32847 orders_o_orderpriority |65876 orders_o_orderstatus |41131 tpch=# \i relsizes.sql(MAINLY BITMAP) relname | relpages +-- customer |41019 customer_c_custkey | 3288 customer_c_mktsegment | 157 customer_c_nationkey | 336 lineitem | 1535724 lineitem_l_linenumber | 7571 lineitem_l_orderkey| 131347 orders | 307567 orders_o_custkey |32847 orders_o_orderpriority | 1427 orders_o_orderstatus | 717 The orders_o_orderpriority and orders_o_orderstatus bitmap indexes are 46 and 57 times smaller than their btree counterparts (hmm...might we see even better compression for larger scale factors?). An obvious deduction is that the TPCH dataset is much more amenable to run compression than my synthetic Zipfian data was. The interesting question is how well real datasets are run compressable, I suspect better than my Zipfian data is a safe assumption! Cheers Mark ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
Tom, On 7/26/06 7:26 AM, Tom Lane [EMAIL PROTECTED] wrote: I wonder whether they oughtn't use 16-bit instead of 8-bit HRL_WORDs We tried variations from 8-bit to 32-bit and came to the conclusion that 8-bit was a better match for the more general case. For the moment I forget exactly why (maybe Jie or Ayush will recall). It's a #define I believe, so you can play with it to find out. There's a lot more to be done with this - I think we've got some big gains ahead. BTW - lots of excitement here at OSCON about bitmap index, and there's a fellow who is using the current Bizgres version, but wants *higher* cardinality support, so I discussed Jie's thoughts about implementing binning on values, basically combining bit vectors into value bins as the cardinality increases. I am still puzzled why our index creation time increases so dramatically as we approach cardinality 10,000. I know that we found that index page traversal for append began to take a lot of time as we started to increase the number of bitvector pages - we had talked about aggregating the append operations into groups before they were implemented to sequentialize the access. - Luke ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
On 7/26/06 8:55 PM, Luke Lonergan [EMAIL PROTECTED] wrote: Tom, On 7/26/06 7:26 AM, Tom Lane [EMAIL PROTECTED] wrote: I wonder whether they oughtn't use 16-bit instead of 8-bit HRL_WORDs We tried variations from 8-bit to 32-bit and came to the conclusion that 8-bit was a better match for the more general case. For the moment I forget exactly why (maybe Jie or Ayush will recall). It's a #define I believe, so you can play with it to find out. There's a lot more to be done with this - I think we've got some big gains ahead. For low-cardinality cases, 8-bit word size is usually better than 16-bit and 32-bit. The reason is that in this case, the compression is better in 8-bit than in 16-bit or 32-bit. But for high-cardinality cases, like 10,000, 16-bit is better. That's because a compressed 8-bit can only represent at most 2^7*8=1024 bits. So every 10,000 bits requires about 10 bytes. However, a compressed 16-bit can represent 2^15*16=524288 bits. We only need 2 bytes. I have been thinking about this recently -- maybe we can support different word sizes for different cardinalities. BTW - lots of excitement here at OSCON about bitmap index, and there's a fellow who is using the current Bizgres version, but wants *higher* cardinality support, so I discussed Jie's thoughts about implementing binning on values, basically combining bit vectors into value bins as the cardinality increases. Yes, that's the basic idea. Essentially we want to limit the number of bins into an ideal value so that (1) the size of the bitmap index can be small; (2) this will still guarantee good query performance. The details still need to be working out. I am still puzzled why our index creation time increases so dramatically as we approach cardinality 10,000. I know that we found that index page traversal for append began to take a lot of time as we started to increase the number of bitvector pages - we had talked about aggregating the append operations into groups before they were implemented to sequentialize the access. I believe that this is because of 8-bit word size. We can try to increase it to 16-bit, and see how the result looks like. Thanks, Jie ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] On-disk bitmap index patch
Mark Kirkwood [EMAIL PROTECTED] writes: An obvious deduction is that the TPCH dataset is much more amenable to run compression than my synthetic Zipfian data was. The interesting question is how well real datasets are run compressable, Yeah --- the back-of-the-envelope calculations I was making presupposed uniform random distribution, and we know that's often not realistic for real datasets. A nonuniform distribution would probably mean that some of the bitmaps compress better-than-expected and others worse. I have no idea how to model that and guess what the overall result is ... regards, tom lane ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
I think we do know, have you reviewed the results in the briefing? - Luke Sent from my GoodLink synchronized handheld (www.good.com) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Sent: Tuesday, July 25, 2006 01:09 AM Eastern Standard Time To: Tom Lane Cc: Bruce Momjian; Jie Zhang; Hannu Krosing; Gavin Sherry; pgsql-hackers@postgresql.org; Luke Lonergan Subject:Re: [HACKERS] On-disk bitmap index patch On Tue, Jul 25, 2006 at 12:36:42AM -0400, Tom Lane wrote: [EMAIL PROTECTED] writes: Reading 1/4, for a larger table, has a good chance of being faster than reading 4/4 of the table. :-) Really? If you have to hit one tuple out of four, it's pretty much guaranteed that you will need to fetch every heap page. So using an index provides zero I/O savings on the heap side, and any fetches needed to read the index are pure cost. Now you have to demonstrate that the CPU costs involved in processing the index are significantly cheaper than the cost of just testing the WHERE qual at every heap tuple --- not a bet that's likely to win at a one-in-four ratio. Haha. Of course - but that's assuming uniform spread of the values. Next I would try clustering the table on the bitmap index... :-) My databases aren't as large as many of yours. Most or all of them will fit in 1 Gbytes of RAM. The I/O cost isn't substantial for these, but the WHERE clause might be. But yeah - we don't know. Waste of code or performance boost. Cheers, mark -- [EMAIL PROTECTED] / [EMAIL PROTECTED] / [EMAIL PROTECTED] __ . . _ ._ . . .__. . ._. .__ . . . .__ | Neighbourhood Coder |\/| |_| |_| |/|_ |\/| | |_ | |/ |_ | | | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness bind them... http://mark.mielke.cc/ ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
Luke Lonergan [EMAIL PROTECTED] writes: I think we do know, have you reviewed the results in the briefing? I find those results moderately unconvincing, primarily because they are based on choosing the least efficient possible data representation (viz char(n)), and thus the btree indexes suffer severe and quite artificial bloat. A database schema chosen with even minimal attention to PG-specific tuning would probably have btree indexes half the size. That wouldn't completely eliminate the performance differential shown, but it would bring it down into the ballpark where you have to question whether it makes sense to support another index AM. The reason I have such high sales resistance is that we've carried the hash and rtree AMs for years, hoping that someone would do the work to make them actually worth using, with little result. I don't want any more second-class-citizen index AMs, and that's why I'm questioning what the scope of applicability of bitmap indexes really is. They need to be popular enough that people will be motivated to work on them, or they shouldn't be in core. regards, tom lane ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] On-disk bitmap index patch
On Sun, Jul 23, 2006 at 05:35:37PM -0700, Luke Lonergan wrote: We presented them at the Postgres Anniversary summit talk (Bruce M. was there) and the reaction was let's get this into 8.2 because many people there (more than 5) really wanted to use it as a standard feature. A version of the slides with only the bitmap index results are located here: http://intranet.greenplum.com/bitmap-index-perf-ayush.ppt. 404 -- Jim C. Nasby, Sr. Engineering Consultant [EMAIL PROTECTED] Pervasive Software http://pervasive.comwork: 512-231-6117 vcard: http://jim.nasby.net/pervasive.vcf cell: 512-569-9461 ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
Ühel kenal päeval, T, 2006-07-25 kell 12:49, kirjutas Jim C. Nasby: On Sun, Jul 23, 2006 at 05:35:37PM -0700, Luke Lonergan wrote: We presented them at the Postgres Anniversary summit talk (Bruce M. was there) and the reaction was let's get this into 8.2 because many people there (more than 5) really wanted to use it as a standard feature. A version of the slides with only the bitmap index results are located here: http://intranet.greenplum.com/bitmap-index-perf-ayush.ppt. 404 Strange. I can download it both from my work and home . -- Hannu Krosing Database Architect Skype Technologies OÜ Akadeemia tee 21 F, Tallinn, 12618, Estonia Skype me: callto:hkrosing Get Skype for free: http://www.skype.com ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] On-disk bitmap index patch
Ühel kenal päeval, T, 2006-07-25 kell 13:06, kirjutas Tom Lane: Luke Lonergan [EMAIL PROTECTED] writes: I think we do know, have you reviewed the results in the briefing? I find those results moderately unconvincing, primarily because they are based on choosing the least efficient possible data representation (viz char(n)), and thus the btree indexes suffer severe and quite artificial bloat. hmm, maybe this should be fixed in btree then ? do we really need to store padding blanks in btree ? A database schema chosen with even minimal attention to PG-specific tuning would probably have btree indexes half the size. That wouldn't completely eliminate the performance differential shown, but it would bring it down into the ballpark where you have to question whether it makes sense to support another index AM. It still depends on your data volumes. if you spend lots and lots of $ on hardware just to store surplus index bloat, it may be worth it. Remember, that the bizgres folks develop these things for real-world datawarehousing, where saving a few (tens or hundreds of) terabytes of storage and corresponging amount of RAM is a real win. The reason I have such high sales resistance is that we've carried the hash and rtree AMs for years, hoping that someone would do the work to make them actually worth using, with little result. What would be the use-case for hash indexes ? And what should be done to make them faster than btree ? I know that they are not wal-logged, but this is beside the point for DWH apps. and was'nt the rtree index recently deprecated in favour of GIST implementation of the same ? I don't want any more second-class-citizen index AMs, and that's why I'm questioning what the scope of applicability of bitmap indexes really is. They need to be popular enough that people will be motivated to work on them, or they shouldn't be in core. Is there an easy way to put them into contrib/ for some test period so that they can become popular among mainstream postgresql users ? -- Hannu Krosing Database Architect Skype Technologies OÜ Akadeemia tee 21 F, Tallinn, 12618, Estonia Skype me: callto:hkrosing Get Skype for free: http://www.skype.com ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] On-disk bitmap index patch
Tom, (I'm also wondering whether this doesn't overlap the use-case for GIN.) It does not. GIN is strictly for multi-value fields. I can think of applications where either GIN or Bitmaps would be an option, but for the majority, they wouldn't. One particular compelling situation for on-disk bitmaps is for terabyte tables where a btree index would not fit into memory. Index performance for an index which is 10x or more the size of RAM really sucks ... I can come up with some test results if you doubt that. Also note that low cardinality is relative. For a 1 billion row table, a column with 10,000 values is low-cardinality, having around 100,000 rows per value ... but that's still 0.01% of the table per value, making index use still applicable. --Josh ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
Hannu Krosing [EMAIL PROTECTED] writes: Ãhel kenal päeval, T, 2006-07-25 kell 13:06, kirjutas Tom Lane: The reason I have such high sales resistance is that we've carried the hash and rtree AMs for years, hoping that someone would do the work to make them actually worth using, with little result. What would be the use-case for hash indexes ? And what should be done to make them faster than btree ? If we knew, we'd do it ;-) But no one's put enough effort into it to find out. and was'nt the rtree index recently deprecated in favour of GIST implementation of the same ? Yeah, we finally gave up on rtree entirely. I don't want to see any other index AMs languishing in the closet like that. If bitmap can hold its own to the extent that people are interested in working on it/improving it, then great, but I'm worried that it's not going to have a wide enough use-case to attract maintainers. regards, tom lane ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] On-disk bitmap index patch
Tom, On 7/25/06 1:31 PM, Tom Lane [EMAIL PROTECTED] wrote: Yeah, we finally gave up on rtree entirely. I don't want to see any other index AMs languishing in the closet like that. If bitmap can hold its own to the extent that people are interested in working on it/improving it, then great, but I'm worried that it's not going to have a wide enough use-case to attract maintainers. How do we close the gap? I think Jie is interested in maintaining it, and we're looking to extend the range of applications for both the AM and extensions that use the raw bitmap comparators made available to the executor. This should be just the start of some really great work on speedy access using bitmaps. Even as it sits, the on-disk bitmap is over 100x faster in cases where it's suited and the other commercial DBMS have had this popular feature for years. - Luke ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] On-disk bitmap index patch
Josh Berkus josh@agliodbs.com writes: One particular compelling situation for on-disk bitmaps is for terabyte tables where a btree index would not fit into memory. Index performance for an index which is 10x or more the size of RAM really sucks ... I can come up with some test results if you doubt that. Sure... Also note that low cardinality is relative. For a 1 billion row table, a column with 10,000 values is low-cardinality, having around 100,000 rows per value ... but that's still 0.01% of the table per value, making index use still applicable. And your point is? Assuming a reasonable datatype like int4, a btree index on this table would occupy say 20GB (16 bytes per entry plus fillfactor overhead). The bitmap version would require 10,000 bitmaps of 1G bits apiece, or 1250GB (not even counting overhead). You need some wildly optimistic assumptions about the compressibility of the bitmaps to get even within hailing distance of the btree, let alone fit in RAM. A realistic assumption for the numbers you mention is that the bitmaps have 1-bits about 100 bits apart, which means you could get maybe 3-to-1 compression using the runlength scheme that's in there ... leaving the bitmap a factor of 20 bigger than the btree. AFAICS low cardinality has to mean just that, a few dozen distinct values at most, for this scheme to have any hope. regards, tom lane ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] On-disk bitmap index patch
Tom Lane wrote: [EMAIL PROTECTED] writes: Reading 1/4, for a larger table, has a good chance of being faster than reading 4/4 of the table. :-) Really? If you have to hit one tuple out of four, it's pretty much guaranteed that you will need to fetch every heap page. I think it's not uncommon to have data that is more clustered than expected. In my case it shows up often in GIS data; where often a query that only accesses 1/4 of the rows in the table really will only access about 1/4 of the pages in the table -- for example when analyzing Texas or the Southwest US. ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] On-disk bitmap index patch
Ron Mayer [EMAIL PROTECTED] writes: Tom Lane wrote: If you have to hit one tuple out of four, it's pretty much guaranteed that you will need to fetch every heap page. I think it's not uncommon to have data that is more clustered than expected. Sure, if the data is fairly static ... and now that there's a fillfactor option for heaps, you can even tolerate (some low rate of) updates without losing the clusteredness. However, that benefit accrues to all index types not only bitmap. regards, tom lane ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
Tom Lane wrote: And your point is? Assuming a reasonable datatype like int4, a btree index on this table would occupy say 20GB (16 bytes per entry plus fillfactor overhead). The bitmap version would require 10,000 bitmaps of 1G bits apiece, or 1250GB (not even counting overhead). You need some wildly optimistic assumptions about the compressibility of the bitmaps to get even within hailing distance of the btree, let alone fit in RAM. A realistic assumption for the numbers you mention is that the bitmaps have 1-bits about 100 bits apart, which means you could get maybe 3-to-1 compression using the runlength scheme that's in there ... leaving the bitmap a factor of 20 bigger than the btree. AFAICS low cardinality has to mean just that, a few dozen distinct values at most, for this scheme to have any hope. I did a little testing of this when Jie first submitted the patch - for a basically Zipfian distribution of int4's the bitmap is still clearly smaller even at 1000 distinct values (see below). It is twice as big at 1, so the crossover point is somewhere in the 1000-1 range (for this test - however the results seem to be reasonably typical). In DSS distinct values 1000 is very common (days of week, months of year, lineitems of order, sex of animal...) so the applicability of this range is perhaps larger than it seems at first sight. Cheers Mark bitmap=# \d bitmaptest Table public.bitmaptest Column | Type | Modifiers +-+--- id | integer | not null val0 | integer | val1 | integer | val2 | integer | val3 | integer | fil| text| bitmap=# select count(distinct val0), count(distinct val1), count(distinct val2), count(distinct val3) from bitmaptest; count | count | count | count ---+---+---+--- 10 | 100 | 1000 | 1 bitmap=# \i relsizes.sql (BTREE) relname | relpages -+-- bitmaptest |93458 bitmaptest_val0 |21899 bitmaptest_val1 |21899 bitmaptest_val2 |21899 bitmaptest_val3 |21899 bitmap=# \i relsizes.sql (BITMAP) relname | relpages -+-- bitmaptest |93458 bitmaptest_val0 | 1286 bitmaptest_val1 | 2313 bitmaptest_val2 | 5726 bitmaptest_val3 |41292 For the interested, the data generator, schema, index files are here: http://homepages.paradise.net.nz/markir/download/bizgres/bitmaptest.tar.gz ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
Thanks Tom and Gavin for your comments! Yes, this patch is generated against 8.2 in a short time. As long as the code is working, I post the patch to get some comments and help. * The xlog routines need help; they seem to not be updated for recent changes in the API for xlog recovery code. Yep. The patch was actually against 8.1 and was hastily brought up to 8.2. I think Jie's intention was to simply let everyone know that this was going on. Thanks for pointing this out. I didn't notice that these are changed in 8.2. * The hacks on vacuum.c (where it tests the AM name) are utterly unacceptable. If you need the main code to do something special for a particular index AM, define a bool flag column for it in pg_am. Yes. Sounds good. * The interface to the existing executor bitmap scan code is mighty messy --- seems like there's a lot of almost duplicate code, a lot of rather invasive hacking, etc. This needs to be rethought and refactored. I agree. I will think about this more. * Why in the world is it introducing duplicate copies of a lot of btree comparison functions? Use the ones that are there. Yes, I raised this with Jie and she has fixed it. One thought is, we may want to rename those comparison functions prefixed with 'bm' to make their naming less confusing. They'll be used by btree, gin and bitmap index methods. Anyway, a seperate patch. Yeah, the main problem I hesitated to use btree's comparison functions because of those function names starting with 'bt'. Since Gavin told me that Gin is using those functions as well, I had changed them. Renaming them would be good. * The patch itself is a mess: it introduces .orig and .rej files, changes around $PostgreSQL$ lines, etc. Right, not to mention patches to configure and a lot of style which needs to be knocked into shape. The way I generate a patch is kind of clumsy. I need to find a better way to do that. I will start fixing these. Thanks, Jie ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] On-disk bitmap index patch
Ühel kenal päeval, P, 2006-07-23 kell 20:25, kirjutas Tom Lane: Gavin Sherry [EMAIL PROTECTED] writes: On Sun, 23 Jul 2006, Tom Lane wrote: However, the main problem I've got with this is that a new index AM is a pretty large burden, and no one's made the slightest effort to sell pghackers on taking this on. For low cardinality sets, bitmaps greatly out perform btree. If the column is sufficiently low cardinality, you might as well just do a seqscan --- you'll be hitting most of the heap's pages anyway. I'm still waiting to be convinced that there's a sweet spot wide enough to justify supporting another index AM. (I'm also wondering whether this doesn't overlap the use-case for GIN.) IIRC they quoted the cardinality of 1 as something that is still faster than btree for several usecases. And also for AND-s of several indexes, where indexes are BIG, your btree indexes may be almost as big as tables but the resulting set of pages is small. -- Hannu Krosing Database Architect Skype Technologies OÜ Akadeemia tee 21 F, Tallinn, 12618, Estonia Skype me: callto:hkrosing Get Skype for free: http://www.skype.com ---(end of broadcast)--- TIP 1: 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] On-disk bitmap index patch
On 7/24/06 6:59 AM, Hannu Krosing [EMAIL PROTECTED] wrote: Ühel kenal päeval, P, 2006-07-23 kell 20:25, kirjutas Tom Lane: Gavin Sherry [EMAIL PROTECTED] writes: On Sun, 23 Jul 2006, Tom Lane wrote: However, the main problem I've got with this is that a new index AM is a pretty large burden, and no one's made the slightest effort to sell pghackers on taking this on. For low cardinality sets, bitmaps greatly out perform btree. If the column is sufficiently low cardinality, you might as well just do a seqscan --- you'll be hitting most of the heap's pages anyway. I'm still waiting to be convinced that there's a sweet spot wide enough to justify supporting another index AM. (I'm also wondering whether this doesn't overlap the use-case for GIN.) IIRC they quoted the cardinality of 1 as something that is still faster than btree for several usecases. And also for AND-s of several indexes, where indexes are BIG, your btree indexes may be almost as big as tables but the resulting set of pages is small. Yeah, Hannu points it out very well -- the bitmap index works very well when columns have low cardinalities and AND operations will produce small number of results. Also, the bitmap index is very small in low cardinality cases, where the btree tends to take up at least 10 times more space. ---(end of broadcast)--- TIP 5: don't forget to increase your free space map settings
Re: [HACKERS] On-disk bitmap index patch
Jie Zhang wrote: IIRC they quoted the cardinality of 1 as something that is still faster than btree for several usecases. And also for AND-s of several indexes, where indexes are BIG, your btree indexes may be almost as big as tables but the resulting set of pages is small. Yeah, Hannu points it out very well -- the bitmap index works very well when columns have low cardinalities and AND operations will produce small number of results. What operations on columns of low cardinality produce a small number of results? That seems contradictory. Also, the bitmap index is very small in low cardinality cases, where the btree tends to take up at least 10 times more space. Also, are adding/changing rows is more expensive with bitmaps than btrees? -- Bruce Momjian [EMAIL PROTECTED] EnterpriseDBhttp://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. + ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] On-disk bitmap index patch
On 7/24/06 6:04 PM, Bruce Momjian [EMAIL PROTECTED] wrote: Jie Zhang wrote: IIRC they quoted the cardinality of 1 as something that is still faster than btree for several usecases. And also for AND-s of several indexes, where indexes are BIG, your btree indexes may be almost as big as tables but the resulting set of pages is small. Yeah, Hannu points it out very well -- the bitmap index works very well when columns have low cardinalities and AND operations will produce small number of results. What operations on columns of low cardinality produce a small number of results? That seems contradictory. Let's see an example. Table 'T' includes two columns, 'p' and 's'. The column 'p' has 100 distinct values, say p1-p100 and the column 'status' has 20 distinct values, say s1-s20. The query 'select * from order where priority=p1 and status=s1' may produce small number of results. Also, if these related rows are clustered together, that would be even better. Also, the bitmap index is very small in low cardinality cases, where the btree tends to take up at least 10 times more space. Also, are adding/changing rows is more expensive with bitmaps than btrees? Inserting a row will only affect the last word (at most last several words) of a bitmap vector, so this should not be very expensive: 3-4 IOs. When a row is updated and the new row is inserted in the middle of the heap, currently the code will update the bit in the place -- where the bit should be. Searching for the page which includes the bit to be updated is not very efficient now, but this can be fixed. Currently, we have to scan the pages for a bitmap vector one by one until we hit the right page. Since the bitmap vector is compressed, updating a bit in the middle may cause its page to overflow. In this case, we create a new page to accommodate those extra bits, and insert this new page right after the original page. Overall, inserting a row or updating a row can be done efficiently. But it is true that the bitmap index does not perform well if there are lots of inserts and updates, especially updates. ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
On Mon, 24 Jul 2006, Bruce Momjian wrote: Jie Zhang wrote: IIRC they quoted the cardinality of 1 as something that is still faster than btree for several usecases. And also for AND-s of several indexes, where indexes are BIG, your btree indexes may be almost as big as tables but the resulting set of pages is small. Yeah, Hannu points it out very well -- the bitmap index works very well when columns have low cardinalities and AND operations will produce small number of results. What operations on columns of low cardinality produce a small number of results? That seems contradictory. WHERE a = 1 and b = 2 a = 1 may be 5% of the table and b = 2 may be 5% of the table but their intersection may be .001%. Luke: the URL you sent to the bitmap slides was internal to Greenplum. Would you be able to put them on a public site? Thanks, Gavin ---(end of broadcast)--- TIP 1: 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] On-disk bitmap index patch
On Mon, Jul 24, 2006 at 09:04:28PM -0400, Bruce Momjian wrote: Jie Zhang wrote: IIRC they quoted the cardinality of 1 as something that is still faster than btree for several usecases. And also for AND-s of several indexes, where indexes are BIG, your btree indexes may be almost as big as tables but the resulting set of pages is small. Yeah, Hannu points it out very well -- the bitmap index works very well when columns have low cardinalities and AND operations will produce small number of results. What operations on columns of low cardinality produce a small number of results? That seems contradictory. Not necessarily. Cardinality of 2 means 1/2. 3 means 1/3. 4 means 1/4. Etc. Reading 1/4, for a larger table, has a good chance of being faster than reading 4/4 of the table. :-) No opinion on whether such tables exist in the real world - but the concept itself seems sound. Also, the bitmap index is very small in low cardinality cases, where the btree tends to take up at least 10 times more space. Also, are adding/changing rows is more expensive with bitmaps than btrees? Without looking at the code, but having read the Oracle docs, I would guess yes. Every vacuum/delete would need to clear all of the bits for the row. Every insert/update would need to allocate a bit in at least the bitmap tree for the row inserted/updated. Seems like more pages may need to be written. Although perhaps some clever optimization would limit this. :-) It seems interesting though. We won't really know until we see the benchmarks. I'm seeing it as a form of working directly with the intermediate form of the bitmap index scanner. If the existing index scanner, building the bitmaps on the fly can out-perform the regular index scanner, I'm seeing potentially in a pre-built bitmap. Obviously, it isn't the answer to everything. The use I see for it, are a few of my 1:N object attribute tables. The table has an object identifier, and a column indicating the attribute type that the value is for. If I have 20 or more attribute type values, however, most objects include rows for most attribute types, my regular index ends up repeating the attribute type for every row. If I want to scan the table for all rows that have a particular attribute type with a particular value, it's a seqscan right now. With the bitmap scanner, knowing which rows to skip to immediately is readily available. Will it be worth it or not? I won't know until I try it. :-) Cheers, mark -- [EMAIL PROTECTED] / [EMAIL PROTECTED] / [EMAIL PROTECTED] __ . . _ ._ . . .__. . ._. .__ . . . .__ | Neighbourhood Coder |\/| |_| |_| |/|_ |\/| | |_ | |/ |_ | | | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness bind them... http://mark.mielke.cc/ ---(end of broadcast)--- TIP 6: explain analyze is your friend
Re: [HACKERS] On-disk bitmap index patch
Jie Zhang wrote: On 7/24/06 6:59 AM, Hannu Krosing [EMAIL PROTECTED] wrote: And also for AND-s of several indexes, where indexes are BIG, your btree indexes may be almost as big as tables but the resulting set of pages is small. Yeah, Hannu points it out very well -- the bitmap index works very well when columns have low cardinalities and AND operations will produce small number of results. Also, the bitmap index is very small in low cardinality cases, where the btree tends to take up at least 10 times more space. The smallness of the bitmap index also means that some queries will require much less work_mem to achieve good performance e.g consider: TPCH dataset with scale factor 10 on my usual PIII HW, query - select count(*) from lineitem where l_linenumber=1; This executes in about 100 seconds with work_mem = 20M if there is a bitmap index on l_linenumber. It takes 3832 seconds (!) if there is a btree index on the same column. Obviously cranking up work_mem will even up the difference (200M gets the btree to about 110 seconds), but being able to get good performance with less memory is a good thing! Cheers Mark ---(end of broadcast)--- TIP 4: Have you searched our list archives? http://archives.postgresql.org
Re: [HACKERS] On-disk bitmap index patch
[EMAIL PROTECTED] writes: Reading 1/4, for a larger table, has a good chance of being faster than reading 4/4 of the table. :-) Really? If you have to hit one tuple out of four, it's pretty much guaranteed that you will need to fetch every heap page. So using an index provides zero I/O savings on the heap side, and any fetches needed to read the index are pure cost. Now you have to demonstrate that the CPU costs involved in processing the index are significantly cheaper than the cost of just testing the WHERE qual at every heap tuple --- not a bet that's likely to win at a one-in-four ratio. Will it be worth it or not? I won't know until I try it. :-) Agreed. regards, tom lane ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] On-disk bitmap index patch
On Tue, Jul 25, 2006 at 12:36:42AM -0400, Tom Lane wrote: [EMAIL PROTECTED] writes: Reading 1/4, for a larger table, has a good chance of being faster than reading 4/4 of the table. :-) Really? If you have to hit one tuple out of four, it's pretty much guaranteed that you will need to fetch every heap page. So using an index provides zero I/O savings on the heap side, and any fetches needed to read the index are pure cost. Now you have to demonstrate that the CPU costs involved in processing the index are significantly cheaper than the cost of just testing the WHERE qual at every heap tuple --- not a bet that's likely to win at a one-in-four ratio. Haha. Of course - but that's assuming uniform spread of the values. Next I would try clustering the table on the bitmap index... :-) My databases aren't as large as many of yours. Most or all of them will fit in 1 Gbytes of RAM. The I/O cost isn't substantial for these, but the WHERE clause might be. But yeah - we don't know. Waste of code or performance boost. Cheers, mark -- [EMAIL PROTECTED] / [EMAIL PROTECTED] / [EMAIL PROTECTED] __ . . _ ._ . . .__. . ._. .__ . . . .__ | Neighbourhood Coder |\/| |_| |_| |/|_ |\/| | |_ | |/ |_ | | | | | | \ | \ |__ . | | .|. |__ |__ | \ |__ | Ottawa, Ontario, Canada One ring to rule them all, one ring to find them, one ring to bring them all and in the darkness bind them... http://mark.mielke.cc/ ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] On-disk bitmap index patch
On Mon, 17 Jul 2006, Jie Zhang wrote: Hi, I have posted a patch to the CVS head for on-disk bitmap index to pgsql-patches. If this can get in 8.2, that would be great. Any comments and suggestions are welcome. I still need to add several items: (1) README file in src/backend/access/bitmap. (2) Bitmap index documentation. (3) Hiding the internal btree. Also, I have disabled the multi-column index support because there is a known problem. Assume that there is a bitmap index on a and b. When a query predicate has only a, the current code may generate a wrong result. That's because the current code assumes that b is null. The ultimate problem is because the search code only handles one bitmap vector now. I need a fix to support manipulating multiple bitmap vectors. If you find any other problems, please let me know. Is anyone else looking at this patch? I am reviewing it with Jie, tidying it up and trying to solve some of the problems mentioned above. If anyone wants to take a look at us, please ask for an updated patch. Thanks, Gavin ---(end of broadcast)--- TIP 3: Have you checked our extensive FAQ? http://www.postgresql.org/docs/faq
Re: [HACKERS] On-disk bitmap index patch
Gavin Sherry [EMAIL PROTECTED] writes: Is anyone else looking at this patch? It's on my list of things to look at, but so are a lot of other patches ;-) A couple of comments after a *very* fast scan through the patch: * The xlog routines need help; they seem to not be updated for recent changes in the API for xlog recovery code. * The hacks on vacuum.c (where it tests the AM name) are utterly unacceptable. If you need the main code to do something special for a particular index AM, define a bool flag column for it in pg_am. * The interface to the existing executor bitmap scan code is mighty messy --- seems like there's a lot of almost duplicate code, a lot of rather invasive hacking, etc. This needs to be rethought and refactored. * Why in the world is it introducing duplicate copies of a lot of btree comparison functions? Use the ones that are there. * The patch itself is a mess: it introduces .orig and .rej files, changes around $PostgreSQL$ lines, etc. However, the main problem I've got with this is that a new index AM is a pretty large burden, and no one's made the slightest effort to sell pghackers on taking this on. What's the use-case, what's the performance like, where is it really an improvement over what we've got? regards, tom lane ---(end of broadcast)--- TIP 9: In versions below 8.0, the planner will ignore your desire to choose an index scan if your joining column's datatypes do not match
Re: [HACKERS] On-disk bitmap index patch
On Sun, 23 Jul 2006, Tom Lane wrote: Gavin Sherry [EMAIL PROTECTED] writes: Is anyone else looking at this patch? It's on my list of things to look at, but so are a lot of other patches ;-) A couple of comments after a *very* fast scan through the patch: * The xlog routines need help; they seem to not be updated for recent changes in the API for xlog recovery code. Yep. The patch was actually against 8.1 and was hastily brought up to 8.2. I think Jie's intention was to simply let everyone know that this was going on. * The hacks on vacuum.c (where it tests the AM name) are utterly unacceptable. If you need the main code to do something special for a particular index AM, define a bool flag column for it in pg_am. Yes. * The interface to the existing executor bitmap scan code is mighty messy --- seems like there's a lot of almost duplicate code, a lot of rather invasive hacking, etc. This needs to be rethought and refactored. I agree. * Why in the world is it introducing duplicate copies of a lot of btree comparison functions? Use the ones that are there. Yes, I raised this with Jie and she has fixed it. One thought is, we may want to rename those comparison functions prefixed with 'bm' to make their naming less confusing. They'll be used by btree, gin and bitmap index methods. Anyway, a seperate patch. * The patch itself is a mess: it introduces .orig and .rej files, changes around $PostgreSQL$ lines, etc. Right, not to mention patches to configure and a lot of style which needs to be knocked into shape. However, the main problem I've got with this is that a new index AM is a pretty large burden, and no one's made the slightest effort to sell pghackers on taking this on. What's the use-case, what's the performance like, where is it really an improvement over what we've got? For low cardinality sets, bitmaps greatly out perform btree. Jie and others at Greenplum tested this implementation (and others) against very large, low cardinality sets. I wasn't involved in it. I urge Jie and/or Luke to present those results. Thanks, Gavin ---(end of broadcast)--- TIP 2: Don't 'kill -9' the postmaster
Re: [HACKERS] On-disk bitmap index patch
Gavin Sherry [EMAIL PROTECTED] writes: On Sun, 23 Jul 2006, Tom Lane wrote: However, the main problem I've got with this is that a new index AM is a pretty large burden, and no one's made the slightest effort to sell pghackers on taking this on. For low cardinality sets, bitmaps greatly out perform btree. If the column is sufficiently low cardinality, you might as well just do a seqscan --- you'll be hitting most of the heap's pages anyway. I'm still waiting to be convinced that there's a sweet spot wide enough to justify supporting another index AM. (I'm also wondering whether this doesn't overlap the use-case for GIN.) regards, tom lane ---(end of broadcast)--- TIP 1: 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] On-disk bitmap index patch
Tom, On 7/23/06 5:25 PM, Tom Lane [EMAIL PROTECTED] wrote: If the column is sufficiently low cardinality, you might as well just do a seqscan --- you'll be hitting most of the heap's pages anyway. I'm still waiting to be convinced that there's a sweet spot wide enough to justify supporting another index AM. (I'm also wondering whether this doesn't overlap the use-case for GIN.) We presented them at the Postgres Anniversary summit talk (Bruce M. was there) and the reaction was let's get this into 8.2 because many people there (more than 5) really wanted to use it as a standard feature. A version of the slides with only the bitmap index results are located here: http://intranet.greenplum.com/bitmap-index-perf-ayush.ppt. - Luke ---(end of broadcast)--- TIP 6: explain analyze is your friend
[HACKERS] On-disk bitmap index patch
Hi, I have posted a patch to the CVS head for on-disk bitmap index to pgsql-patches. If this can get in 8.2, that would be great. Any comments and suggestions are welcome. I still need to add several items: (1) README file in src/backend/access/bitmap. (2) Bitmap index documentation. (3) Hiding the internal btree. Also, I have disabled the multi-column index support because there is a known problem. Assume that there is a bitmap index on a and b. When a query predicate has only a, the current code may generate a wrong result. That's because the current code assumes that b is null. The ultimate problem is because the search code only handles one bitmap vector now. I need a fix to support manipulating multiple bitmap vectors. If you find any other problems, please let me know. Thanks, Jie ---(end of broadcast)--- TIP 6: explain analyze is your friend
