/ Check-in [63f2ee22]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Refactor the space-analysis script for readability. (CVS 2081)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 63f2ee22e20ed7e520fd9230acc5c6db43b69d13
User & Date: danielk1977 2004-11-09 07:42:11
Context
2004-11-09
12:44
Port the "DEFAULT CURRENT_TIME" etc. functionality from an earlier fork of sqlite. (CVS 2082) check-in: 0d27c8ff user: danielk1977 tags: trunk
07:42
Refactor the space-analysis script for readability. (CVS 2081) check-in: 63f2ee22 user: danielk1977 tags: trunk
2004-11-08
16:15
Update the space-analyzer tool to support auto-vacuum databases. (CVS 2080) check-in: 1cb80866 user: danielk1977 tags: trunk
Changes
Hide Diffs Unified Diffs Show Whitespace Changes Patch

Changes to tool/spaceanal.tcl.

25
26
27
28
29
30
31
32



33
34
35
36
37
38
39
..
48
49
50
51
52
53
54
55
56
57

58
59
60
61
62
63
64
65
66
67
68
69
70
71
72








73

74




























75












76
77
78
79
80





81
82
83
84
85
86
87
88
89
90
91
92
93











94




95
96





97
98
99




100
101
102
103
104
105
106
107
108






109
110
111
112






113
114
115
116
117



118



119
120
121
122
123
124
125
126
127









128
129

130
131
132

133
134




135
136
137
138
139
140
141
...
148
149
150
151
152
153
154
155


156
157
158
159
160
161
162
163
164
165
166
167
168



169
170
171

172
173
174
175
176
177
178
179
180
181











182




183





184
185
186
187




188
189
190
191
192
193
194
195
196




197
198
199
200
201
202
203
204





205
206
207
208



209
210
211
212
213
214
215
...
255
256
257
258
259
260
261
262
263









264
265
266
267
268
269
270
...
271
272
273
274
275
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
...
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
...
348
349
350
351
352
353
354
355
356

357
358
359
360
361
362
363
364
365
366
367
368
...
372
373
374
375
376
377
378
379


380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
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
...
597
598
599
600
601
602
603
604

605
606
607
608
609
610
611
}

# Open the database
#
sqlite3 db [lindex $argv 0]
set DB [btree_open [lindex $argv 0] 1000 0]

# In-memory database for collecting statistics



#
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
................................................................................
   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
);}
mem eval $tabledef

# This query will be used to find the root page number for every table
# in the database.
#

set sql {
  SELECT name, rootpage 
    FROM sqlite_master WHERE type='table'
  UNION ALL
  SELECT 'sqlite_master', 1
  ORDER BY 1
}

# Quote a string for SQL
#
proc quote txt {
  regsub -all ' $txt '' q
  return '$q'
}









# Analyze every table in the database, one at a time.

#




























set pageSize [db eval {PRAGMA page_size}]












foreach {name rootpage} [db eval $sql] {
  puts stderr "Analyzing table $name..."
  set cursor [btree_cursor $DB $rootpage 0]
  set go [btree_first $cursor]
  catch {unset seen}





  set total_payload 0        ;# Payload space used by all entries
  set total_ovfl 0           ;# Payload space on overflow pages
  set unused_int 0           ;# Unused space on interior nodes
  set unused_leaf 0          ;# Unused space on leaf nodes
  set unused_ovfl 0          ;# Unused space on overflow pages
  set cnt_ovfl 0             ;# Number of entries that use overflows
  set cnt_leaf_entry 0       ;# Number of leaf entries
  set cnt_int_entry 0        ;# Number of interor entries
  set mx_payload 0           ;# Maximum payload size
  set ovfl_pages 0           ;# Number of overflow pages used
  set leaf_pages 0           ;# Number of leaf pages
  set int_pages 0            ;# Number of interior pages
  while {$go==0} {











    incr cnt_leaf_entry




    set stat [btree_cursor_info $cursor]
    set payload [lindex $stat 6]





    if {$payload>$mx_payload} {set mx_payload $payload}
    incr total_payload $payload
    set local [lindex $stat 8]    




    set ovfl [expr {$payload-$local}]
    if {$ovfl} {
      incr cnt_ovfl
      incr total_ovfl $ovfl
      set n [expr {int(ceil($ovfl/($pageSize-4.0)))}]
      incr ovfl_pages $n
      incr unused_ovfl [expr {$n*($pageSize-4) - $ovfl}]
    }
    set pgno [lindex $stat 0]






    if {![info exists seen($pgno)]} {
      set seen($pgno) 1
      incr leaf_pages
      incr unused_leaf [lindex $stat 4]






      set parent [lindex $stat 9]
      set up 0
      while {$parent!=0 && ![info exists seen($parent)]} {
        incr up
        set stat [btree_cursor_info $cursor $up]



        set seen($parent) 1



        incr int_pages
        incr cnt_int_entry [lindex $stat 2]
        incr unused_int [lindex $stat 4]
        set parent [lindex $stat 9]
      }
    }
    set go [btree_next $cursor]
  }
  btree_close_cursor $cursor









  if {[llength [array names seen]]==0} {
    set leaf_pages 1

    set unused_leaf [expr {$pageSize-8}]
  } elseif {$rootpage==1 && ![info exists seen(1)]} {
    incr int_pages

    incr unused_int [expr {$pageSize-112}]
  }




  set sql "INSERT INTO space_used VALUES("
  append sql [quote $name]
  append sql ",[quote $name]"
  append sql ",0"
  append sql ",[expr {$cnt_leaf_entry+$cnt_int_entry}]"
  append sql ",$cnt_leaf_entry"
  append sql ",$total_payload"
................................................................................
  append sql ",$unused_int"
  append sql ",$unused_leaf"
  append sql ",$unused_ovfl"
  append sql );
  mem eval $sql
}

# This query will be used to find the root page number for every index


# in the database.
#
set sql {
  SELECT name, tbl_name, rootpage 
    FROM sqlite_master WHERE type='index'
  ORDER BY 2, 1
}

# Analyze every index in the database, one at a time.
#
set pageSize [db eval {PRAGMA page_size}]
foreach {name tbl_name rootpage} [db eval $sql] {
  puts stderr "Analyzing index $name of table $tbl_name..."



  set cursor [btree_cursor $DB $rootpage 0]
  set go [btree_first $cursor]
  catch {unset seen}

  set total_payload 0        ;# Payload space used by all entries
  set total_ovfl 0           ;# Payload space on overflow pages
  set unused_leaf 0          ;# Unused space on leaf nodes
  set unused_ovfl 0          ;# Unused space on overflow pages
  set cnt_ovfl 0             ;# Number of entries that use overflows
  set cnt_leaf_entry 0       ;# Number of leaf entries
  set mx_payload 0           ;# Maximum payload size
  set ovfl_pages 0           ;# Number of overflow pages used
  set leaf_pages 0           ;# Number of leaf pages
  while {$go==0} {











    incr cnt_leaf_entry




    set stat [btree_cursor_info $cursor]





    set payload [btree_keysize $cursor]
    if {$payload>$mx_payload} {set mx_payload $payload}
    incr total_payload $payload
    set local [lindex $stat 8]    




    set ovfl [expr {$payload-$local}]
    if {$ovfl} {
      incr cnt_ovfl
      incr total_ovfl $ovfl
      set n [expr {int(ceil($ovfl/($pageSize-4.0)))}]
      incr ovfl_pages $n
      incr unused_ovfl [expr {$n*($pageSize-4) - $ovfl}]
    }
    set pgno [lindex $stat 0]




    if {![info exists seen($pgno)]} {
      set seen($pgno) 1
      incr leaf_pages
      incr unused_leaf [lindex $stat 4]
    }
    set go [btree_next $cursor]
  }
  btree_close_cursor $cursor





  if {[llength [array names seen]]==0} {
    set leaf_pages 1
    set unused_leaf [expr {$pageSize-8}]
  }



  set sql "INSERT INTO space_used VALUES("
  append sql [quote $name]
  append sql ",[quote $tbl_name]"
  append sql ",1"
  append sql ",$cnt_leaf_entry"
  append sql ",$cnt_leaf_entry"
  append sql ",$total_payload"
................................................................................
  }
}

# Generate a subreport that covers some subset of the database.
# the $where clause determines which subset to analyze.
#
proc subreport {title where} {
  global pageSize
  set hit 0









  mem eval "
    SELECT
      sum(nentry) AS nentry,
      sum(leaf_entries) AS nleaf,
      sum(payload) AS payload,
      sum(ovfl_payload) AS ovfl_payload,
      max(mx_payload) AS mx_payload,
................................................................................
      sum(ovfl_cnt) as ovfl_cnt,
      sum(leaf_pages) AS leaf_pages,
      sum(int_pages) AS int_pages,
      sum(ovfl_pages) AS ovfl_pages,
      sum(leaf_unused) AS leaf_unused,
      sum(int_unused) AS int_unused,
      sum(ovfl_unused) AS ovfl_unused
    FROM space_used WHERE $where" {} {set hit 1}
  if {!$hit} {return 0}



  puts ""
  set len [string length $title]
  incr len 5
  set stars "***********************************"
  append stars $stars
  set stars [string range $stars $len end]
  puts "*** $title $stars"
  puts ""













  set total_pages [expr {$leaf_pages+$int_pages+$ovfl_pages}]
  statline "Percentage of total database" [percent $total_pages $::file_pgcnt]
  statline "Number of entries" $nleaf
  set total_unused [expr {$ovfl_unused+$int_unused+$leaf_unused}]

  set storage [expr {$total_pages*$pageSize}]
  statline "Bytes of storage consumed" $storage
  statline "Bytes of payload" $payload \
       [percent $payload $storage {of storage consumed}]

  statline "Average payload per entry" [expr {$nleaf>0?$payload/$nleaf:0}]
  set avgunused [expr {$nleaf>0?$total_unused/$nleaf:0}]
  statline "Average unused bytes per entry" $avgunused
  set nint [expr {$nentry-$nleaf}]
  if {$int_pages>0} {
    statline "Average fanout" [format %.2f [expr {($nint+0.0)/$int_pages}]]


  }













  statline "Maximum payload per entry" $mx_payload
  statline "Entries that use overflow" $ovfl_cnt \
        [percent $ovfl_cnt $nleaf {of all entries}]
  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} {
    statline "Unused bytes on index pages" $int_unused \

         [percent $int_unused [expr {$int_pages*$pageSize}] {of index space}]

  }
  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}]
................................................................................
}

# 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
# bytes and the page size used by the database (also in bytes).
proc autovacuum_overhead {filePages pageSize} {

  # Read the value of meta 4. If non-zero, then the database supports
  # auto-vacuum. It would be possible to use "PRAGMA auto_vacuum" instead,
  # but that would not work if the SQLITE_OMIT_PRAGMA macro was defined
  # when the library was built.
  set meta4 [lindex [btree_get_meta $::DB] 4]
................................................................................
  # 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) ))]
}

# Output summary statistics:
#

puts "/** Disk-Space Utilization Report For $file_to_analyze"
puts "*** As of [clock format [clock seconds] -format {%Y-%b-%d %H:%M:%S}]"
puts ""

# Variables:
#
# 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.
................................................................................
# 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:



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 q {SELECT sum(leaf_pages+int_pages+ovfl_pages) FROM space_used}
set inuse_pgcnt   [expr [mem eval $q]]
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   [lindex [btree_get_meta $DB] 0]
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 q {SELECT count(*) FROM sqlite_master WHERE name LIKE 'sqlite_autoindex%'}
set nautoindex [db eval $q]
set nmanindex [expr {$nindex-$nautoindex}]

# set total_payload [mem eval "SELECT sum(payload) FROM space_used"]
set user_payload [mem one {SELECT sum(payload) FROM space_used
     WHERE NOT is_index AND name NOT LIKE 'sqlite_master'}]
set user_payload_percent [percent $user_payload $file_bytes]






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_payload_percent

