Install a search tree depth limit in GIN bulk-insert operations, to prevent
Tom Lane <tgl@sss.pgh.pa.us>
Install a search tree depth limit in GIN bulk-insert operations, to prevent them from degrading badly when the input is sorted or nearly so. In this scenario the tree is unbalanced to the point of becoming a mere linked list, so insertions become O(N^2). The easiest and most safely back-patchable solution is to stop growing the tree sooner, ie limit the growth of N. We might later consider a rebalancing tree algorithm, but it's not clear that the benefit would be worth the cost and complexity. Per report from Sergey Burladyan and an earlier complaint from Heikki. Back-patch to 8.2; older versions didn't have GIN indexes.
Files
| Path | Change | +/− |
|---|---|---|
| src/backend/access/gin/ginfast.c | modified | +5 −4 |
| src/backend/access/gin/gininsert.c | modified | +4 −2 |
| src/include/access/gin.h | modified | +11 −6 |