On Thu, Sep 8, 2016 at 6:44 AM, Peter Geoghegan <pg@heroku.com> wrote:
> On Fri, Sep 2, 2016 at 11:19 AM, Kevin Grittner <kgrittn@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