# Output table rankings
#
puts ""
puts "*** Page counts for all tables with their indices ********************"
puts ""
mem eval {SELECT tblname, count(*) AS cnt, 
................................................................................
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 the database

#
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;"







|
>
>
>







 







|
<

>
|
<
<
<
<
<
<
|
<
<
|




>
>
>
>
>
>
>
>
|
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>


<
<
<
>
>
>
>
>












<
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
|
<
>
>
>
>
>
|
|
<
>
>
>
>
|







<
>
>
>
>
>
>
|
|

|
>
>
>
>
>
>
|
|
|
<
<
>
>
>
|
>
>
>

|
|
<


<

|
>
>
>
>
>
>
>
>
>


>
|
<
<
>
|
|
>
>
>
>







 







|
>
>
|


<
|


<
<
<
<


>
>
>
|
<
<
>









<
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
|
>
>
>
>
>
|


<
>
>
>
>
|







<
>
>
>
>
|
|

|

<

|
>
>
>
>
>




>
>
>







 







|
<
>
>
>
>
>
>
>
>
>







 







|
<
>
>
>


<
<
<
|


>
>
>
>
>
>
>
>
>
>
>
>
>

<
<
<
>

<
<
|
>
|
|
<
<

<
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
<

|

|
|
|

<
>

>







 







|







 







<
|
>
|
<
<
<
<







 







|
>
>







|
|











|
|





|

>
>
>
>
>












|







 







|
>







25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
..
51
52
53
54
55
56
57
58

59
60
61






62


63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121



122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138

139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155

156
157
158
159
160
161
162

163
164
165
166
167
168
169
170
171
172
173
174

175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193


194
195
196
197
198
199
200
201
202
203

204
205

206
207
208
209
210
211
212
213
214
215
216
217
218
219
220


221
222
223
224
225
226
227
228
229
230
231
232
233
234
...
241
242
243
244
245
246
247
248
249
250
251
252
253

254
255
256




257
258
259
260
261
262


263
264
265
266
267
268
269
270
271
272

273
274
275
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
326
327
328
329
330
331
332
333
334
335
336
337
338
339
...
379
380
381
382
383
384
385
386

387
388
389
390
391
392
393
394
395
396
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



433
434


435
436
437
438


439

440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457

458
459
460
461
462
463
464

465
466
467
468
469
470
471
472
473
474
...
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
...
501
502
503
504
505
506
507

508
509
510




511
512
513
514
515
516
517
...
521
522
523
524
525
526
527
528
529
530
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
...
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
}

# Open the database
#
sqlite3 db [lindex $argv 0]
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
................................................................................
   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
);}
mem eval $tabledef

# 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'
}

# This proc is a wrapper around the btree_cursor_info command. The
# second argument is an open btree cursor returned by [btree_cursor].
# The first argument is the name of an array variable that exists in
# the scope of the caller. If the third argument is non-zero, then
# info is returned for the page that lies $up entries upwards in the
# tree-structure. (i.e. $up==1 returns the parent page, $up==2 the 
# grandparent etc.)
#
# The following entries in that array are filled in with information retrieved
# using [btree_cursor_info]:
#
#   $arrayvar(page_no)             =  The page number
#   $arrayvar(entry_no)            =  The entry number
#   $arrayvar(page_entries)        =  Total number of entries on this page
#   $arrayvar(cell_size)           =  Cell size (local payload + header)
#   $arrayvar(page_freebytes)      =  Number of free bytes on this page
#   $arrayvar(page_freeblocks)     =  Number of free blocks on the page
#   $arrayvar(payload_bytes)       =  Total payload size (local + overflow)
#   $arrayvar(header_bytes)        =  Header size in bytes
#   $arrayvar(local_payload_bytes) =  Local payload size
#   $arrayvar(parent)              =  Parent page number
# 
proc cursor_info {arrayvar csr {up 0}} {
  upvar $arrayvar a
  foreach [list a(page_no) \
                a(entry_no) \
                a(page_entries) \
                a(cell_size) \
                a(page_freebytes) \
                a(page_freeblocks) \
                a(payload_bytes) \
                a(header_bytes) \
                a(local_payload_bytes) \
                a(parent) ] [btree_cursor_info $csr $up] {}
}

# Determine the page-size of the database. This global variable is used
# throughout the script.
#
set pageSize [db eval {PRAGMA page_size}]

