On Thu, Sep 8, 2016 at 6:44 AM, Peter Geoghegan <p...@heroku.com> wrote: > On Fri, Sep 2, 2016 at 11:19 AM, Kevin Grittner <kgri...@gmail.com> wrote: >> IMV the process is to post a patch to this list to certify that it >> is yours to contribute and free of IP encumbrances that would >> prevent us from using it. I will wait for that post. > > I attach my V3
+ * Ideally, we'd compare every item in the index against every other + * item in the index, and not trust opclass obedience of the transitive + * law to bridge the gap between children and their grandparents (as + * well as great-grandparents, and so on). We don't go to those + * lengths because that would be prohibitively expensive, and probably + * not markedly more effective in practice. + */ I skimmed the Modern B-Tree Techniques paper recently, and there was a section on "the cousin problem" when verifying btrees, which this comment reminded me of. I tried to come up with an example of a pair of characters being switched in a collation that would introduce undetectable corruption: T1. Order = a < b < c < d Btree = [a|c] / \ / \ / \ [a]-------[c] | | | | [b]-------[d] T2. Order = a < c < b < d Now c and b have been switched around. Won't amcheck still pass since we only verify immediate downlinks and siblings? Yet searches for b will take a wrong turn at the root. Do I have this right? I wonder if there is a way to verify that each page's high key < the 'next' key for all ancestors. -- Thomas Munro http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers