summaryrefslogtreecommitdiff
path: root/src/backend/access/gist/gistutil.c
Commit message (Collapse)AuthorAgeFilesLines
...
* Minor cleanup of GiST code, for readability.Heikki Linnakangas2015-03-261-35/+15
| | | | | Remove the gistcentryinit function, inlining the relevant part of it into the only caller.
* Update copyright for 2015Bruce Momjian2015-01-061-1/+1
| | | | Backpatch certain files through 9.0
* pgindent run for 9.4Bruce Momjian2014-05-061-4/+4
| | | | | 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-071-1/+1
| | | | | Update all files in head, and files COPYRIGHT and legal.sgml in all back branches.
* pgindent run for release 9.3Bruce Momjian2013-05-291-3/+3
| | | | | This is the first run of the Perl-based pgindent script. Also update pgindent instructions.
* Support unlogged GiST index.Heikki Linnakangas2013-02-111-8/+22
| | | | | | | | | | | | | | | The reason this wasn't supported before was that GiST indexes need an increasing sequence to detect concurrent page-splits. In a regular WAL- logged GiST index, the LSN of the page-split record is used for that purpose, and in a temporary index, we can get away with a backend-local counter. Neither of those methods works for an unlogged relation. To provide such an increasing sequence of numbers, create a "fake LSN" counter that is saved and restored across shutdowns. On recovery, unlogged relations are blown away, so the counter doesn't need to survive that either. Jeevan Chalke, based on discussions with Robert Haas, Tom Lane and me.
* Repair bugs in GiST page splitting code for multi-column indexes.Tom Lane2013-02-071-30/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | When considering a non-last column in a multi-column GiST index, gistsplit.c tries to improve on the split chosen by the opclass-specific pickSplit function by considering penalties for the next column. However, there were two bugs in this code: it failed to recompute the union keys for the leftmost index columns, even though these might well change after reassigning tuples; and it included the old union keys in the recomputation for the columns it did recompute, so that those keys couldn't get smaller even if they should. The first problem could result in an invalid index in which searches wouldn't find index entries that are in fact present; the second would make the index less efficient to search. Both of these errors were caused by misuse of gistMakeUnionItVec, whose API was designed in a way that just begged such errors to be made. There is no situation in which it's safe or useful to compute the union keys for a subset of the index columns, and there is no caller that wants any previous union keys to be included in the computation; so the undocumented choice to treat the union keys as in/out rather than pure output parameters is a waste of code as well as being dangerous. Hence, rather than just making a minimal patch, I've changed the API of gistMakeUnionItVec to remove the "startkey" parameter (it now always processes all index columns) and treat the attr/isnull arrays as purely output parameters. In passing, also get rid of a couple of unnecessary and dangerous uses of static variables in gistutil.c. It's remarkable that the one in gistMakeUnionKey hasn't given us portability troubles before now, because in addition to posing a re-entrancy hazard, it was unsafely assuming that a static char[] array would have at least Datum alignment. Per investigation of a trouble report from Tomas Vondra. (There are also some bugs in contrib/btree_gist to be fixed, but that seems like material for a separate patch.) Back-patch to all supported branches.
* Add some randomness to the choice of which GiST page to insert to.Heikki Linnakangas2013-01-251-4/+62
| | | | | | | | | | | | | | | | | When descending the tree for an insert, and there are multiple equally good pages we could insert to, make the choice in random. Previously, we would always choose the tuple with lowest offset number. That meant that when two non-leaf pages overlap - in the extreme case they might have exactly the same key - all but the first such page went unused. That wasn't optimal for space usage; if you deleted some tuples from the non-first pages, the space would never be reused. With this patch, the other pages are sometimes chosen too, although there's still a heavy bias towards low-offset tuples, so that we don't lose cache locality when doing a lot of inserts with similar keys. Original idea by Alexander Korotkov, although this patch version was written by me and copy-edited by Tom Lane.
* Update copyrights for 2013Bruce Momjian2013-01-011-1/+1
| | | | | Fully update git head, and update back branches in ./COPYRIGHT and legal.sgml files.
* Improve coding of gistchoose and gistRelocateBuildBuffersOnSplit.Tom Lane2012-08-301-53/+60
| | | | | | | | This is mostly cosmetic, but it does eliminate a speculative portability issue. The previous coding ignored the fact that sum_grow could easily overflow (in fact, it could be summing multiple IEEE float infinities). On a platform where that didn't guarantee to produce a positive result, the code would misbehave. In any case, it was less than readable.
* Fix logic bug in gistchoose and gistRelocateBuildBuffersOnSplit.Robert Haas2012-08-301-2/+43
| | | | | | | | | | | | Every time the best-tuple-found-so-far changes, we need to reset all the penalty values in which_grow[] to the penalties for the new best tuple. The old code failed to do this, resulting in inferior index quality. The original patch from Alexander Korotkov was just two lines; I took the liberty of fleshing that out by adding a bunch of comments that I hope will make this logic easier for others to understand than it was for me.
* Replace XLogRecPtr struct with a 64-bit integer.Heikki Linnakangas2012-06-241-8/+2
| | | | | | | | | | | | | | This simplifies code that needs to do arithmetic on XLogRecPtrs. To avoid changing on-disk format of data pages, the LSN on data pages is still stored in the old format. That should keep pg_upgrade happy. However, we have XLogRecPtrs embedded in the control file, and in the structs that are sent over the replication protocol, so this changes breaks compatibility of pg_basebackup and server. I didn't do anything about this in this patch, per discussion on -hackers, the right thing to do would to be to change the replication protocol to be architecture-independent, so that you could use a newer version of pg_receivexlog, for example, against an older server version.
* Assorted comment fixes, mostly just typos, but some obsolete statements.Tom Lane2012-01-291-3/+3
| | | | YAMAMOTO Takashi
* Update copyright notices for year 2012.Bruce Momjian2012-01-011-1/+1
|
* Use IEEE infinity, not 1e10, for null-and-not-null case in gistpenalty().Tom Lane2011-11-271-2/+5
| | | | | | | Use of a randomly chosen large value was never exactly graceful, and now that there are penalty functions that are intentionally using infinity, it doesn't seem like a good idea for null-vs-not-null to be using something less.
* Buffering GiST index build algorithm.Heikki Linnakangas2011-09-081-5/+22
| | | | | | | | | When building a GiST index that doesn't fit in cache, buffers are attached to some internal nodes in the index. This speeds up the build by avoiding random I/O that would otherwise be needed to traverse all the way down the tree to the find right leaf page for tuple. Alexander Korotkov
* Remove unnecessary #include references, per pgrminclude script.Bruce Momjian2011-09-011-3/+0
|
* Pgindent run before 9.1 beta2.Bruce Momjian2011-06-091-2/+2
|
* Protect GIST logic that assumes penalty values can't be negative.Tom Lane2011-05-311-2/+9
| | | | | | | | | | Apparently sane-looking penalty code might return small negative values, for example because of roundoff error. This will confuse places like gistchoose(). Prevent problems by clamping negative penalty values to zero. (Just to be really sure, I also made it force NaNs to zero.) Back-patch to all supported branches. Alexander Korotkov
* Make GIN and GIST pass the index collation to all their support functions.Tom Lane2011-04-221-18/+25
| | | | | | | Experimentation with contrib/btree_gist shows that the majority of the GIST support functions potentially need collation information. Safest policy seems to be to pass it to all of them, instead of making assumptions about which ones could possibly need it.
* pgindent run before PG 9.1 beta 1.Bruce Momjian2011-04-101-1/+2
|
* Stamp copyrights for year 2011.Bruce Momjian2011-01-011-1/+1
|
* Rewrite the GiST insertion logic so that we don't need the post-recoveryHeikki Linnakangas2010-12-231-21/+7
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | cleanup stage to finish incomplete inserts or splits anymore. There was two reasons for the cleanup step: 1. When a new tuple was inserted to a leaf page, the downlink in the parent needed to be updated to contain (ie. to be consistent with) the new key. Updating the parent in turn might require recursively updating the parent of the parent. We now handle that by updating the parent while traversing down the tree, so that when we insert the leaf tuple, all the parents are already consistent with the new key, and the tree is consistent at every step. 2. When a page is split, we need to insert the downlink for the new right page(s), and update the downlink for the original page to not include keys that moved to the right page(s). We now handle that by setting a new flag, F_FOLLOW_RIGHT, on the non-rightmost pages in the split. When that flag is set, scans always follow the rightlink, regardless of the NSN mechanism used to detect concurrent page splits. That way the tree is consistent right after split, even though the downlink is still missing. This is very similar to the way B-tree splits are handled. When the downlink is inserted in the parent, the flag is cleared. To keep the insertion algorithm simple, when an insertion sees an incomplete split, indicated by the F_FOLLOW_RIGHT flag, it finishes the split before doing anything else. These changes allow removing the whole "invalid tuple" mechanism, but I retained the scan code to still follow invalid tuples correctly. While we don't create any such tuples anymore, we want to handle them gracefully in case you pg_upgrade a GiST index that has them. If we encounter any on an insert, though, we just throw an error saying that you need to REINDEX. The issue that got me into doing this is that if you did a checkpoint while an insert or split was in progress, and the checkpoint finishes quickly so that there is no WAL record related to the insert between RedoRecPtr and the checkpoint record, recovery from that checkpoint would not know to finish the incomplete insert. IOW, we have the same issue we solved with the rm_safe_restartpoint mechanism during normal operation too. It's highly unlikely to happen in practice, and this fix is far too large to backpatch, so we're just going to live with in previous versions, but this refactoring fixes it going forward. With this patch, you don't get the annoying 'index "FOO" needs VACUUM or REINDEX to finish crash recovery' notices anymore if you crash at an unfortunate moment.
* The GiST scan algorithm uses LSNs to detect concurrent pages splits, butHeikki Linnakangas2010-11-161-0/+21
| | | | | | | | | | | | | temporary indexes are not WAL-logged. We used a constant LSN for temporary indexes, on the assumption that we don't need to worry about concurrent page splits in temporary indexes because they're only visible to the current session. But that assumption is wrong, it's possible to insert rows and split pages in the same session, while a scan is in progress. For example, by opening a cursor and fetching some rows, and INSERTing new rows before fetching some more. Fix by generating fake increasing LSNs, used in place of real LSNs in temporary GiST indexes.
* Remove cvs keywords from all files.Magnus Hagander2010-09-201-1/+1
|
* Update copyright for the year 2010.Bruce Momjian2010-01-021-2/+2
|
* 8.4 pgindent run, with new combined Linux/FreeBSD/MinGW typedef listBruce Momjian2009-06-111-2/+3
| | | | provided by Andrew.
* Change the reloptions machinery to use a table-based parser, and provideAlvaro Herrera2009-01-051-4/+3
| | | | | | | | a more complete framework for writing custom option processing routines by user-defined access methods. Catalog version bumped due to the general API changes, which are going to affect user-defined "amoptions" routines.
* Update copyright for 2009.Bruce Momjian2009-01-011-2/+2
|
* Rewrite the FSM. Instead of relying on a fixed-size shared memory segment, theHeikki Linnakangas2008-09-301-2/+3
| | | | | | | | | | | | | free space information is stored in a dedicated FSM relation fork, with each relation (except for hash indexes; they don't use FSM). This eliminates the max_fsm_relations and max_fsm_pages GUC options; remove any trace of them from the backend, initdb, and documentation. Rewrite contrib/pg_freespacemap to match the new FSM implementation. Also introduce a new variant of the get_raw_page(regclass, int4, int4) function in contrib/pageinspect that let's you to return pages from any relation fork, and a new fsm_page_contents() function to inspect the new FSM pages.
* Clean up the use of some page-header-access macros: principally, useTom Lane2008-07-131-3/+2
| | | | | | | | | | SizeOfPageHeaderData instead of sizeof(PageHeaderData) in places where that makes the code clearer, and avoid casting between Page and PageHeader where possible. Zdenek Kotala, with some additional cleanup by Heikki Linnakangas. I did not apply the parts of the proposed patch that would have resulted in slightly changing the on-disk format of hash indexes; it seems to me that's not a win as long as there's any chance of having in-place upgrade for 8.4.
* Improve our #include situation by moving pointer types away from theAlvaro Herrera2008-06-191-1/+2
| | | | | | | corresponding struct definitions. This allows other headers to avoid including certain highly-loaded headers such as rel.h and relscan.h, instead using just relcache.h, heapam.h or genam.h, which are more lightweight and thus cause less unnecessary dependencies.
* Fix 64-bit problem in recent patch.Tom Lane2008-06-151-2/+2
|
* Refactor XLogOpenRelation() and XLogReadBuffer() in preparation for relationHeikki Linnakangas2008-06-121-10/+8
| | | | | | | | | | forks. XLogOpenRelation() and the associated light-weight relation cache in xlogutils.c is gone, and XLogReadBuffer() now takes a RelFileNode as argument, instead of Relation. For functions that still need a Relation struct during WAL replay, there's a new function called CreateFakeRelcacheEntry() that returns a fake entry like XLogOpenRelation() used to.
* Restructure some header files a bit, in particular heapam.h, by removing someAlvaro Herrera2008-05-121-2/+3
| | | | | | | | | | | | unnecessary #include lines in it. Also, move some tuple routine prototypes and macros to htup.h, which allows removal of heapam.h inclusion from some .c files. For this to work, a new header file access/sysattr.h needed to be created, initially containing attribute numbers of system columns, for pg_dump usage. While at it, make contrib ltree, intarray and hstore header files more consistent with our header style.
* Update copyrights in source tree to 2008.Bruce Momjian2008-01-011-2/+2
|
* HOT updates. When we update a tuple without changing any of its indexedTom Lane2007-09-201-2/+2
| | | | | | | | | | | | columns, and the new version can be stored on the same heap page, we no longer generate extra index entries for the new version. Instead, index searches follow the HOT-chain links to ensure they find the correct tuple version. In addition, this patch introduces the ability to "prune" dead tuples on a per-page basis, without having to do a complete VACUUM pass to recover space. VACUUM is still needed to clean up dead index entries, however. Pavan Deolasee, with help from a bunch of other people.
* Redefine the lp_flags field of item pointers as having four states, ratherTom Lane2007-09-121-2/+2
| | | | | | | | | than two independent bits (one of which was never used in heap pages anyway, or at least hadn't been in a very long time). This gives us flexibility to add the HOT notions of redirected and dead item pointers without requiring anything so klugy as magic values of lp_off and lp_len. The state values are chosen so that for the states currently in use (pre-HOT) there is no change in the physical representation.
* Minor tweaking of index special-space definitions so that the variousTom Lane2007-04-091-3/+4
| | | | | | | | | | index types can be reliably distinguished by examining the special space on an index page. Per my earlier proposal, plus the realization that there's no need for btree's vacuum cycle ID to cycle through every possible 16-bit value. Restricting its range a little costs nearly nothing and eliminates the possibility of collisions. Memo to self: remember to make bitmap indexes play along with this scheme, assuming that patch ever gets accepted.
* Update CVS HEAD for 2007 copyright. Back branches are typically notBruce Momjian2007-01-051-2/+2
| | | | back-stamped for this.
* pgindent run for 8.2.Bruce Momjian2006-10-041-80/+109
|
* Remove 576 references of include files that were not needed.Bruce Momjian2006-07-141-4/+1
|
* Code review for FILLFACTOR patch. Change WITH grammar as per earlierTom Lane2006-07-031-11/+13
| | | | | | | | | | | | | | | | discussion (including making def_arg allow reserved words), add missed opt_definition for UNIQUE case. Put the reloptions support code in a less random place (I chose to make a new file access/common/reloptions.c). Eliminate header inclusion creep. Make the index options functions safely user-callable (seems like client apps might like to be able to test validity of options before trying to make an index). Reduce overhead for normal case with no options by allowing rd_options to be NULL. Fix some unmaintainably klugy code, including getting rid of Natts_pg_class_fixed at long last. Some stylistic cleanup too, and pay attention to keeping comments in sync with code. Documentation still needs work, though I did fix the omissions in catalogs.sgml and indexam.sgml.
* Add FILLFACTOR to CREATE INDEX.Bruce Momjian2006-07-021-3/+17
| | | | ITAGAKI Takahiro
* ChangesTeodor Sigaev2006-06-281-360/+61
| | | | | | | | | | | | | | | | | | | | * new split algorithm (as proposed in http://archives.postgresql.org/pgsql-hackers/2006-06/msg00254.php) * possible call pickSplit() for second and below columns * add spl_(l|r)datum_exists to GIST_SPLITVEC - pickSplit should check its values to use already defined spl_(l|r)datum for splitting. pickSplit should set spl_(l|r)datum_exists to 'false' (if they was 'true') to signal to caller about using spl_(l|r)datum. * support for old pickSplit(): not very optimal but correct split * remove 'bytes' field from GISTENTRY: in any case size of value is defined by it's type. * split GIST_SPLITVEC to two structures: one for using in picksplit and second - for internal use. * some code refactoring * support of subsplit to rtree opclasses TODO: add support of subsplit to contrib modules
* Som improve page split in multicolumn GiST index.Teodor Sigaev2006-05-291-38/+47
| | | | | | If user picksplit on n-th column generate equals left and right unions then it calls picksplit on n+1-th column.
* * Add support NULL to GiST.Teodor Sigaev2006-05-241-278/+198
| | | | | | | | * some refactoring and simplify code int gistutil.c and gist.c * now in some cases it can be called used-defined picksplit method for non-first column in index, but here is a place to do more. * small fix of docs related to support NULL.
* Simplify gistSplit() and some refactoring related code.Teodor Sigaev2006-05-191-80/+105
|
* Reduce size of critial section during vacuum full, criticalTeodor Sigaev2006-05-171-5/+4
| | | | | | | | sections now isn't nested. All user-defined functions now is called outside critsections. Small improvements in WAL protocol. TODO: improve XLOG replay
* Reduce size of critical section and remove call of user-defined functions inTeodor Sigaev2006-05-101-5/+21
| | | | | | insertion and deletion, modify gistSplit() to do not use buffers. TODO: gistvacuumcleanup and XLOG
View Lorry Controller Status