# Analyze every table in the database, one at a time.
#
# The following query returns the name and root-page of each table in the
# database, including the sqlite_master table.
#
set sql {
  SELECT name, rootpage FROM sqlite_master WHERE type='table'
  UNION ALL
  SELECT 'sqlite_master', 1
  ORDER BY 1
}
foreach {name rootpage} [db eval $sql] {
  puts stderr "Analyzing table $name..."




  # Code below traverses the table being analyzed (table name $name), using the
  # btree cursor $cursor. Statistics related to table $name are accumulated in
  # the following variables:
  #
  set total_payload 0        ;# Payload space used by all entries
  set total_ovfl 0           ;# Payload space on overflow pages
  set unused_int 0           ;# Unused space on interior nodes
  set unused_leaf 0          ;# Unused space on leaf nodes
  set unused_ovfl 0          ;# Unused space on overflow pages
  set cnt_ovfl 0             ;# Number of entries that use overflows
  set cnt_leaf_entry 0       ;# Number of leaf entries
  set cnt_int_entry 0        ;# Number of interor entries
  set mx_payload 0           ;# Maximum payload size
  set ovfl_pages 0           ;# Number of overflow pages used
  set leaf_pages 0           ;# Number of leaf pages
  set int_pages 0            ;# Number of interior pages


  # As the btree is traversed, the array variable $seen($pgno) is set to 1
  # the first time page $pgno is encountered.
  #
  catch {unset seen}

  # The following loop runs once for each entry in table $name. The table
  # is traversed using the btree cursor stored in variable $csr
  #
  set csr [btree_cursor $DB $rootpage 0]
  for {btree_first $csr} {![btree_eof $csr]} {btree_next $csr} {
    incr cnt_leaf_entry

    # Retrieve information about the entry the btree-cursor points to into
    # the array variable $ci (cursor info).
    #
    cursor_info ci $csr


    # Check if the payload of this entry is greater than the current 
    # $mx_payload statistic for the table. Also increase the $total_payload
    # statistic.
    #
    if {$ci(payload_bytes)>$mx_payload} {set mx_payload $ci(payload_bytes)}
    incr total_payload $ci(payload_bytes)


    # If this entry uses overflow pages, then update the $cnt_ovfl, 
    # $total_ovfl, $ovfl_pages and $unused_ovfl statistics.
    #
    set ovfl [expr {$ci(payload_bytes)-$ci(local_payload_bytes)}]
    if {$ovfl} {
      incr cnt_ovfl
      incr total_ovfl $ovfl
      set n [expr {int(ceil($ovfl/($pageSize-4.0)))}]
      incr ovfl_pages $n
      incr unused_ovfl [expr {$n*($pageSize-4) - $ovfl}]
    }


    # If this is the first table entry analyzed for the page, then update
    # the page-related statistics $leaf_pages and $unused_leaf. Also, if
    # this page has a parent page that has not been analyzed, retrieve
    # info for the parent and update statistics for it too.
    #
    if {![info exists seen($ci(page_no))]} {
      set seen($ci(page_no)) 1
      incr leaf_pages
      incr unused_leaf $ci(page_freebytes)

      # Now check if the page has a parent that has not been analyzed. If
      # so, update the $int_pages, $cnt_int_entry and $unused_int statistics
      # accordingly. Then check if the parent page has a parent that has
      # not yet been analyzed etc.
      #
      # set parent $ci(parent_page_no)
      for {set up 1} \
          {$ci(parent)!=0 && ![info exists seen($ci(parent))]} {incr up} \


      {
        # Mark the parent as seen.
        #
        set seen($ci(parent)) 1

        # Retrieve info for the parent and update statistics.
        cursor_info ci $csr $up
        incr int_pages
        incr cnt_int_entry $ci(page_entries)
        incr unused_int $ci(page_freebytes)

      }
    }

  }
  btree_close_cursor $csr

  # Handle the special case where a table contains no data. In this case
  # all statistics are zero, except for the number of leaf pages (1) and
  # the unused bytes on leaf pages ($pageSize - 8).
  #
  # An exception to the above is the sqlite_master table. If it is empty
  # then all statistics are zero except for the number of leaf pages (1),
  # and the number of unused bytes on leaf pages ($pageSize - 112).
  #
  if {[llength [array names seen]]==0} {
    set leaf_pages 1
    if {$rootpage==1} {
      set unused_leaf [expr {$pageSize-112}]


    } else {
      set unused_leaf [expr {$pageSize-8}]
    }
  }

  # Insert the statistics for the table analyzed into the in-memory database.
  #
  set sql "INSERT INTO space_used VALUES("
  append sql [quote $name]
  append sql ",[quote $name]"
  append sql ",0"
  append sql ",[expr {$cnt_leaf_entry+$cnt_int_entry}]"
  append sql ",$cnt_leaf_entry"
  append sql ",$total_payload"
................................................................................
  append sql ",$unused_int"
  append sql ",$unused_leaf"
  append sql ",$unused_ovfl"
  append sql );
  mem eval $sql
}

# Analyze every index in the database, one at a time.
#
# The query below returns the name, associated table and root-page number 
# for every index in the database.
#
set sql {

  SELECT name, tbl_name, rootpage FROM sqlite_master WHERE type='index'
  ORDER BY 2, 1
}




