Class: Innodb::Page::Index
- Inherits:
-
Innodb::Page
- Object
- Innodb::Page
- Innodb::Page::Index
- Defined in:
- lib/innodb/page/index.rb
Overview
A specialized class for handling INDEX pages, which contain a portion of the data from exactly one B+tree. These are typically the most common type of page in any database.
The basic structure of an INDEX page is: FIL header, INDEX header, FSEG header, fixed-width system records (infimum and supremum), user records (the actual data) which grow ascending by offset, free space, the page directory which grows descending by offset, and the FIL trailer.
Direct Known Subclasses
Defined Under Namespace
Classes: Compressed, RecordCursor
Constant Summary collapse
- RECORD_NEXT_SIZE =
The size (in bytes) of the “next” pointer in each record header.
2
- RECORD_REDUNDANT_BITS_SIZE =
The size (in bytes) of the bit-packed fields in each record header for “redundant” record format.
4
- RECORD_REDUNDANT_OFF1_OFFSET_MASK =
Masks for 1-byte record end-offsets within “redundant” records.
0x7f
- RECORD_REDUNDANT_OFF1_NULL_MASK =
0x80
- RECORD_REDUNDANT_OFF2_OFFSET_MASK =
Masks for 2-byte record end-offsets within “redundant” records.
0x3fff
- RECORD_REDUNDANT_OFF2_NULL_MASK =
0x8000
- RECORD_REDUNDANT_OFF2_EXTERN_MASK =
0x4000
- RECORD_COMPACT_BITS_SIZE =
The size (in bytes) of the bit-packed fields in each record header for “compact” record format.
3
- RECORD_MAX_N_SYSTEM_FIELDS =
Maximum number of fields.
3
- RECORD_MAX_N_FIELDS =
1024 - 1
- RECORD_MAX_N_USER_FIELDS =
RECORD_MAX_N_FIELDS - RECORD_MAX_N_SYSTEM_FIELDS * 2
- PAGE_DIRECTION =
Page direction values possible in the page_header’s :direction field.
{ 1 => :left, # Inserts have been in descending order. 2 => :right, # Inserts have been in ascending order. 3 => :same_rec, # Unused by InnoDB. 4 => :same_page, # Unused by InnoDB. 5 => :no_direction, # Inserts have been in random order. }
- RECORD_TYPES =
Record types used in the :type field of the record header.
{ 0 => :conventional, # A normal user record in a leaf page. 1 => :node_pointer, # A node pointer in a non-leaf page. 2 => :infimum, # The system "infimum" record. 3 => :supremum, # The system "supremum" record. }
- RECORD_INFO_MIN_REC_FLAG =
This record is the minimum record at this level of the B-tree.
1
- RECORD_INFO_DELETED_FLAG =
This record has been marked as deleted.
2
- PAGE_DIR_SLOT_SIZE =
The size (in bytes) of the record pointers in each page directory slot.
2
- PAGE_DIR_SLOT_MIN_N_OWNED =
The minimum number of records “owned” by each record with an entry in the page directory.
4
- PAGE_DIR_SLOT_MAX_N_OWNED =
The maximum number of records “owned” by each record with an entry in the page directory.
8
Constants inherited from Innodb::Page
PAGE_TYPE, PAGE_TYPE_BY_VALUE, SPECIALIZED_CLASSES
Instance Attribute Summary
Attributes inherited from Innodb::Page
Instance Method Summary collapse
-
#binary_search_by_directory(dir, key) ⇒ Object
Search or a record within a single page using the page directory to limit the number of record comparisons required.
-
#directory ⇒ Object
Return an array of row offsets for all entries in the page directory.
-
#directory_slot_for_record(this_record) ⇒ Object
Return the slot number for the page directory entry which “owns” the provided record.
-
#directory_slots ⇒ Object
The number of directory slots in use.
-
#directory_space ⇒ Object
The amount of space consumed by the page directory.
-
#dump ⇒ Object
Dump the contents of a page for debugging purposes.
-
#each_child_page ⇒ Object
Iterate through all child pages of a node (non-leaf) page, which are stored as records with the child page number as the last field in the record.
-
#each_garbage_record ⇒ Object
Iterate through all records in the garbage list.
-
#each_record ⇒ Object
Iterate through all records.
- #each_region {|{ :offset => pos_index_header, :length => size_index_header, :name => :index_header, :info => "Index Header", }| ... } ⇒ Object
-
#free_space ⇒ Object
Return the amount of free space in the page.
-
#fseg_header ⇒ Object
Return the “fseg” header.
-
#garbage_offset ⇒ Object
A helper function to return the offset to the first free record.
-
#header_space ⇒ Object
The amount of space consumed by the page header.
-
#index_id ⇒ Object
A helper function to return the index id.
-
#infimum ⇒ Object
Return the infimum record on a page.
-
#level ⇒ Object
A helper function to return the page level from the “page” header, for easier access.
-
#linear_search_from_cursor(search_cursor, key) ⇒ Object
Search for a record within a single page, and return either a perfect match for the key, or the last record closest to they key but not greater than the key.
-
#make_record_description ⇒ Object
Return a set of field objects that describe the record.
-
#max_record ⇒ Object
Return the maximum record on this page.
-
#min_record ⇒ Object
Return the minimum record on this page.
-
#offset_is_directory_slot?(offset) ⇒ Boolean
Return the slot number of the provided offset in the page directory, or nil if the offset is not present in the page directory.
-
#page_header ⇒ Object
Return the “index” header.
-
#pos_directory ⇒ Object
The position of the page directory, which starts at the “fil” trailer and grows backwards from there.
-
#pos_fseg_header ⇒ Object
Return the byte offset of the start of the “fseg” header, which immediately follows the “index” header.
-
#pos_index_header ⇒ Object
Return the byte offset of the start of the “index” page header, which immediately follows the “fil” header.
-
#pos_infimum ⇒ Object
Return the byte offset of the start of the “origin” of the infimum record, which is always the first record in the singly-linked record chain on any page, and represents a record with a “lower value than any possible user record”.
-
#pos_records ⇒ Object
Return the byte offset of the start of records within the page (the position immediately after the page header).
-
#pos_supremum ⇒ Object
Return the byte offset of the start of the “origin” of the supremum record, which is always the last record in the singly-linked record chain on any page, and represents a record with a “higher value than any possible user record”.
-
#pos_user_records ⇒ Object
Return the byte offset of the start of the user records in a page, which immediately follows the supremum record.
-
#record(offset) ⇒ Object
Parse and return a record at a given offset.
-
#record_bytes ⇒ Object
Return the actual bytes of the portion of the page which is used to store user records (eliminate the headers and trailer from the page).
-
#record_cursor(offset = :min, direction = :forward) ⇒ Object
Return a RecordCursor starting at offset.
- #record_describer ⇒ Object
- #record_describer=(o) ⇒ Object
-
#record_fields ⇒ Object
Returns the (ordered) set of fields that describe records in this page.
-
#record_format ⇒ Object
Return (and cache) the record format provided by an external class.
-
#record_header(cursor) ⇒ Object
Return the header from a record.
-
#record_header_compact_additional(header, cursor) ⇒ Object
Read additional header information from a compact format record header.
-
#record_header_compact_null_bitmap(cursor) ⇒ Object
Return an array indicating which fields are null.
-
#record_header_compact_variable_lengths_and_externs(cursor, nulls) ⇒ Object
Return an array containing an array of the length of each variable-length field and an array indicating which fields are stored externally.
-
#record_header_redundant_additional(header, cursor) ⇒ Object
Read additional header information from a redundant format record header.
-
#record_header_redundant_field_end_offsets(header, cursor) ⇒ Object
Read field end offsets from the provided cursor for each field as counted by n_fields.
-
#record_is_directory_slot?(this_record) ⇒ Boolean
Return the slot number of the provided record in the page directory, or nil if the record is not present in the page directory.
-
#record_space ⇒ Object
Return the amount of space occupied by records in the page.
-
#records ⇒ Object
A helper function to return the number of records.
-
#root? ⇒ Boolean
A helper function to identify root index pages; they must be the only pages at their level.
-
#size_fseg_header ⇒ Object
The size of the “fseg” header.
-
#size_index_header ⇒ Object
The size of the “index” header.
-
#size_mum_record ⇒ Object
The size of the data from the supremum or infimum records.
-
#size_mum_record_header_additional ⇒ Object
The size of the additional data structures in the header of the system records, which is just 1 byte in redundant format to store the offset of the end of the field.
-
#size_record_header ⇒ Object
Return the size of the header for each record.
-
#supremum ⇒ Object
Return the supremum record on a page.
-
#system_record(offset) ⇒ Object
Parse and return simple fixed-format system records, such as InnoDB’s internal infimum and supremum records.
-
#trailer_space ⇒ Object
The amount of space consumed by the trailers in the page.
-
#used_space ⇒ Object
Return the amount of used space in the page.
Methods inherited from Innodb::Page
#calculate_checksum, #checksum, #corrupt?, #cursor, #fil_header, handle, #initialize, #inspect, #lsn, maybe_undefined, #name, #next, #offset, parse, #pos_fil_header, #pos_fil_trailer, #pos_page_body, #prev, #size, #size_fil_header, #size_fil_trailer, #type
Constructor Details
This class inherits a constructor from Innodb::Page
Instance Method Details
#binary_search_by_directory(dir, key) ⇒ Object
Search or a record within a single page using the page directory to limit the number of record comparisons required. Once the last page directory entry closest to but not greater than the key is found, fall back to linear search using linear_search_from_cursor to find the closest record whose key is not greater than the desired key. (If an exact match is desired, the returned record must be checked in the same way as the above linear_search_from_cursor function.)
813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 |
# File 'lib/innodb/page/index.rb', line 813 def binary_search_by_directory(dir, key) Innodb::Stats.increment :binary_search_by_directory return nil if dir.empty? # Split the directory at the mid-point (using integer math, so the division # is rounding down). Retrieve the record that sits at the mid-point. mid = ((dir.size-1) / 2) rec = record(dir[mid]) if Innodb.debug? puts "binary_search_by_directory: page=%i, level=%i, dir.size=%i, dir[%i]=(%s)" % [ offset, level, dir.size, mid, rec.key_string, ] end # The mid-point record was the infimum record, which is not comparable with # compare_key, so we need to just linear scan from here. If the mid-point # is the beginning of the page there can't be many records left to check # anyway. if rec.header[:type] == :infimum return linear_search_from_cursor(record_cursor(rec.next), key) end # Compare the desired key to the mid-point record's key. case rec.compare_key(key) when 0 # An exact match for the key was found. Return the record. Innodb::Stats.increment :binary_search_by_directory_exact_match rec when +1 # The mid-point record's key is less than the desired key. if dir.size > 2 # There are more entries remaining from the directory, recurse again # using binary search on the right half of the directory, which # represents values greater than or equal to the mid-point record's # key. Innodb::Stats.increment :binary_search_by_directory_recurse_right binary_search_by_directory(dir[mid...dir.size], key) else next_rec = record(dir[mid+1]) next_key = next_rec && next_rec.compare_key(key) if dir.size == 1 || next_key == -1 || next_key == 0 # This is the last entry remaining from the directory, or our key is # greater than rec and less than rec+1's key. Use linear search to # find the record starting at rec. Innodb::Stats.increment :binary_search_by_directory_linear_search linear_search_from_cursor(record_cursor(rec.offset), key) elsif next_key == +1 Innodb::Stats.increment :binary_search_by_directory_linear_search linear_search_from_cursor(record_cursor(next_rec.offset), key) else nil end end when -1 # The mid-point record's key is greater than the desired key. if dir.size == 1 # If this is the last entry remaining from the directory, we didn't # find anything workable. Innodb::Stats.increment :binary_search_by_directory_empty_result nil else # Recurse on the left half of the directory, which represents values # less than the mid-point record's key. Innodb::Stats.increment :binary_search_by_directory_recurse_left binary_search_by_directory(dir[0...mid], key) end end end |
#directory ⇒ Object
Return an array of row offsets for all entries in the page directory.
596 597 598 599 600 601 602 603 604 605 606 607 |
# File 'lib/innodb/page/index.rb', line 596 def directory return @directory if @directory @directory = [] cursor(pos_directory).backward.name("page_directory") do |c| directory_slots.times do |n| @directory.push c.name("slot[#{n}]") { c.get_uint16 } end end @directory end |
#directory_slot_for_record(this_record) ⇒ Object
Return the slot number for the page directory entry which “owns” the provided record. This will be either the record itself, or the nearest record with an entry in the directory and a value greater than the record.
624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 |
# File 'lib/innodb/page/index.rb', line 624 def directory_slot_for_record(this_record) if slot = record_is_directory_slot?(this_record) return slot end unless search_cursor = record_cursor(this_record.next) raise "Couldn't position cursor" end while rec = search_cursor.record if slot = record_is_directory_slot?(rec) return slot end end return record_is_directory_slot?(supremum) end |
#directory_slots ⇒ Object
The number of directory slots in use.
172 173 174 |
# File 'lib/innodb/page/index.rb', line 172 def directory_slots page_header[:n_dir_slots] end |
#directory_space ⇒ Object
The amount of space consumed by the page directory.
177 178 179 |
# File 'lib/innodb/page/index.rb', line 177 def directory_space directory_slots * PAGE_DIR_SLOT_SIZE end |
#dump ⇒ Object
Dump the contents of a page for debugging purposes.
1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 |
# File 'lib/innodb/page/index.rb', line 1014 def dump super puts "page header:" pp page_header puts puts "fseg header:" pp fseg_header puts puts "sizes:" puts " %-15s%5i" % [ "header", header_space ] puts " %-15s%5i" % [ "trailer", trailer_space ] puts " %-15s%5i" % [ "directory", directory_space ] puts " %-15s%5i" % [ "free", free_space ] puts " %-15s%5i" % [ "used", used_space ] puts " %-15s%5i" % [ "record", record_space ] puts " %-15s%5.2f" % [ "per record", (page_header[:n_recs] > 0) ? (record_space / page_header[:n_recs]) : 0 ] puts puts "page directory:" pp directory puts puts "system records:" pp infimum.record pp supremum.record puts puts "garbage records:" each_garbage_record do |rec| pp rec.record puts end puts puts "records:" each_record do |rec| pp rec.record puts end puts end |
#each_child_page ⇒ Object
Iterate through all child pages of a node (non-leaf) page, which are stored as records with the child page number as the last field in the record.
925 926 927 928 929 930 931 932 933 934 935 936 937 |
# File 'lib/innodb/page/index.rb', line 925 def each_child_page return nil if level == 0 unless block_given? return enum_for(:each_child_page) end each_record do |rec| yield rec.child_page_number, rec.key end nil end |
#each_garbage_record ⇒ Object
Iterate through all records in the garbage list.
904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 |
# File 'lib/innodb/page/index.rb', line 904 def each_garbage_record unless block_given? return enum_for(:each_garbage_record) end if garbage_offset == 0 return nil end c = record_cursor(garbage_offset) while rec = c.record yield rec end nil end |
#each_record ⇒ Object
Iterate through all records.
889 890 891 892 893 894 895 896 897 898 899 900 901 |
# File 'lib/innodb/page/index.rb', line 889 def each_record unless block_given? return enum_for(:each_record) end c = record_cursor(:min) while rec = c.record yield rec end nil end |
#each_region {|{ :offset => pos_index_header, :length => size_index_header, :name => :index_header, :info => "Index Header", }| ... } ⇒ Object
939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 |
# File 'lib/innodb/page/index.rb', line 939 def each_region unless block_given? return enum_for(:each_region) end super do |region| yield region end yield({ :offset => pos_index_header, :length => size_index_header, :name => :index_header, :info => "Index Header", }) yield({ :offset => pos_fseg_header, :length => size_fseg_header, :name => :fseg_header, :info => "File Segment Header", }) yield({ :offset => pos_infimum - 5, :length => size_mum_record + 5, :name => :infimum, :info => "Infimum", }) yield({ :offset => pos_supremum - 5, :length => size_mum_record + 5, :name => :supremum, :info => "Supremum", }) directory_slots.times do |n| yield({ :offset => pos_directory - (n * 2), :length => 2, :name => :directory, :info => "Page Directory", }) end each_garbage_record do |record| yield({ :offset => record.offset - record.header[:length], :length => record.length + record.header[:length], :name => :garbage, :info => "Garbage", }) end each_record do |record| yield({ :offset => record.offset - record.header[:length], :length => record.header[:length], :name => :record_header, :info => "Record Header", }) yield({ :offset => record.offset, :length => record.length || 1, :name => :record_data, :info => "Record Data", }) end nil end |
#free_space ⇒ Object
Return the amount of free space in the page.
187 188 189 190 |
# File 'lib/innodb/page/index.rb', line 187 def free_space page_header[:garbage_size] + (size - size_fil_trailer - directory_space - page_header[:heap_top]) end |
#fseg_header ⇒ Object
Return the “fseg” header.
262 263 264 265 266 267 268 269 270 271 272 273 |
# File 'lib/innodb/page/index.rb', line 262 def fseg_header @fseg_header ||= cursor(pos_fseg_header).name("fseg") do |c| { :leaf => c.name("fseg[leaf]") { Innodb::FsegEntry.get_inode(@space, c) }, :internal => c.name("fseg[internal]") { Innodb::FsegEntry.get_inode(@space, c) }, } end end |
#garbage_offset ⇒ Object
A helper function to return the offset to the first free record.
257 258 259 |
# File 'lib/innodb/page/index.rb', line 257 def garbage_offset page_header && page_header[:garbage_offset] end |
#header_space ⇒ Object
The amount of space consumed by the page header.
165 166 167 168 169 |
# File 'lib/innodb/page/index.rb', line 165 def header_space # The end of the supremum system record is the beginning of the space # available for user records. pos_user_records end |
#index_id ⇒ Object
A helper function to return the index id.
235 236 237 |
# File 'lib/innodb/page/index.rb', line 235 def index_id page_header && page_header[:index_id] end |
#infimum ⇒ Object
Return the infimum record on a page.
461 462 463 |
# File 'lib/innodb/page/index.rb', line 461 def infimum @infimum ||= system_record(pos_infimum) end |
#level ⇒ Object
A helper function to return the page level from the “page” header, for easier access.
241 242 243 |
# File 'lib/innodb/page/index.rb', line 241 def level page_header && page_header[:level] end |
#linear_search_from_cursor(search_cursor, key) ⇒ Object
Search for a record within a single page, and return either a perfect match for the key, or the last record closest to they key but not greater than the key. (If an exact match is desired, compare_key must be used to check if the returned record matches. This makes the function useful for search in both leaf and non-leaf pages.)
758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 |
# File 'lib/innodb/page/index.rb', line 758 def linear_search_from_cursor(search_cursor, key) Innodb::Stats.increment :linear_search_from_cursor this_rec = search_cursor.record if Innodb.debug? puts "linear_search_from_cursor: page=%i, level=%i, start=(%s)" % [ offset, level, this_rec && this_rec.key_string, ] end # Iterate through all records until finding either a matching record or # one whose key is greater than the desired key. while this_rec && next_rec = search_cursor.record Innodb::Stats.increment :linear_search_from_cursor_record_scans if Innodb.debug? puts "linear_search_from_cursor: page=%i, level=%i, current=(%s)" % [ offset, level, this_rec && this_rec.key_string, ] end # If we reach supremum, return the last non-system record we got. return this_rec if next_rec.header[:type] == :supremum if this_rec.compare_key(key) < 0 return this_rec end if (this_rec.compare_key(key) >= 0) && (next_rec.compare_key(key) < 0) # The desired key is either an exact match for this_rec or is greater # than it but less than next_rec. If this is a non-leaf page, that # will mean that the record will fall on the leaf page this node # pointer record points to, if it exists at all. return this_rec end this_rec = next_rec end this_rec end |
#make_record_description ⇒ Object
Return a set of field objects that describe the record.
488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 |
# File 'lib/innodb/page/index.rb', line 488 def make_record_description position = (0..RECORD_MAX_N_FIELDS).each description = record_describer.description fields = {:type => description[:type], :key => [], :sys => [], :row => []} description[:key].each do |field| fields[:key] << Innodb::Field.new(position.next, field[:name], *field[:type]) end # If this is a leaf page of the clustered index, read InnoDB's internal # fields, a transaction ID and roll pointer. if level == 0 && fields[:type] == :clustered [["DB_TRX_ID", :TRX_ID,],["DB_ROLL_PTR", :ROLL_PTR]].each do |name, type| fields[:sys] << Innodb::Field.new(position.next, name, type, :NOT_NULL) end end # If this is a leaf page of the clustered index, or any page of a # secondary index, read the non-key fields. if (level == 0 && fields[:type] == :clustered) || (fields[:type] == :secondary) description[:row].each do |field| fields[:row] << Innodb::Field.new(position.next, field[:name], *field[:type]) end end fields end |
#max_record ⇒ Object
Return the maximum record on this page.
740 741 742 743 744 745 746 747 748 749 750 751 |
# File 'lib/innodb/page/index.rb', line 740 def max_record # Since the records are only singly-linked in the forward direction, in # order to do find the last record, we must create a cursor and walk # backwards one step. unless max_cursor = record_cursor(supremum.offset, :backward) raise "Couldn't position cursor" end # Note the deliberate use of prev_record rather than record; we want # to skip over supremum itself. max = max_cursor.prev_record max if max != infimum end |
#min_record ⇒ Object
Return the minimum record on this page.
734 735 736 737 |
# File 'lib/innodb/page/index.rb', line 734 def min_record min = record(infimum.next) min if min != supremum end |
#offset_is_directory_slot?(offset) ⇒ Boolean
Return the slot number of the provided offset in the page directory, or nil if the offset is not present in the page directory.
611 612 613 |
# File 'lib/innodb/page/index.rb', line 611 def offset_is_directory_slot?(offset) directory.index(offset) end |
#page_header ⇒ Object
Return the “index” header.
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 |
# File 'lib/innodb/page/index.rb', line 209 def page_header @page_header ||= cursor(pos_index_header).name("index") do |c| index = { :n_dir_slots => c.name("n_dir_slots") { c.get_uint16 }, :heap_top => c.name("heap_top") { c.get_uint16 }, :n_heap_format => c.name("n_heap_format") { c.get_uint16 }, :garbage_offset => c.name("garbage_offset") { c.get_uint16 }, :garbage_size => c.name("garbage_size") { c.get_uint16 }, :last_insert_offset => c.name("last_insert_offset") { c.get_uint16 }, :direction => c.name("direction") { PAGE_DIRECTION[c.get_uint16] }, :n_direction => c.name("n_direction") { c.get_uint16 }, :n_recs => c.name("n_recs") { c.get_uint16 }, :max_trx_id => c.name("max_trx_id") { c.get_uint64 }, :level => c.name("level") { c.get_uint16 }, :index_id => c.name("index_id") { c.get_uint64 }, } index[:n_heap] = index[:n_heap_format] & (2**15-1) index[:format] = (index[:n_heap_format] & 1<<15) == 0 ? :redundant : :compact index.delete :n_heap_format index end end |
#pos_directory ⇒ Object
The position of the page directory, which starts at the “fil” trailer and grows backwards from there.
160 161 162 |
# File 'lib/innodb/page/index.rb', line 160 def pos_directory pos_fil_trailer end |
#pos_fseg_header ⇒ Object
Return the byte offset of the start of the “fseg” header, which immediately follows the “index” header.
86 87 88 |
# File 'lib/innodb/page/index.rb', line 86 def pos_fseg_header pos_index_header + size_index_header end |
#pos_index_header ⇒ Object
Return the byte offset of the start of the “index” page header, which immediately follows the “fil” header.
75 76 77 |
# File 'lib/innodb/page/index.rb', line 75 def pos_index_header pos_fil_header + size_fil_header end |
#pos_infimum ⇒ Object
Return the byte offset of the start of the “origin” of the infimum record, which is always the first record in the singly-linked record chain on any page, and represents a record with a “lower value than any possible user record”. The infimum record immediately follows the page header.
127 128 129 130 131 |
# File 'lib/innodb/page/index.rb', line 127 def pos_infimum pos_records + size_record_header + size_mum_record_header_additional end |
#pos_records ⇒ Object
Return the byte offset of the start of records within the page (the position immediately after the page header).
146 147 148 149 150 |
# File 'lib/innodb/page/index.rb', line 146 def pos_records size_fil_header + size_index_header + size_fseg_header end |
#pos_supremum ⇒ Object
Return the byte offset of the start of the “origin” of the supremum record, which is always the last record in the singly-linked record chain on any page, and represents a record with a “higher value than any possible user record”. The supremum record immediately follows the infimum record.
137 138 139 140 141 142 |
# File 'lib/innodb/page/index.rb', line 137 def pos_supremum pos_infimum + size_record_header + size_mum_record_header_additional + size_mum_record end |
#pos_user_records ⇒ Object
Return the byte offset of the start of the user records in a page, which immediately follows the supremum record.
154 155 156 |
# File 'lib/innodb/page/index.rb', line 154 def pos_user_records pos_supremum + size_mum_record end |
#record(offset) ⇒ Object
Parse and return a record at a given offset.
531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 |
# File 'lib/innodb/page/index.rb', line 531 def record(offset) return nil unless offset return infimum if offset == pos_infimum return supremum if offset == pos_supremum cursor(offset).forward.name("record[#{offset}]") do |c| # There is a header preceding the row itself, so back up and read it. header = c.peek { record_header(c) } this_record = { :format => page_header[:format], :offset => offset, :header => header, :next => header[:next] == 0 ? nil : (header[:next]), } if record_format this_record[:type] = record_format[:type] # Used to indicate whether a field is part of key/row/sys. fmap = [:key, :row, :sys].inject({}) do |h, k| this_record[k] = [] record_format[k].each { |f| h[f.position] = k } h end # Read the fields present in this record. record_fields.each do |f| p = fmap[f.position] c.name("#{p.to_s}[#{f.name}]") do this_record[p] << { :name => f.name, :type => f.data_type.name, :value => f.value(c, this_record), :extern => f.extern(c, this_record), }.reject { |k, v| v.nil? } end end # If this is a node (non-leaf) page, it will have a child page number # (or "node pointer") stored as the last field. if level > 0 # Read the node pointer in a node (non-leaf) page. this_record[:child_page_number] = c.name("child_page_number") { c.get_uint32 } end this_record[:length] = c.position - offset # Add system field accessors for convenience. this_record[:sys].each do |f| case f[:name] when "DB_TRX_ID" this_record[:transaction_id] = f[:value] when "DB_ROLL_PTR" this_record[:roll_pointer] = f[:value] end end end Innodb::Record.new(self, this_record) end end |
#record_bytes ⇒ Object
Return the actual bytes of the portion of the page which is used to store user records (eliminate the headers and trailer from the page).
204 205 206 |
# File 'lib/innodb/page/index.rb', line 204 def record_bytes data(pos_user_records, page_header[:heap_top] - pos_user_records) end |
#record_cursor(offset = :min, direction = :forward) ⇒ Object
Return a RecordCursor starting at offset.
729 730 731 |
# File 'lib/innodb/page/index.rb', line 729 def record_cursor(offset=:min, direction=:forward) RecordCursor.new(self, offset, direction) end |
#record_describer ⇒ Object
474 475 476 477 478 479 480 481 482 483 484 485 |
# File 'lib/innodb/page/index.rb', line 474 def record_describer return @record_describer if @record_describer if space and space.innodb_system and index_id @record_describer = space.innodb_system.data_dictionary.record_describer_by_index_id(index_id) elsif space @record_describer = space.record_describer end @record_describer end |
#record_describer=(o) ⇒ Object
470 471 472 |
# File 'lib/innodb/page/index.rb', line 470 def record_describer=(o) @record_describer = o end |
#record_fields ⇒ Object
Returns the (ordered) set of fields that describe records in this page.
524 525 526 527 528 |
# File 'lib/innodb/page/index.rb', line 524 def record_fields if record_format record_format.values_at(:key, :sys, :row).flatten.sort_by {|f| f.position} end end |
#record_format ⇒ Object
Return (and cache) the record format provided by an external class.
517 518 519 520 521 |
# File 'lib/innodb/page/index.rb', line 517 def record_format if record_describer @record_format ||= make_record_description() end end |
#record_header(cursor) ⇒ Object
Return the header from a record.
276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 |
# File 'lib/innodb/page/index.rb', line 276 def record_header(cursor) origin = cursor.position header = {} cursor.backward.name("header") do |c| case page_header[:format] when :compact # The "next" pointer is a relative offset from the current record. header[:next] = c.name("next") { origin + c.get_sint16 } # Fields packed in a 16-bit integer (LSB first): # 3 bits for type # 13 bits for heap_number bits1 = c.name("bits1") { c.get_uint16 } header[:type] = RECORD_TYPES[bits1 & 0x07] header[:heap_number] = (bits1 & 0xf8) >> 3 when :redundant # The "next" pointer is an absolute offset within the page. header[:next] = c.name("next") { c.get_uint16 } # Fields packed in a 24-bit integer (LSB first): # 1 bit for offset_size (0 = 2 bytes, 1 = 1 byte) # 10 bits for n_fields # 13 bits for heap_number bits1 = c.name("bits1") { c.get_uint24 } header[:offset_size] = (bits1 & 1) == 0 ? 2 : 1 header[:n_fields] = (bits1 & (((1 << 10) - 1) << 1)) >> 1 header[:heap_number] = (bits1 & (((1 << 13) - 1) << 11)) >> 11 end # Fields packed in an 8-bit integer (LSB first): # 4 bits for n_owned # 4 bits for flags bits2 = c.name("bits2") { c.get_uint8 } header[:n_owned] = bits2 & 0x0f info = (bits2 & 0xf0) >> 4 header[:min_rec] = (info & RECORD_INFO_MIN_REC_FLAG) != 0 header[:deleted] = (info & RECORD_INFO_DELETED_FLAG) != 0 case page_header[:format] when :compact record_header_compact_additional(header, cursor) when :redundant record_header_redundant_additional(header, cursor) end header[:length] = origin - cursor.position end header end |
#record_header_compact_additional(header, cursor) ⇒ Object
Read additional header information from a compact format record header.
328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 |
# File 'lib/innodb/page/index.rb', line 328 def record_header_compact_additional(header, cursor) case header[:type] when :conventional, :node_pointer # The variable-length part of the record header contains a # bit vector indicating NULL fields and the length of each # non-NULL variable-length field. if record_format header[:nulls] = cursor.name("nulls") { record_header_compact_null_bitmap(cursor) } header[:lengths], header[:externs] = cursor.name("lengths_and_externs") { record_header_compact_variable_lengths_and_externs(cursor, header[:nulls]) } end end end |
#record_header_compact_null_bitmap(cursor) ⇒ Object
Return an array indicating which fields are null.
348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 |
# File 'lib/innodb/page/index.rb', line 348 def record_header_compact_null_bitmap(cursor) fields = record_fields # The number of bits in the bitmap is the number of nullable fields. size = fields.count { |f| f.nullable? } # There is no bitmap if there are no nullable fields. return [] unless size > 0 null_bit_array = cursor.get_bit_array(size).reverse! # For every nullable field, select the ones which are actually null. fields.inject([]) do |nulls, f| nulls << f.name if f.nullable? && (null_bit_array.shift == 1) nulls end end |
#record_header_compact_variable_lengths_and_externs(cursor, nulls) ⇒ Object
Return an array containing an array of the length of each variable-length field and an array indicating which fields are stored externally.
368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 |
# File 'lib/innodb/page/index.rb', line 368 def record_header_compact_variable_lengths_and_externs(cursor, nulls) fields = (record_format[:key] + record_format[:row]) lengths = {} externs = [] # For each non-NULL variable-length field, the record header contains # the length in one or two bytes. fields.each do |f| next if !f.variable? || nulls.include?(f.name) len = cursor.get_uint8 ext = false # Two bytes are used only if the length exceeds 127 bytes and the # maximum length exceeds 255 bytes (or the field is a BLOB type). if len > 127 && (f.blob? || f.data_type.width > 255) ext = (0x40 & len) != 0 len = ((len & 0x3f) << 8) + cursor.get_uint8 end lengths[f.name] = len externs << f.name if ext end return lengths, externs end |
#record_header_redundant_additional(header, cursor) ⇒ Object
Read additional header information from a redundant format record header.
397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 |
# File 'lib/innodb/page/index.rb', line 397 def record_header_redundant_additional(header, cursor) lengths, nulls, externs = [], [], [] field_offsets = record_header_redundant_field_end_offsets(header, cursor) this_field_offset = 0 field_offsets.each do |n| case header[:offset_size] when 1 next_field_offset = (n & RECORD_REDUNDANT_OFF1_OFFSET_MASK) lengths << (next_field_offset - this_field_offset) nulls << ((n & RECORD_REDUNDANT_OFF1_NULL_MASK) != 0) externs << false when 2 next_field_offset = (n & RECORD_REDUNDANT_OFF2_OFFSET_MASK) lengths << (next_field_offset - this_field_offset) nulls << ((n & RECORD_REDUNDANT_OFF2_NULL_MASK) != 0) externs << ((n & RECORD_REDUNDANT_OFF2_EXTERN_MASK) != 0) end this_field_offset = next_field_offset end # If possible, refer to fields by name rather than position for # better formatting (i.e. pp). if record_format header[:lengths], header[:nulls], header[:externs] = {}, [], [] record_fields.each do |f| header[:lengths][f.name] = lengths[f.position] header[:nulls] << f.name if nulls[f.position] header[:externs] << f.name if externs[f.position] end else header[:lengths], header[:nulls], header[:externs] = lengths, nulls, externs end end |
#record_header_redundant_field_end_offsets(header, cursor) ⇒ Object
Read field end offsets from the provided cursor for each field as counted by n_fields.
436 437 438 439 440 441 442 443 |
# File 'lib/innodb/page/index.rb', line 436 def record_header_redundant_field_end_offsets(header, cursor) (0...header[:n_fields]).to_a.inject([]) do |offsets, n| cursor.name("field_end_offset[#{n}]") { offsets << cursor.get_uint_by_size(header[:offset_size]) } offsets end end |
#record_is_directory_slot?(this_record) ⇒ Boolean
Return the slot number of the provided record in the page directory, or nil if the record is not present in the page directory.
617 618 619 |
# File 'lib/innodb/page/index.rb', line 617 def record_is_directory_slot?(this_record) offset_is_directory_slot?(this_record.offset) end |
#record_space ⇒ Object
Return the amount of space occupied by records in the page.
198 199 200 |
# File 'lib/innodb/page/index.rb', line 198 def record_space used_space - header_space - directory_space - trailer_space end |
#records ⇒ Object
A helper function to return the number of records.
246 247 248 |
# File 'lib/innodb/page/index.rb', line 246 def records page_header && page_header[:n_recs] end |
#root? ⇒ Boolean
A helper function to identify root index pages; they must be the only pages at their level.
252 253 254 |
# File 'lib/innodb/page/index.rb', line 252 def root? self.prev.nil? && self.next.nil? end |
#size_fseg_header ⇒ Object
The size of the “fseg” header.
91 92 93 |
# File 'lib/innodb/page/index.rb', line 91 def size_fseg_header 2 * Innodb::FsegEntry::SIZE end |
#size_index_header ⇒ Object
The size of the “index” header.
80 81 82 |
# File 'lib/innodb/page/index.rb', line 80 def size_index_header 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 2 + 8 + 2 + 8 end |
#size_mum_record ⇒ Object
The size of the data from the supremum or infimum records.
119 120 121 |
# File 'lib/innodb/page/index.rb', line 119 def size_mum_record 8 end |
#size_mum_record_header_additional ⇒ Object
The size of the additional data structures in the header of the system records, which is just 1 byte in redundant format to store the offset of the end of the field. This is needed specifically here since we need to be able to calculate the fixed positions of these system records.
109 110 111 112 113 114 115 116 |
# File 'lib/innodb/page/index.rb', line 109 def size_mum_record_header_additional case page_header[:format] when :compact 0 # No additional data is stored in compact format. when :redundant 1 # A 1-byte offset for 1 field is stored in redundant format. end end |
#size_record_header ⇒ Object
Return the size of the header for each record.
96 97 98 99 100 101 102 103 |
# File 'lib/innodb/page/index.rb', line 96 def size_record_header case page_header[:format] when :compact RECORD_NEXT_SIZE + RECORD_COMPACT_BITS_SIZE when :redundant RECORD_NEXT_SIZE + RECORD_REDUNDANT_BITS_SIZE end end |
#supremum ⇒ Object
Return the supremum record on a page.
466 467 468 |
# File 'lib/innodb/page/index.rb', line 466 def supremum @supremum ||= system_record(pos_supremum) end |
#system_record(offset) ⇒ Object
Parse and return simple fixed-format system records, such as InnoDB’s internal infimum and supremum records.
447 448 449 450 451 452 453 454 455 456 457 458 |
# File 'lib/innodb/page/index.rb', line 447 def system_record(offset) cursor(offset).name("record[#{offset}]") do |c| header = c.peek { record_header(c) } Innodb::Record.new(self, { :offset => offset, :header => header, :next => header[:next], :data => c.name("data") { c.get_bytes(size_mum_record) }, :length => c.position - offset, }) end end |
#trailer_space ⇒ Object
The amount of space consumed by the trailers in the page.
182 183 184 |
# File 'lib/innodb/page/index.rb', line 182 def trailer_space size_fil_trailer end |
#used_space ⇒ Object
Return the amount of used space in the page.
193 194 195 |
# File 'lib/innodb/page/index.rb', line 193 def used_space size - free_space end |