aboutsummaryrefslogtreecommitdiff
path: root/src/backend/nodes/bitmapset.c
Commit message (Collapse)AuthorAge
* Update copyright for 2025Bruce Momjian2025-01-01
| | | | Backpatch-through: 13
* Move some bitmap logic out of bitmapset.cJohn Naylor2024-03-06
| | | | | | | | | Move the logic for selecting appropriate pg_bitutils.h functions based on word size to bitmapset.h for wider visibility. Reviewed (in a previous version) by Tom Lane Discussion: https://postgr.es/m/CAFBsxsFW2JjTo58jtDB%2B3sZhxMx3t-3evew8%3DAcr%2BGGhC%2BkFaA%40mail.gmail.com
* Fix broken Bitmapset optimization in DiscreteKnapsack()David Rowley2024-01-19
| | | | | | | | | | | | | | | | | | | | | | Some code in DiscreteKnapsack() attempted to zero all words in a Bitmapset by performing bms_del_members() to delete all the members from itself before replacing those members with members from another set. When that code was written, this was a valid way to manipulate the set in such a way to save from palloc having to be called to allocate a new Bitmapset. However, 00b41463c modified Bitmapsets so that an empty set is *always* represented as NULL and this breaks the optimization as the Bitmapset code will always pfree the memory when the set becomes empty. Since DiscreteKnapsack() has been coded to avoid as many unneeded allocations as possible, it seems risky to not fix this. Here we add bms_replace_members() to effectively perform an in-place copy of another set, reusing the memory of the existing set, when possible. This got broken in v16, but no backpatch for now as there've been no complaints. Reviewed-by: Richard Guo Discussion: https://postgr.es/m/CAApHDvoTCBkBU2PJghNOFUiO0q=QP4WAWHi5sJP6_4=b2WodrA@mail.gmail.com
* Fix REALLOCATE_BITMAPSETS codeDavid Rowley2024-01-17
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 7d58f2342 added a compile-time option to have bitmapset.c reallocate the set before returning when a set is modified. That commit failed to do its job in various cases and returned the input set when it shouldn't have in these cases. Here we fix those missing cases. This commit also adds some documentation about what REALLOCATE_BITMAPSETS is for. This is important as future functions that go inside bitmapset.c need to know if they need to do anything special when this compile-time option is defined. Also, between 71a3e8c43 and 7d58f2342 some Asserts seem to have become duplicated. Tidy these up. Rather than having the Assert check each aspect of what makes a set invalid, here we introduce a helper function which returns false when a set is invalid and have the Asserts use this instead. Also, make a pass on improving the comments in bitmapset.c. Various comments mentioned the input sets being "recycled". This could be interpreted to mean that the output set will always point to the same memory as the given input parameter. Here we try to make it clear that this must not be relied upon and that callers must ensure that all references to a given set are updated on each modification. In passing, improve comments for bms_union(), bms_intersect() and bms_difference() to detail what they do. I (David) have too often had to remind myself by reading the code each time to find out if I need, for example, to use bms_union() or bms_join(). I also removed some low-value comments that were trying to convey information about "these operations" without mentioning which operations it was talking about. It seems better to document these things in the function header comment instead. Author: Richard Guo, David Rowley Discussion: https://postgr.es/m/CAMbWs4-djy9qYux2gZrtmxA0StrYXJjvB-oqLxn-d7J88t=PQQ@mail.gmail.com
* Update copyright for 2024Bruce Momjian2024-01-03
| | | | | | | | Reported-by: Michael Paquier Discussion: https://postgr.es/m/ZZKTDPxBBMt3C0J9@paquier.xyz Backpatch-through: 12
* REALLOCATE_BITMAPSETS manual compile-time optionAlexander Korotkov2023-12-27
| | | | | | | | This option forces each bitmapset modification to reallocate bitmapset. This is useful for debugging hangling pointers to bitmapset's. Discussion: https://postgr.es/m/CAMbWs4_wJthNtYBL%2BSsebpgF-5L2r5zFFk6xYbS0A78GKOTFHw%40mail.gmail.com Reviewed-by: Richard Guo, Andres Freund, Ashutosh Bapat, Andrei Lepikhov
* Add asserts to bimapset manipulation functionsAlexander Korotkov2023-12-27
| | | | | | | | New asserts validate that arguments are really bitmapsets. This should help to early detect accesses to dangling pointers. Discussion: https://postgr.es/m/CAMbWs4_wJthNtYBL%2BSsebpgF-5L2r5zFFk6xYbS0A78GKOTFHw%40mail.gmail.com Reviewed-by: Richard Guo, Andres Freund, Ashutosh Bapat, Andrei Lepikhov
* Remove trailing zero words from BitmapsetsDavid Rowley2023-07-04
| | | | | | | | | | | | | | | | | | | | | Prior to this, Bitmapsets could contain trailing words which had no members set. Many places in bitmapset.c had to loop over trailing words to check for empty words. If we ensure we always remove these trailing zero words then we can perform various optimizations such as fast pathing bms_is_subset to return false when 'a' has more words than 'b'. A similar optimization is possible in bms_equal. Both of these together can yield quite significant performance increases in the query planner when querying a partitioned table with around 100 or more partitions. While we're at it, since the minimum number of words a Bitmapset can contain is 1, we can make use of do/while loops instead of for loops when looping over all words in a set. This means checking the loop condition 1 less time, which for single-word sets cuts the loop condition checks in half. Author: David Rowley Reviewed-by: Yuya Watari Discussion: https://postgr.es/m/CAApHDvr5O41MuUjw0DQKqmAnv7QqvmLqXReEd5o4nXTzWp8-+w@mail.gmail.com
* Require empty Bitmapsets to be represented as NULL.Tom Lane2023-03-02
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When I designed the Bitmapset module, I set things up so that an empty Bitmapset could be represented either by a NULL pointer, or by an allocated object all of whose bits are zero. I've recently come to the conclusion that that was a bad idea and we should instead have a convention like the longstanding invariant for Lists, whereby an empty list is represented by NIL and nothing else. To do this, we need to fix bms_intersect, bms_difference, and a couple of other functions to check for having produced an empty result; but then we can replace bms_is_empty(a) by a simple "a == NULL" test. This is very likely a (marginal) win performance-wise, because we call bms_is_empty many more times than those other functions put together. However, the real reason to do it is that we have various places that have hand-implemented a rule about "this Bitmapset variable must be exactly NULL if empty", so that they can use checks-for-null in place of bms_is_empty calls in particularly hot code paths. That is a really fragile, mistake-prone way to do things, and I'm surprised that we've seldom been bitten by it. It's not well documented at all which variables have this property, so you can't readily tell which code might be violating those conventions. By making the convention universal, we can eliminate a subtle source of bugs. Patch by me; thanks to Nathan Bossart and Richard Guo for review. Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
* Remove bms_first_member().Tom Lane2023-03-02
| | | | | | | | | | | | | | This function has been semi-deprecated ever since we invented bms_next_member(). Its habit of scribbling on the input bitmapset isn't great, plus for sufficiently large bitmapsets it would take O(N^2) time to complete a loop. Now we have the additional problem that reducing the input to empty while leaving it still accessible would violate a planned invariant. So let's just get rid of it, after updating the few extant callers to use bms_next_member(). Patch by me; thanks to Nathan Bossart and Richard Guo for review. Discussion: https://postgr.es/m/1159933.1677621588@sss.pgh.pa.us
* Update copyright for 2023Bruce Momjian2023-01-02
| | | | Backpatch-through: 11
* Make Bitmapsets be valid Nodes.Tom Lane2022-11-13
| | | | | | | | | | | | | | | | | | | | | | | Add a NodeTag field to struct Bitmapset. This is free because of alignment considerations on 64-bit hardware. While it adds some space on 32-bit machines, we aren't optimizing for that case anymore. The advantage is that data structures such as Lists of Bitmapsets are now first-class objects to the Node infrastructure, and don't require special-case code to handle. This patch includes removal of one such special case, in indxpath.c: bms_equal_any() can now be replaced by list_member(). There may be more existing code that could be simplified, but I didn't look very hard. We also get to drop the read_write_ignore annotations on a couple of RelOptInfo fields. The outfuncs/readfuncs support is arranged so that nothing changes in the string representation of a Bitmapset field; therefore, this doesn't need a catversion bump. Amit Langote and Tom Lane Discussion: https://postgr.es/m/109089.1668197158@sss.pgh.pa.us
* Update copyright for 2022Bruce Momjian2022-01-07
| | | | Backpatch-through: 10
* Flush Memoize cache when non-key parameters change, take 2David Rowley2021-11-24
| | | | | | | | | | | | | | | | It's possible that a subplan below a Memoize node contains a parameter from above the Memoize node. If this parameter changes then cache entries may become out-dated due to the new parameter value. Previously Memoize was mistakenly not aware of this. We fix this here by flushing the cache whenever a parameter that's not part of the cache key changes. Bug: #17213 Reported by: Elvis Pranskevichus Author: David Rowley Discussion: https://postgr.es/m/17213-988ed34b225a2862@postgresql.org Backpatch-through: 14, where Memoize was added
* Revert "Flush Memoize cache when non-key parameters change"David Rowley2021-11-24
| | | | This reverts commit 1050048a315790a505465bfcceb26eaf8dbc7e2e.
* Flush Memoize cache when non-key parameters changeDavid Rowley2021-11-24
| | | | | | | | | | | | | | | | It's possible that a subplan below a Memoize node contains a parameter from above the Memoize node. If this parameter changes then cache entries may become out-dated due to the new parameter value. Previously Memoize was mistakenly not aware of this. We fix this here by flushing the cache whenever a parameter that's not part of the cache key changes. Bug: #17213 Reported by: Elvis Pranskevichus Author: David Rowley Discussion: https://postgr.es/m/17213-988ed34b225a2862@postgresql.org Backpatch-through: 14, where Memoize was added
* Update copyright for 2021Bruce Momjian2021-01-02
| | | | Backpatch-through: 9.5
* Move src/backend/utils/hash/hashfn.c to src/commonRobert Haas2020-02-27
| | | | | | | | | | | | | | This also involves renaming src/include/utils/hashutils.h, which becomes src/include/common/hashfn.h. Perhaps an argument can be made for keeping the hashutils.h name, but it seemed more consistent to make it match the name of the file, and also more descriptive of what is actually going on here. Patch by me, reviewed by Suraj Kharage and Mark Dilger. Off-list advice on how not to break the Windows build from Davinder Singh and Amit Kapila. Discussion: http://postgr.es/m/CA+TgmoaRiG4TXND8QuM6JXFRkM_1wL2ZNhzaUKsuec9-4yrkgw@mail.gmail.com
* Move bitmap_hash and bitmap_match to bitmapset.c.Robert Haas2020-02-24
| | | | | | | | | | | The closely-related function bms_hash_value is already defined in that file, and this change means that hashfn.c no longer needs to depend on nodes/bitmapset.h. That gets us closer to allowing use of the hash functions in hashfn.c in frontend code. Patch by me, reviewed by Suraj Kharage and Mark Dilger. Discussion: http://postgr.es/m/CA+TgmoaRiG4TXND8QuM6JXFRkM_1wL2ZNhzaUKsuec9-4yrkgw@mail.gmail.com
* Update copyrights for 2020Bruce Momjian2020-01-01
| | | | Backpatch-through: update all files in master, backpatch legal files through 9.4
* Initial pgindent run for v12.Tom Lane2019-05-22
| | | | | | | | This is still using the 2.0 version of pg_bsd_indent. I thought it would be good to commit this separately, so as to document the differences between 2.0 and 2.1 behavior. Discussion: https://postgr.es/m/16296.1558103386@sss.pgh.pa.us
* Add support for multivariate MCV listsTomas Vondra2019-03-27
| | | | | | | | | | | | | | | | Introduce a third extended statistic type, supported by the CREATE STATISTICS command - MCV lists, a generalization of the statistic already built and used for individual columns. Compared to the already supported types (n-distinct coefficients and functional dependencies), MCV lists are more complex, include column values and allow estimation of much wider range of common clauses (equality and inequality conditions, IS NULL, IS NOT NULL etc.). Similarly to the other types, a new pseudo-type (pg_mcv_list) is used. Author: Tomas Vondra Reviewed-by: Dean Rasheed, David Rowley, Mark Dilger, Alvaro Herrera Discussion: https://postgr.es/m/dfdac334-9cf2-2597-fb27-f0fb3753f435@2ndquadrant.com
* Move hash_any prototype from access/hash.h to utils/hashutils.hAlvaro Herrera2019-03-11
| | | | | | | | | | | | | | | | | | | | | ... as well as its implementation from backend/access/hash/hashfunc.c to backend/utils/hash/hashfn.c. access/hash is the place for the hash index AM, not really appropriate for generic facilities, which is what hash_any is; having things the old way meant that anything using hash_any had to include the AM's include file, pointlessly polluting its namespace with unrelated, unnecessary cruft. Also move the HTEqual strategy number to access/stratnum.h from access/hash.h. To avoid breaking third-party extension code, add an #include "utils/hashutils.h" to access/hash.h. (An easily removed line by committers who enjoy their asbestos suits to protect them from angry extension authors.) Discussion: https://postgr.es/m/201901251935.ser5e4h6djt2@alvherre.pgsql
* Make use of compiler builtins and/or assembly for CLZ, CTZ, POPCNT.Tom Lane2019-02-15
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Test for the compiler builtins __builtin_clz, __builtin_ctz, and __builtin_popcount, and make use of these in preference to handwritten C code if they're available. Create src/port infrastructure for "leftmost one", "rightmost one", and "popcount" so as to centralize these decisions. On x86_64, __builtin_popcount generally won't make use of the POPCNT opcode because that's not universally supported yet. Provide code that checks CPUID and then calls POPCNT via asm() if available. This requires indirecting through a function pointer, which is an annoying amount of overhead for a one-instruction operation, but it's probably not worth working harder than this for our current use-cases. I'm not sure we've found all the existing places that could profit from this new infrastructure; but we at least touched all the ones that used copied-and-pasted versions of the bitmapset.c code, and got rid of multiple copies of the associated constant arrays. While at it, replace c-compiler.m4's one-per-builtin-function macros with a single one that can handle all the cases we need to worry about so far. Also, because I'm paranoid, make those checks into AC_LINK checks rather than just AC_COMPILE; the former coding failed to verify that libgcc has support for the builtin, in cases where it's not inline code. David Rowley, Thomas Munro, Alvaro Herrera, Tom Lane Discussion: https://postgr.es/m/CAKJS1f9WTAGG1tPeJnD18hiQW5gAk59fQ6WK-vfdAKEHyRg2RA@mail.gmail.com
* Revert attempts to use POPCNT etc instructionsAlvaro Herrera2019-02-15
| | | | | | | | | | | This reverts commits fc6c72747ae6, 109de05cbb03, d0b4663c23b7 and 711bab1e4d19. Somebody will have to try harder before submitting this patch again. I've spent entirely too much time on it already, and the #ifdef maze yet to be written in order for it to build at all got on my nerves. The amount of work needed to get a platform-specific performance improvement that's barely above the noise level is not worth it.
* Add basic support for using the POPCNT and SSE4.2s LZCNT opcodesAlvaro Herrera2019-02-13
| | | | | | | | | | | | | These opcodes have been around in the AMD world since 2007, and 2008 in the case of intel. They're supported in GCC and Clang via some __builtin macros. The opcodes may be unavailable during runtime, in which case we fall back on a C-based implementation of the code. In order to get the POPCNT instruction we must pass the -mpopcnt option to the compiler. We do this only for the pg_bitutils.c file. David Rowley (with fragments taken from a patch by Thomas Munro) Discussion: https://postgr.es/m/CAKJS1f9WTAGG1tPeJnD18hiQW5gAk59fQ6WK-vfdAKEHyRg2RA@mail.gmail.com
* Update copyright for 2019Bruce Momjian2019-01-02
| | | | Backpatch-through: certain files through 9.4
* Remove dead code left behind by 1b6801051.Tom Lane2018-07-30
|
* Change bms_add_range to be a no-op for empty rangesAlvaro Herrera2018-07-30
| | | | | | | | | | | | | | | | In commit 84940644de93, bms_add_range was added with an API to fail with an error if an empty range was specified. This seems arbitrary and unhelpful, so turn that case into a no-op instead. Callers that require further verification on the arguments or result can apply them by themselves. This fixes the bug that partition pruning throws an API error for a case involving the default partition of a default partition, as in the included test case. Reported-by: Rajkumar Raghuwanshi <rajkumar.raghuwanshi@enterprisedb.com> Diagnosed-by: Tom Lane <tgl@sss.pgh.pa.us> Discussion: https://postgr.es/m/16590.1532622503@sss.pgh.pa.us
* Post-feature-freeze pgindent run.Tom Lane2018-04-26
| | | | Discussion: https://postgr.es/m/15719.1523984266@sss.pgh.pa.us
* Make bms_prev_member work correctly with a 64 bit bitmapwordTeodor Sigaev2018-04-23
| | | | | | | | | | | | 5c067521 erroneously had coded bms_prev_member assuming that a bitmapword would always hold 32 bits and started it's search on what it thought was the highest 8-bits of the word. This was not the case if bitmapwords were 64 bits. In passing add a test to exercise this function a little. Previously there was no coverage at all. David Rowly
* Add bms_prev_member functionAlvaro Herrera2018-04-07
| | | | | | | | | | | | This works very much like the existing bms_last_member function, only it traverses through the Bitmapset in the opposite direction from the most significant bit down to the least significant bit. A special prevbit value of -1 may be used to have the function determine the most significant bit. This is useful for starting a loop. When there are no members less than prevbit, the function returns -2 to indicate there are no more members. Author: David Rowley Discussion: https://postgr.es/m/CAKJS1f-K=3d5MDASNYFJpUpc20xcBnAwNC1-AOeunhn0OtkWbQ@mail.gmail.com
* Improve the heuristic for ordering child paths of a parallel append.Tom Lane2018-01-09
| | | | | | | | | | | | | | | | | | | | | | | | | Commit ab7271677 introduced code that attempts to order the child scans of a Parallel Append node in a way that will minimize execution time, based on total cost and startup cost. However, it failed to think hard about what to do when estimated costs are exactly equal; a case that's particularly likely to occur when comparing on startup cost. In such a case the ordering of the child paths would be left to the whims of qsort, an algorithm that isn't even stable. We can improve matters by applying the rule used elsewhere in the planner: if total costs are equal, sort on startup cost, and vice versa. When both cost estimates are exactly equal, rather than letting qsort do something unpredictable, sort based on the child paths' relids, which should typically result in sorting in inheritance order. (The latter provision requires inventing a qsort-style comparator for bitmapsets, but maybe we'll have use for that for other reasons in future.) This results in a few plan changes in the select_parallel test, but those all look more reasonable than before, when the actual underlying cost numbers are taken into account. Discussion: https://postgr.es/m/4944.1515446989@sss.pgh.pa.us
* Update copyright for 2018Bruce Momjian2018-01-02
| | | | Backpatch-through: certain files through 9.3
* Remove extra word from comment.Robert Haas2017-11-30
| | | | | | | | | David Rowley, who also was the primary author of the patch that added this function; the attribution in my previous commit, 84940644de931f331433b35e3a391822671f8c9c, was incorrect due to sloppiness on my part. Discussion: http://postgr.es/m/CAKJS1f_0iSiLQsf_c06AzOWAc3eS6ePjjVQFpcFv3W-O5aktnQ@mail.gmail.com
* New C function: bms_add_rangeRobert Haas2017-11-29
| | | | | | | | | | | This will be used by pending patches to improve partition pruning. Amit Langote and Kyotaro Horiguchi, per a suggestion from David Rowley. Review and testing of the larger patch set of which this is a part by Ashutosh Bapat, David Rowley, Dilip Kumar, Jesper Pedersen, Rajkumar Raghuwanshi, Beena Emerson, Amul Sul, and Kyotaro Horiguchi. Discussion: http://postgr.es/m/098b9c71-1915-1a2a-8d52-1a7a50ce79e8@lab.ntt.co.jp
* Change TRUE/FALSE to true/falsePeter Eisentraut2017-11-08
| | | | | | | | | | | | | | The lower case spellings are C and C++ standard and are used in most parts of the PostgreSQL sources. The upper case spellings are only used in some files/modules. So standardize on the standard spellings. The APIs for ICU, Perl, and Windows define their own TRUE and FALSE, so those are left as is when using those APIs. In code comments, we use the lower-case spelling for the C concepts and keep the upper-case spelling for the SQL concepts. Reviewed-by: Michael Paquier <michael.paquier@gmail.com>
* Support hashed aggregation with grouping sets.Andrew Gierth2017-03-27
| | | | | | | | | | | | | | | | | | This extends the Aggregate node with two new features: HashAggregate can now run multiple hashtables concurrently, and a new strategy MixedAggregate populates hashtables while doing sorted grouping. The planner will now attempt to save as many sorts as possible when planning grouping sets queries, while not exceeding work_mem for the estimated combined sizes of all hashtables used. No SQL-level changes are required. There should be no user-visible impact other than the new EXPLAIN output and possible changes to result ordering when ORDER BY was not used (which affected a few regression tests). The enable_hashagg option is respected. Author: Andrew Gierth Reviewers: Mark Dilger, Andres Freund Discussion: https://postgr.es/m/87vatszyhj.fsf@news-spur.riddles.org.uk
* Update copyright via script for 2017Bruce Momjian2017-01-03
|
* Update copyright for 2016Bruce Momjian2016-01-02
| | | | Backpatch certain files through 9.1
* Update copyright for 2015Bruce Momjian2015-01-06
| | | | Backpatch certain files through 9.0
* Add bms_get_singleton_member(), and use it where appropriate.Tom Lane2014-11-28
| | | | | | | | | | This patch adds a function that replaces a bms_membership() test followed by a bms_singleton_member() call, performing both the test and the extraction of a singleton set's member in one scan of the bitmapset. The performance advantage over the old way is probably minimal in current usage, but it seems worthwhile on notational grounds anyway. David Rowley
* Add bms_next_member(), and use it where appropriate.Tom Lane2014-11-28
| | | | | | | | | | | | This patch adds a way of iterating through the members of a bitmapset nondestructively, unlike the old way with bms_first_member(). While bms_next_member() is very slightly slower than bms_first_member() (at least for typical-size bitmapsets), eliminating the need to palloc and pfree a temporary copy of the target bitmapset is a significant win. So this method should be preferred in all cases where a temporary copy would be necessary. Tom Lane, with suggestions from Dean Rasheed and David Rowley
* pgindent run for 9.4Bruce Momjian2014-05-06
| | | | | This includes removing tabs after periods in C comments, which was applied to back branches, so this change should not effect backpatching.
* Update copyright for 2014Bruce Momjian2014-01-07
| | | | | Update all files in head, and files COPYRIGHT and legal.sgml in all back branches.
* In bms_add_member(), use repalloc() if the bms needs to be enlarged.Heikki Linnakangas2013-09-30
| | | | | | | | | | | Previously bms_add_member() would palloc a whole-new copy of the existing set, copy the words, and pfree the old one. repalloc() is potentially much faster, and more importantly, this is less surprising if CurrentMemoryContext is not the same as the context the old set is in. bms_add_member() still allocates a new bitmapset in CurrentMemoryContext if NULL is passed as argument, but that is a lot less likely to induce bugs. Nicholas White.
* Update copyrights for 2013Bruce Momjian2013-01-01
| | | | | Fully update git head, and update back branches in ./COPYRIGHT and legal.sgml files.
* Run pgindent on 9.2 source tree in preparation for first 9.3Bruce Momjian2012-06-10
| | | | commit-fest.
* Use parameterized paths to generate inner indexscans more flexibly.Tom Lane2012-01-27
| | | | | | | | | | | | | | | | | | | This patch fixes the planner so that it can generate nestloop-with- inner-indexscan plans even with one or more levels of joining between the indexscan and the nestloop join that is supplying the parameter. The executor was fixed to handle such cases some time ago, but the planner was not ready. This should improve our plans in many situations where join ordering restrictions formerly forced complete table scans. There is probably a fair amount of tuning work yet to be done, because of various heuristics that have been added to limit the number of parameterized paths considered. However, we are not going to find out what needs to be adjusted until the code gets some real-world use, so it's time to get it in there where it can be tested easily. Note API change for index AM amcostestimate functions. I'm not aware of any non-core index AMs, but if there are any, they will need minor adjustments.
* Update copyright notices for year 2012.Bruce Momjian2012-01-01
|
generated by cgit v1.2.3 (git 2.25.1) at 2025-06-07 17:38:00 +0000