foreach {name tbl_name rootpage} [db eval $sql] {
  puts stderr "Analyzing index $name of table $tbl_name..."

  # Code below traverses the index being analyzed (index name $name), using the
  # btree cursor $cursor. Statistics related to index $name are accumulated in
  # the following variables:


  #
  set total_payload 0        ;# Payload space used by all entries
  set total_ovfl 0           ;# Payload space on overflow pages
  set unused_leaf 0          ;# Unused space on leaf nodes
  set unused_ovfl 0          ;# Unused space on overflow pages
  set cnt_ovfl 0             ;# Number of entries that use overflows
  set cnt_leaf_entry 0       ;# Number of leaf entries
  set mx_payload 0           ;# Maximum payload size
  set ovfl_pages 0           ;# Number of overflow pages used
  set leaf_pages 0           ;# Number of leaf pages


  # As the btree is traversed, the array variable $seen($pgno) is set to 1
  # the first time page $pgno is encountered.
  #
  catch {unset seen}

  # The following loop runs once for each entry in index $name. The index
  # is traversed using the btree cursor stored in variable $csr
  #
  set csr [btree_cursor $DB $rootpage 0]
  for {btree_first $csr} {![btree_eof $csr]} {btree_next $csr} {
    incr cnt_leaf_entry

    # Retrieve information about the entry the btree-cursor points to into
    # the array variable $ci (cursor info).
    #
    cursor_info ci $csr

    # Check if the payload of this entry is greater than the current 
    # $mx_payload statistic for the table. Also increase the $total_payload
    # statistic.
    #
    set payload [btree_keysize $csr]
    if {$payload>$mx_payload} {set mx_payload $payload}
    incr total_payload $payload


    # If this entry uses overflow pages, then update the $cnt_ovfl, 
    # $total_ovfl, $ovfl_pages and $unused_ovfl statistics.
    #
    set ovfl [expr {$payload-$ci(local_payload_bytes)}]
    if {$ovfl} {
      incr cnt_ovfl
      incr total_ovfl $ovfl
      set n [expr {int(ceil($ovfl/($pageSize-4.0)))}]
      incr ovfl_pages $n
      incr unused_ovfl [expr {$n*($pageSize-4) - $ovfl}]
    }


    # If this is the first table entry analyzed for the page, then update
    # the page-related statistics $leaf_pages and $unused_leaf.
    #
    if {![info exists seen($ci(page_no))]} {
      set seen($ci(page_no)) 1
      incr leaf_pages
      incr unused_leaf $ci(page_freebytes)
    }

  }
  btree_close_cursor $csr

  # Handle the special case where a index contains no data. In this case
  # all statistics are zero, except for the number of leaf pages (1) and
  # the unused bytes on leaf pages ($pageSize - 8).
  #
  if {[llength [array names seen]]==0} {
    set leaf_pages 1
    set unused_leaf [expr {$pageSize-8}]
  }

  # Insert the statistics for the index analyzed into the in-memory database.
  #
  set sql "INSERT INTO space_used VALUES("
  append sql [quote $name]
  append sql ",[quote $tbl_name]"
  append sql ",1"
  append sql ",$cnt_leaf_entry"
  append sql ",$cnt_leaf_entry"
  append sql ",$total_payload"
................................................................................
  }
}

# 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
      sum(nentry) AS nentry,
      sum(leaf_entries) AS nleaf,
      sum(payload) AS payload,
      sum(ovfl_payload) AS ovfl_payload,
      max(mx_payload) AS mx_payload,
................................................................................
      sum(ovfl_cnt) as ovfl_cnt,
      sum(leaf_pages) AS leaf_pages,
      sum(int_pages) AS int_pages,
      sum(ovfl_pages) AS ovfl_pages,
      sum(leaf_unused) AS leaf_unused,
      sum(int_unused) AS int_unused,
      sum(ovfl_unused) AS ovfl_unused
    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 [expr {$nleaf>0?$payload/$nleaf:0}]
  set avg_unused [expr {$nleaf>0?$total_unused/$nleaf:0}]


  if {$int_pages>0} {

    # TODO: Is this formula correct?
    set avg_fanout [format %.2f [expr double($nentry-$nleaf)/$int_pages]]
  }
  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
  }
  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}]
................................................................................
}

# 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} {

  # Read the value of meta 4. If non-zero, then the database supports
  # auto-vacuum. It would be possible to use "PRAGMA auto_vacuum" instead,
  # but that would not work if the SQLITE_OMIT_PRAGMA macro was defined
  # when the library was built.
  set meta4 [lindex [btree_get_meta $::DB] 4]
................................................................................
  # 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.
................................................................................
# 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 [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   [lindex [btree_get_meta $DB] 0]
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 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"
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, 
................................................................................
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;"