On Fri, Nov 18, 2016 at 12:17 PM, Peter Geoghegan <p...@heroku.com> wrote: > So, the Btree you show is supposed to be good? You've left it up to me > to draw T2, the corrupt version? If so, here is a drawing of T2 for > the sake of clarity: > > Btree = [a|b] > / \ > / \ > / \ > [a]-------[b] > | | > | | > [c]-------[d]
Actually I meant that at T2 the btree is exactly same as it was at T1, but the order of the values has changed according to the comparator (for example, because a collation definition changed when you updated your operating system), so that the btree is now corrupted. Based on Goetz Graefe's paper I was wondering if amcheck would be unable to detect this due to the cousin problem. >> 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. > > I don't think you have it right, because your argument is predicated > on classic L&Y, not the Postgres variant. The high key is literally > guaranteed to be *equal* to the initial first value of the right half > of a split page post-split (at least initially), which is where the > new downlink for the new right half comes from in turn, so it will be > exactly equal as well. There is a comment which says all this within > _bt_insert_parent(), actually. > > In general, I think it's pretty bad that we're so loose about > representing the key space in downlinks compared to classic L&Y, > because it probably makes index bloat a lot worse in internal pages, > messing up the key space long term. As long as we're doing that, > though, we clearly cannot usefully "verify that each page's high key < > the 'next' key for all ancestors", because we deviate from L&Y in a > way that makes that check always fail. It's okay that it always fails > for us (it doesn't actually indicate corruption), because of our > duplicate-aware index scan logic (change to invariant). > > In summary, I'm pretty sure that our "Ki <= v <= Ki+1" thing makes the > cousin problem a non-issue, because we don't follow downlinks that are > equal to our scankey -- we go to their immediate left and start > *there*, in order to support duplicates in leaf pages. Index scans for > 'b' work for both T1 and T2 in Postgres, because we refuse to follow > the 'b' downlinks when doing an index scan for 'b' (relevant to T2). I > would actually like to change things to make the invariant the classic > L&Y "Ki < v <= Ki+1", to avoid bloat in the internal pages and to make > suffix truncation in internal pages work. > > So, we don't have the cousin problem, but since I wish for us to adopt > the stricter classic L&Y invariant at some point, you could say that I > also wished that we had the cousin problem. Thank you for your patient explanation! Please see my humble attempt to test this scenario and learn something about btrees in the process, attached. amcheck does detect the violation of the high key invariant. > Confused yet? :-) Yes. But it's getting better slowly :-) -- Thomas Munro http://www.enterprisedb.com
create extension if not exists amcheck; create extension if not exists pageinspect; drop table if exists my_table; drop type if exists my_type; -- define an enum ordered a, b, c, d, but do it in a funky way that results in -- odd OIDs that we can later mess around with create type my_type as enum ('d'); alter type my_type add value 'c' before 'd'; alter type my_type add value 'b' before 'c'; alter type my_type add value 'a' before 'b'; create table my_table (my_column my_type, counter serial); create index my_index on my_table(my_column); create or replace function pretty_print_btree_recurse(pageno int, height int, level int) returns void language plpgsql as $$ declare v_spaces text := rpad('', (height - level) * 2, ' '); v_ctid text; v_subpageno int; v_key_hex text; v_key_oid oid; v_key_label text; v_page_description text; v_item int; begin if height = level then v_page_description := 'root'; elsif level = 0 then v_page_description := 'leaf'; else v_page_description := 'intl'; end if; for v_ctid, v_key_hex, v_item in select ctid::text, data, itemoffset from bt_page_items('my_index', pageno) loop if v_ctid like '(4294967295,%' then continue; end if; v_subpageno := (v_ctid::point); v_key_oid := ('x' || substring(v_key_hex, 1, 2))::bit(8)::int + (('x' || substring(v_key_hex, 4, 2))::bit(8)::int << 8); v_key_label := coalesce((select enumlabel from pg_enum where oid = v_key_oid::oid), '-inf'); if level = 0 then raise info '% % page % item %: [%] -> heap tuple', v_spaces, v_page_description, pageno, v_item - 1, v_key_label; else raise info '% % page % item %: [%] -> page %', v_spaces, v_page_description, pageno, v_item, v_key_label, v_subpageno; end if; if level > 0 then perform pretty_print_btree_recurse(v_subpageno, height, level - 1); end if; end loop; end; $$; create or replace function pretty_print_btree() returns void language plpgsql as $$ declare v_root int; v_height int; begin select root, level into v_root, v_height from bt_metap('my_index'); if v_root = 0 then raise info 'empty btree'; else perform pretty_print_btree_recurse(v_root, v_height, v_height); end if; end; $$; truncate my_table; insert into my_table (my_column) select 'a' from generate_series(1, 64000); insert into my_table (my_column) select 'c' from generate_series(1, 64000); insert into my_table (my_column) select 'b' from generate_series(1, 64000); insert into my_table (my_column) select 'd' from generate_series(1, 64000); delete from my_table where my_column = 'a' and counter > (select min(counter) from my_table where my_column = 'a'); delete from my_table where my_column = 'b' and counter > (select min(counter) from my_table where my_column = 'b'); delete from my_table where my_column = 'c' and counter > (select min(counter) from my_table where my_column = 'c'); delete from my_table where my_column = 'd' and counter > (select min(counter) from my_table where my_column = 'd'); vacuum my_table; -- now we have a btree that looks like this: -- Btree = [a|c] -- / \ -- / \ -- / \ -- [a]-------[c] -- | | -- | | -- [b]-------[d] select pretty_print_btree(); set seq_page_cost to 100; set enable_bitmapscan to false; -- we can find b by index scan select * from my_table where my_column = 'b'; -- now mess with the sort order of the enum, as a cheap hack way to simulate -- a collation order change affecting a text field. this switches the order -- of 'b' and 'c' around in the enum update pg_enum set enumsortorder = 999 where enumtypid = 'my_type'::regtype and enumlabel = 'c'; update pg_enum set enumsortorder = 0 where enumtypid = 'my_type'::regtype and enumlabel = 'b'; update pg_enum set enumsortorder = -1 where enumtypid = 'my_type'::regtype and enumlabel = 'c'; -- log out and back in again to nuke syscache -- now we can't find 'b' by index scan anymore! set seq_page_cost to 100; set enable_bitmapscan to false; select * from my_table where my_column = 'b'; -- let's see what amcheck says about that select bt_index_check('my_index'); ERROR: high key invariant violated for index "my_index"
-- Sent via pgsql-hackers mailing list (firstname.lastname@example.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers