Get `gn gen` to succeed on Windows

third_party/sqlite/src/tool/spaceanal.tcl

Index: third_party/sqlite/src/tool/spaceanal.tcl
diff --git a/third_party/sqlite/src/tool/spaceanal.tcl b/third_party/sqlite/src/tool/spaceanal.tcl
new file mode 100644
index 0000000000000000000000000000000000000000..bf6244e8c994c269b3f7d4cfd356bd7da6548574
--- /dev/null
+++ b/third_party/sqlite/src/tool/spaceanal.tcl
@@ -0,0 +1,626 @@
+# Run this TCL script using "testfixture" in order get a report that shows
+# how much disk space is used by a particular data to actually store data
+# versus how much space is unused.
+#
+
+if {[catch {
+
+# Get the name of the database to analyze
+#
+#set argv $argv0
+if {[llength $argv]!=1} {
+  puts stderr "Usage: $argv0 database-name"
+  exit 1
+}
+set file_to_analyze [lindex $argv 0]
+if {![file exists $file_to_analyze]} {
+  puts stderr "No such file: $file_to_analyze"
+  exit 1
+}
+if {![file readable $file_to_analyze]} {
+  puts stderr "File is not readable: $file_to_analyze"
+  exit 1
+}
+if {[file size $file_to_analyze]<512} {
+  puts stderr "Empty or malformed database: $file_to_analyze"
+  exit 1
+}
+
+# Open the database
+#
+sqlite3 db [lindex $argv 0]
+register_dbstat_vtab db
+
+set pageSize [db one {PRAGMA page_size}]
+
+#set DB [btree_open [lindex $argv 0] 1000 0]
+
+# In-memory database for collecting statistics. This script loops through
+# the tables and indices in the database being analyzed, adding a row for each
+# to an in-memory database (for which the schema is shown below). It then
+# queries the in-memory db to produce the space-analysis report.
+#
+sqlite3 mem :memory:
+set tabledef\
+{CREATE TABLE space_used(
+   name clob,        -- Name of a table or index in the database file
+   tblname clob,     -- Name of associated table
+   is_index boolean, -- TRUE if it is an index, false for a table
+   nentry int,       -- Number of entries in the BTree
+   leaf_entries int, -- Number of leaf entries
+   payload int,      -- Total amount of data stored in this table or index
+   ovfl_payload int, -- Total amount of data stored on overflow pages
+   ovfl_cnt int,     -- Number of entries that use overflow
+   mx_payload int,   -- Maximum payload size
+   int_pages int,    -- Number of interior pages used
+   leaf_pages int,   -- Number of leaf pages used
+   ovfl_pages int,   -- Number of overflow pages used
+   int_unused int,   -- Number of unused bytes on interior pages
+   leaf_unused int,  -- Number of unused bytes on primary pages
+   ovfl_unused int,  -- Number of unused bytes on overflow pages
+   gap_cnt int       -- Number of gaps in the page layout
+);}
+mem eval $tabledef
+
+# Create a temporary "dbstat" virtual table.
+#
+db eval { 
+  CREATE VIRTUAL TABLE temp.stat USING dbstat;
+  CREATE TEMP TABLE dbstat AS SELECT * FROM temp.stat ORDER BY name, path;
+  DROP TABLE temp.stat;
+}
+
+proc isleaf {pagetype is_index} {
+  return [expr {$pagetype == "leaf" || ($pagetype == "internal" && $is_index)}]
+}
+proc isoverflow {pagetype is_index} {
+  return [expr {$pagetype == "overflow"}]
+}
+proc isinternal {pagetype is_index} {
+  return [expr {$pagetype == "internal" && $is_index==0}]
+}
+
+db func isleaf isleaf
+db func isinternal isinternal
+db func isoverflow isoverflow
+
+set sql { SELECT name, tbl_name FROM sqlite_master WHERE rootpage>0 }
+foreach {name tblname} [concat sqlite_master sqlite_master [db eval $sql]] {
+
+  set is_index [expr {$name!=$tblname}]
+  db eval {
+    SELECT 
+      sum(ncell) AS nentry,
+      sum(isleaf(pagetype, $is_index) * ncell) AS leaf_entries,
+      sum(payload) AS payload,
+      sum(isoverflow(pagetype, $is_index) * payload) AS ovfl_payload,
+      sum(path LIKE '%+000000') AS ovfl_cnt,
+      max(mx_payload) AS mx_payload,
+      sum(isinternal(pagetype, $is_index)) AS int_pages,
+      sum(isleaf(pagetype, $is_index)) AS leaf_pages,
+      sum(isoverflow(pagetype, $is_index)) AS ovfl_pages,
+      sum(isinternal(pagetype, $is_index) * unused) AS int_unused,
+      sum(isleaf(pagetype, $is_index) * unused) AS leaf_unused,
+      sum(isoverflow(pagetype, $is_index) * unused) AS ovfl_unused
+    FROM temp.dbstat WHERE name = $name
+  } break
+
+  # Column 'gap_cnt' is set to the number of non-contiguous entries in the
+  # list of pages visited if the b-tree structure is traversed in a top-down
+  # fashion (each node visited before its child-tree is passed). Any overflow
+  # chains present are traversed from start to finish before any child-tree
+  # is.
+  #
+  set gap_cnt 0
+  set pglist [db eval {
+    SELECT pageno FROM temp.dbstat WHERE name = $name ORDER BY rowid
+  }]
+  set prev [lindex $pglist 0]
+  foreach pgno [lrange $pglist 1 end] {
+    if {$pgno != $prev+1} {incr gap_cnt}
+    set prev $pgno
+  }
+
+  mem eval {
+    INSERT INTO space_used VALUES(
+      $name,
+      $tblname,
+      $is_index,
+      $nentry,
+      $leaf_entries,
+      $payload,     
+      $ovfl_payload,
+      $ovfl_cnt,   
+      $mx_payload,
+      $int_pages,
+      $leaf_pages,  
+      $ovfl_pages, 
+      $int_unused, 
+      $leaf_unused,
+      $ovfl_unused,
+      $gap_cnt
+    );
+  }
+}
+
+proc integerify {real} {
+  if {[string is double -strict $real]} {
+    return [expr {int($real)}]
+  } else {
+    return 0
+  }
+}
+mem function int integerify
+
+# Quote a string for use in an SQL query. Examples:
+#
+# [quote {hello world}]   == {'hello world'}
+# [quote {hello world's}] == {'hello world''s'}
+#
+proc quote {txt} {
+  regsub -all ' $txt '' q
+  return '$q'
+}
+
+# Generate a single line of output in the statistics section of the
+# report.
+#
+proc statline {title value {extra {}}} {
+  set len [string length $title]
+  set dots [string range {......................................} $len end]
+  set len [string length $value]
+  set sp2 [string range {          } $len end]
+  if {$extra ne ""} {
+    set extra " $extra"
+  }
+  puts "$title$dots $value$sp2$extra"
+}
+
+# Generate a formatted percentage value for $num/$denom
+#
+proc percent {num denom {of {}}} {
+  if {$denom==0.0} {return ""}
+  set v [expr {$num*100.0/$denom}]
+  set of {}
+  if {$v==100.0 || $v<0.001 || ($v>1.0 && $v<99.0)} {
+    return [format {%5.1f%% %s} $v $of]
+  } elseif {$v<0.1 || $v>99.9} {
+    return [format {%7.3f%% %s} $v $of]
+  } else {
+    return [format {%6.2f%% %s} $v $of]
+  }
+}
+
+proc divide {num denom} {
+  if {$denom==0} {return 0.0}
+  return [format %.2f [expr double($num)/double($denom)]]
+}
+
+# Generate a subreport that covers some subset of the database.
+# the $where clause determines which subset to analyze.
+#
+proc subreport {title where} {
+  global pageSize file_pgcnt
+
+  # Query the in-memory database for the sum of various statistics 
+  # for the subset of tables/indices identified by the WHERE clause in
+  # $where. Note that even if the WHERE clause matches no rows, the
+  # following query returns exactly one row (because it is an aggregate).
+  #
+  # The results of the query are stored directly by SQLite into local 
+  # variables (i.e. $nentry, $nleaf etc.).
+  #
+  mem eval "
+    SELECT
+      int(sum(nentry)) AS nentry,
+      int(sum(leaf_entries)) AS nleaf,
+      int(sum(payload)) AS payload,
+      int(sum(ovfl_payload)) AS ovfl_payload,
+      max(mx_payload) AS mx_payload,
+      int(sum(ovfl_cnt)) as ovfl_cnt,
+      int(sum(leaf_pages)) AS leaf_pages,
+      int(sum(int_pages)) AS int_pages,
+      int(sum(ovfl_pages)) AS ovfl_pages,
+      int(sum(leaf_unused)) AS leaf_unused,
+      int(sum(int_unused)) AS int_unused,
+      int(sum(ovfl_unused)) AS ovfl_unused,
+      int(sum(gap_cnt)) AS gap_cnt
+    FROM space_used WHERE $where" {} {}
+
+  # Output the sub-report title, nicely decorated with * characters.
+  #
+  puts ""
+  set len [string length $title]
+  set stars [string repeat * [expr 65-$len]]
+  puts "*** $title $stars"
+  puts ""
+
+  # Calculate statistics and store the results in TCL variables, as follows:
+  #
+  # total_pages: Database pages consumed.
+  # total_pages_percent: Pages consumed as a percentage of the file.
+  # storage: Bytes consumed.
+  # payload_percent: Payload bytes used as a percentage of $storage.
+  # total_unused: Unused bytes on pages.
+  # avg_payload: Average payload per btree entry.
+  # avg_fanout: Average fanout for internal pages.
+  # avg_unused: Average unused bytes per btree entry.
+  # ovfl_cnt_percent: Percentage of btree entries that use overflow pages.
+  #
+  set total_pages [expr {$leaf_pages+$int_pages+$ovfl_pages}]
+  set total_pages_percent [percent $total_pages $file_pgcnt]
+  set storage [expr {$total_pages*$pageSize}]
+  set payload_percent [percent $payload $storage {of storage consumed}]
+  set total_unused [expr {$ovfl_unused+$int_unused+$leaf_unused}]
+  set avg_payload [divide $payload $nleaf]
+  set avg_unused [divide $total_unused $nleaf]
+  if {$int_pages>0} {
+    # TODO: Is this formula correct?
+    set nTab [mem eval "
+      SELECT count(*) FROM (
+          SELECT DISTINCT tblname FROM space_used WHERE $where AND is_index=0
+      )
+    "]
+    set avg_fanout [mem eval "
+      SELECT (sum(leaf_pages+int_pages)-$nTab)/sum(int_pages) FROM space_used
+          WHERE $where AND is_index = 0
+    "]
+    set avg_fanout [format %.2f $avg_fanout]
+  }
+  set ovfl_cnt_percent [percent $ovfl_cnt $nleaf {of all entries}]
+
+  # Print out the sub-report statistics.
+  #
+  statline {Percentage of total database} $total_pages_percent
+  statline {Number of entries} $nleaf
+  statline {Bytes of storage consumed} $storage
+  statline {Bytes of payload} $payload $payload_percent
+  statline {Average payload per entry} $avg_payload
+  statline {Average unused bytes per entry} $avg_unused
+  if {[info exists avg_fanout]} {
+    statline {Average fanout} $avg_fanout
+  }
+  if {$total_pages>1} {
+    set fragmentation [percent $gap_cnt [expr {$total_pages-1}] {fragmentation}]
+    statline {Fragmentation} $fragmentation
+  }
+  statline {Maximum payload per entry} $mx_payload
+  statline {Entries that use overflow} $ovfl_cnt $ovfl_cnt_percent
+  if {$int_pages>0} {
+    statline {Index pages used} $int_pages
+  }
+  statline {Primary pages used} $leaf_pages
+  statline {Overflow pages used} $ovfl_pages
+  statline {Total pages used} $total_pages
+  if {$int_unused>0} {
+    set int_unused_percent \
+         [percent $int_unused [expr {$int_pages*$pageSize}] {of index space}]
+    statline "Unused bytes on index pages" $int_unused $int_unused_percent
+  }
+  statline "Unused bytes on primary pages" $leaf_unused \
+     [percent $leaf_unused [expr {$leaf_pages*$pageSize}] {of primary space}]
+  statline "Unused bytes on overflow pages" $ovfl_unused \
+     [percent $ovfl_unused [expr {$ovfl_pages*$pageSize}] {of overflow space}]
+  statline "Unused bytes on all pages" $total_unused \
+               [percent $total_unused $storage {of all space}]
+  return 1
+}
+
+# Calculate the overhead in pages caused by auto-vacuum. 
+#
+# This procedure calculates and returns the number of pages used by the 
+# auto-vacuum 'pointer-map'. If the database does not support auto-vacuum,
+# then 0 is returned. The two arguments are the size of the database file in
+# pages and the page size used by the database (in bytes).
+proc autovacuum_overhead {filePages pageSize} {
+
+  # Set $autovacuum to non-zero for databases that support auto-vacuum.
+  set autovacuum [db one {PRAGMA auto_vacuum}]
+
+  # If the database is not an auto-vacuum database or the file consists
+  # of one page only then there is no overhead for auto-vacuum. Return zero.
+  if {0==$autovacuum || $filePages==1} {
+    return 0
+  }
+
+  # The number of entries on each pointer map page. The layout of the
+  # database file is one pointer-map page, followed by $ptrsPerPage other
+  # pages, followed by a pointer-map page etc. The first pointer-map page
+  # is the second page of the file overall.
+  set ptrsPerPage [expr double($pageSize/5)]
+
+  # Return the number of pointer map pages in the database.
+  return [expr int(ceil( ($filePages-1.0)/($ptrsPerPage+1.0) ))]
+}
+
+
+# Calculate the summary statistics for the database and store the results
+# in TCL variables. They are output below. Variables are as follows:
+#
+# pageSize:      Size of each page in bytes.
+# file_bytes:    File size in bytes.
+# file_pgcnt:    Number of pages in the file.
+# file_pgcnt2:   Number of pages in the file (calculated).
+# av_pgcnt:      Pages consumed by the auto-vacuum pointer-map.
+# av_percent:    Percentage of the file consumed by auto-vacuum pointer-map.
+# inuse_pgcnt:   Data pages in the file.
+# inuse_percent: Percentage of pages used to store data.
+# free_pgcnt:    Free pages calculated as (<total pages> - <in-use pages>)
+# free_pgcnt2:   Free pages in the file according to the file header.
+# free_percent:  Percentage of file consumed by free pages (calculated).
+# free_percent2: Percentage of file consumed by free pages (header).
+# ntable:        Number of tables in the db.
+# nindex:        Number of indices in the db.
+# nautoindex:    Number of indices created automatically.
+# nmanindex:     Number of indices created manually.
+# user_payload:  Number of bytes of payload in table btrees 
+#                (not including sqlite_master)
+# user_percent:  $user_payload as a percentage of total file size.
+
+set file_bytes  [file size $file_to_analyze]
+set file_pgcnt  [expr {$file_bytes/$pageSize}]
+
+set av_pgcnt    [autovacuum_overhead $file_pgcnt $pageSize]
+set av_percent  [percent $av_pgcnt $file_pgcnt]
+
+set sql {SELECT sum(leaf_pages+int_pages+ovfl_pages) FROM space_used}
+set inuse_pgcnt   [expr int([mem eval $sql])]
+set inuse_percent [percent $inuse_pgcnt $file_pgcnt]
+
+set free_pgcnt    [expr $file_pgcnt-$inuse_pgcnt-$av_pgcnt]
+set free_percent  [percent $free_pgcnt $file_pgcnt]
+set free_pgcnt2   [db one {PRAGMA freelist_count}]
+set free_percent2 [percent $free_pgcnt2 $file_pgcnt]
+
+set file_pgcnt2 [expr {$inuse_pgcnt+$free_pgcnt2+$av_pgcnt}]
+
+set ntable [db eval {SELECT count(*)+1 FROM sqlite_master WHERE type='table'}]
+set nindex [db eval {SELECT count(*) FROM sqlite_master WHERE type='index'}]
+set sql {SELECT count(*) FROM sqlite_master WHERE name LIKE 'sqlite_autoindex%'}
+set nautoindex [db eval $sql]
+set nmanindex [expr {$nindex-$nautoindex}]
+
+# set total_payload [mem eval "SELECT sum(payload) FROM space_used"]
+set user_payload [mem one {SELECT int(sum(payload)) FROM space_used
+     WHERE NOT is_index AND name NOT LIKE 'sqlite_master'}]
+set user_percent [percent $user_payload $file_bytes]
+
+# Output the summary statistics calculated above.
+#
+puts "/** Disk-Space Utilization Report For $file_to_analyze"
+catch {
+  puts "*** As of [clock format [clock seconds] -format {%Y-%b-%d %H:%M:%S}]"
+}
+puts ""
+statline {Page size in bytes} $pageSize
+statline {Pages in the whole file (measured)} $file_pgcnt
+statline {Pages in the whole file (calculated)} $file_pgcnt2
+statline {Pages that store data} $inuse_pgcnt $inuse_percent
+statline {Pages on the freelist (per header)} $free_pgcnt2 $free_percent2
+statline {Pages on the freelist (calculated)} $free_pgcnt $free_percent
+statline {Pages of auto-vacuum overhead} $av_pgcnt $av_percent
+statline {Number of tables in the database} $ntable
+statline {Number of indices} $nindex
+statline {Number of named indices} $nmanindex
+statline {Automatically generated indices} $nautoindex
+statline {Size of the file in bytes} $file_bytes
+statline {Bytes of user payload stored} $user_payload $user_percent
+
+# Output table rankings
+#
+puts ""
+puts "*** Page counts for all tables with their indices ********************"
+puts ""
+mem eval {SELECT tblname, count(*) AS cnt, 
+              int(sum(int_pages+leaf_pages+ovfl_pages)) AS size
+          FROM space_used GROUP BY tblname ORDER BY size+0 DESC, tblname} {} {
+  statline [string toupper $tblname] $size [percent $size $file_pgcnt]
+}
+
+# Output subreports
+#
+if {$nindex>0} {
+  subreport {All tables and indices} 1
+}
+subreport {All tables} {NOT is_index}
+if {$nindex>0} {
+  subreport {All indices} {is_index}
+}
+foreach tbl [mem eval {SELECT name FROM space_used WHERE NOT is_index
+                       ORDER BY name}] {
+  regsub ' $tbl '' qn
+  set name [string toupper $tbl]
+  set n [mem eval "SELECT count(*) FROM space_used WHERE tblname='$qn'"]
+  if {$n>1} {
+    subreport "Table $name and all its indices" "tblname='$qn'"
+    subreport "Table $name w/o any indices" "name='$qn'"
+    subreport "Indices of table $name" "tblname='$qn' AND is_index"
+  } else {
+    subreport "Table $name" "name='$qn'"
+  }
+}
+
+# Output instructions on what the numbers above mean.
+#
+puts {
+*** Definitions ******************************************************
+
+Page size in bytes
+
+    The number of bytes in a single page of the database file.  
+    Usually 1024.
+
+Number of pages in the whole file
+}
+puts \
+"    The number of $pageSize-byte pages that go into forming the complete
+    database"
+puts \
+{
+Pages that store data
+
+    The number of pages that store data, either as primary B*Tree pages or
+    as overflow pages.  The number at the right is the data pages divided by
+    the total number of pages in the file.
+
+Pages on the freelist
+
+    The number of pages that are not currently in use but are reserved for
+    future use.  The percentage at the right is the number of freelist pages
+    divided by the total number of pages in the file.
+
+Pages of auto-vacuum overhead
+
+    The number of pages that store data used by the database to facilitate
+    auto-vacuum. This is zero for databases that do not support auto-vacuum.
+
+Number of tables in the database
+
+    The number of tables in the database, including the SQLITE_MASTER table
+    used to store schema information.
+
+Number of indices
+
+    The total number of indices in the database.
+
+Number of named indices
+
+    The number of indices created using an explicit CREATE INDEX statement.
+
+Automatically generated indices
+
+    The number of indices used to implement PRIMARY KEY or UNIQUE constraints
+    on tables.
+
+Size of the file in bytes
+
+    The total amount of disk space used by the entire database files.
+
+Bytes of user payload stored
+
+    The total number of bytes of user payload stored in the database. The
+    schema information in the SQLITE_MASTER table is not counted when
+    computing this number.  The percentage at the right shows the payload
+    divided by the total file size.
+
+Percentage of total database
+
+    The amount of the complete database file that is devoted to storing
+    information described by this category.
+
+Number of entries
+
+    The total number of B-Tree key/value pairs stored under this category.
+
+Bytes of storage consumed
+
+    The total amount of disk space required to store all B-Tree entries
+    under this category.  The is the total number of pages used times
+    the pages size.
+
+Bytes of payload
+
+    The amount of payload stored under this category.  Payload is the data
+    part of table entries and the key part of index entries.  The percentage
+    at the right is the bytes of payload divided by the bytes of storage 
+    consumed.
+
+Average payload per entry
+
+    The average amount of payload on each entry.  This is just the bytes of
+    payload divided by the number of entries.
+
+Average unused bytes per entry
+
+    The average amount of free space remaining on all pages under this
+    category on a per-entry basis.  This is the number of unused bytes on
+    all pages divided by the number of entries.
+
+Fragmentation
+
+    The percentage of pages in the table or index that are not
+    consecutive in the disk file.  Many filesystems are optimized
+    for sequential file access so smaller fragmentation numbers 
+    sometimes result in faster queries, especially for larger
+    database files that do not fit in the disk cache.
+
+Maximum payload per entry
+
+    The largest payload size of any entry.
+
+Entries that use overflow
+
+    The number of entries that user one or more overflow pages.
+
+Total pages used
+
+    This is the number of pages used to hold all information in the current
+    category.  This is the sum of index, primary, and overflow pages.
+
+Index pages used
+
+    This is the number of pages in a table B-tree that hold only key (rowid)
+    information and no data.
+
+Primary pages used
+
+    This is the number of B-tree pages that hold both key and data.
+
+Overflow pages used
+
+    The total number of overflow pages used for this category.
+
+Unused bytes on index pages
+
+    The total number of bytes of unused space on all index pages.  The
+    percentage at the right is the number of unused bytes divided by the
+    total number of bytes on index pages.
+
+Unused bytes on primary pages
+
+    The total number of bytes of unused space on all primary pages.  The
+    percentage at the right is the number of unused bytes divided by the
+    total number of bytes on primary pages.
+
+Unused bytes on overflow pages
+
+    The total number of bytes of unused space on all overflow pages.  The
+    percentage at the right is the number of unused bytes divided by the
+    total number of bytes on overflow pages.
+
+Unused bytes on all pages
+
+    The total number of bytes of unused space on all primary and overflow 
+    pages.  The percentage at the right is the number of unused bytes 
+    divided by the total number of bytes.
+}
+
+# Output a dump of the in-memory database. This can be used for more
+# complex offline analysis.
+#
+puts "**********************************************************************"
+puts "The entire text of this report can be sourced into any SQL database"
+puts "engine for further analysis.  All of the text above is an SQL comment."
+puts "The data used to generate this report follows:"
+puts "*/"
+puts "BEGIN;"
+puts $tabledef
+unset -nocomplain x
+mem eval {SELECT * FROM space_used} x {
+  puts -nonewline "INSERT INTO space_used VALUES"
+  set sep (
+  foreach col $x(*) {
+    set v $x($col)
+    if {$v=="" || ![string is double $v]} {set v [quote $v]}
+    puts -nonewline $sep$v
+    set sep ,
+  }
+  puts ");"
+}
+puts "COMMIT;"
+
+} err]} {
+  puts "ERROR: $err"
+  puts $errorInfo
+  exit 1
+}