util/db_tuner.c

   1 /*
   2  * See the file LICENSE for redistribution information.
   3  *
   4  * Copyright (c) 2011, 2012 Oracle and/or its affiliates.  All rights reserved.
   5  *
   6  * $Id$
   7  *
   8  * This utility choses a reasonable pagesize for a BTREE database.
   9  *
  10  * Here we assume that:
  11  * 1) This set of records are already in a BTREE database, which may been
  12  *    configured with a unreasonable page size.
  13  * 2) Treat the database as if it were compacted.
  14  * 3) The goal is to optimize the database for the current content,
  15  *    rather than for ongoing insertions.
  16  *
  17  * The page size of a BTREE can be 512, 1024, 2048, 4096, 8192, 16384,
  18  * 32768, 65536, totally 8 different cases. So we have 8 possible BTREE,
  19  * each with different pagesize to contain them. Without actually creating
  20  * those 8 databases, this utility tries to simulate situations, that is,
  21  * for each pagesize, how many leaf pages, over flow pages and duplicate
  22  * pages are needed, and what's the distribution of each kind of pages
  23  * based on their fill factor.
  24  *
  25  * db_tuner contains 2 parts:
  26  *
  27  * I) Simulation of 8 different pagesized databases.
  28  * This includes, the number of leaf pages, overflow pages caused by
  29  * big key/data in leaf layers, and duplicate pages, the distribution
  30  * of each kind of pages in different fill factor ranges.
  31  *
  32  * This is achieved by retrieving those records from existing btree and
  33  * inserting them into different kind of pages. Since the records from
  34  * the btree are sorted, they are inserted into the end of each page.
  35  * If this page become full, that is no enough space, only this new
  36  * record will be put into next new page.
  37  *
  38  * II) Recommend the best page size.
  39  * From our simulation results, this utility choose a page size based on
  40  * the number of overflow pages and storage (on-disk space).
  41  * If there is no overflow pages, then choose the one resulting in
  42  * the smallest storage as the recommended page size. Otherwise,
  43  * choose the one that results in a reasonable small number of overflow pages.
  44  */
  45
  46 #include "db_config.h"
  47
  48 #include <assert.h>
  49 #include <math.h>
  50
  51 #include "db_int.h"
  52 #include "dbinc/db_page.h"
  53 #include "dbinc/btree.h"
  54
  55 #ifndef lint
  56 static const char copyright[] =
  57     "Copyright (c) 2011, 2012 Oracle and/or its affiliates.  All rights reserved.\n";
  58 #endif
  59
  60 /*
  61  * Fill factor distribution division,
  62  * e.g., [0.000 - 0.099], ..., [0.900 - 0.999], [1.000- 1.000]
  63  */
  64 #define DIST_DIVISION                   11
  65
  66 /* Error return code in db_tuner, different with those in src\dbinc\db.in. */
  67 /* Dist >= DIST_DIVISION. */
  68 #define EXIT_DIST_OUTRANGE              (-31000)
  69 /* "Insert" zero needed. */
  70 #define EXIT_INSERT_ZERO_NEED           (-31001)
  71 /* On-page duplicate set = 0. */
  72 #define EXIT_INSERT_ZERO_ONPGDUP        (-31002)
  73
  74 /* Follows are some special "insert" types based on the data. */
  75 /* Insert as normal case. */
  76 #define INSERT_NORMAL                   0x0001
  77 /* Nothing is inserted. */
  78 #define INSERT_NOTHING                  0x0002
  79 /* No key but a slot is inserted. */
  80 #define INSERT_SLOT                     0x0003
  81 /* A B_DUPLICATE point is inserted. */
  82 #define INSERT_BDUPLICATE               0x0004
  83
  84 /*
  85  * Page size of BTREE can be from DB_MIN_PGSIZE (512) to DB_MAX_PGSIZE(64K),
  86  * and all the pagesize is the power of 2, so we have 8 possible cases.
  87  *
  88  * 8 is from ((int)(log(DB_MAX_PGSIZE) - log(DB_MIN_PGSIZE) + 1)).
  89  */
  90 #define NUM_PGSIZES                     8
  91
  92 /* Structure used to store statistics of the assessment. */
  93 typedef struct __tuner_ff_stat {
  94         uintmax_t pgsize_leaf_dist[NUM_PGSIZES][DIST_DIVISION];
  95         uintmax_t pgsize_ovfl_dist[NUM_PGSIZES][DIST_DIVISION];
  96         uintmax_t pgsize_dup_dist[NUM_PGSIZES][DIST_DIVISION];
  97
  98         /* Info used to track stats across page in a traverse. */
  99         u_int32_t pg_leaf_offset[NUM_PGSIZES];
 100         u_int32_t pg_dup_offset[NUM_PGSIZES];
 101 }TUNER_FF_STAT;
 102
 103 static int __tuner_analyze_btree __P((DB_ENV *, DB *, u_int32_t));
 104 static int __tuner_ff_stat_callback __P((DBC *, PAGE *, void *, int *));
 105 static int __tuner_generate_fillfactor_stats __P((DB_ENV *, DB *,
 106     TUNER_FF_STAT *));
 107 static int __tuner_insert_dupdata __P((DB *, u_int32_t, int, TUNER_FF_STAT *));
 108 static int __tuner_insert_kvpair __P((DB *, u_int32_t, u_int32_t, int, int,
 109     int, TUNER_FF_STAT *));
 110 static int __tuner_leaf_page __P((DBC *, PAGE *, TUNER_FF_STAT *));
 111 static int __tuner_leaf_dupdata __P((DBC*, PAGE *, int, int, u_int32_t,
 112     TUNER_FF_STAT *));
 113 static int __tuner_leaf_dupdata_entries __P((DBC *, PAGE *, int, int, int, int,
 114     TUNER_FF_STAT *));
 115 static int __tuner_opd_data_entries __P((DBC *, PAGE *, int, int,
 116     TUNER_FF_STAT *));
 117 static int __tuner_opd_data __P((DBC *, PAGE *, int, int, TUNER_FF_STAT *));
 118 static int __tuner_opd_page __P((DBC *, PAGE *, TUNER_FF_STAT *));
 119 static int __tuner_print_btree_fillfactor __P((u_int32_t, TUNER_FF_STAT *));
 120 static int __tuner_record_dup_pg __P((int, TUNER_FF_STAT *));
 121 static int __tuner_record_last_opd __P((int, TUNER_FF_STAT *));
 122 static int __tuner_record_leaf_pg __P((int, TUNER_FF_STAT *));
 123 static int __tuner_record_ovfl_pg __P((u_int32_t, int, TUNER_FF_STAT *));
 124
 125 static int get_opd_size __P((DBC*, PAGE*, u_int32_t*));
 126 static int item_size __P((DB *, PAGE *, db_indx_t));
 127 static int item_space __P((DB *, PAGE *, db_indx_t));
 128 int main __P((int, char *[]));
 129 static int open_db __P((DB **, DB_ENV *, char *, char *));
 130 static int sum_opd_page_data_entries __P((DB *, PAGE *));
 131 static int usage __P((void));
 132 static int version_check __P((void));
 133
 134 const char *progname = "db_tuner";
 135
 136 int
 137 main(argc, argv)
 138         int argc;
 139         char *argv[];
 140 {
 141         extern char *optarg;
 142         DB *dbp;
 143         DB_ENV *dbenv;
 144         DBTYPE dbtype;
 145         char *dbname, *home, *subdb;
 146         int ch, is_set_dbfile, ret;
 147         u_int32_t cachesize, verbose;
 148
 149         if ((ret = version_check()) != 0)
 150                 return (ret);
 151
 152         dbenv = NULL;
 153         dbp = NULL;
 154         cachesize = 0;
 155         dbname = home = subdb = NULL;
 156         is_set_dbfile = verbose = 0;
 157         dbtype = DB_UNKNOWN;
 158
 159         while ((ch = getopt(argc, argv, "c:d:h:vs:")) != EOF)
 160                 switch (ch) {
 161                 case 'c':
 162                         cachesize = atoi(optarg);
 163                         break;
 164                 case 'd':
 165                         dbname = optarg;
 166                         is_set_dbfile = 1;
 167                         break;
 168                 case 'h':
 169                         home = optarg;
 170                         break;
 171                 case 's':
 172                         subdb = optarg;
 173                         break;
 174                 case 'v':
 175                         verbose = 1;
 176                         break;
 177                 default:
 178                         usage();
 179                 }
 180
 181         /* Handle possible interruptions. */
 182         __db_util_siginit();
 183
 184         if (!is_set_dbfile)
 185                 usage();
 186
 187         if ((ret = db_env_create(&dbenv, 0)) != 0) {
 188                 fprintf(stderr, "%s: db_env_create: %s\n",
 189                     progname, db_strerror(ret));
 190                 goto err;
 191         }
 192
 193         dbenv->set_errfile(dbenv, stderr);
 194         dbenv->set_errpfx(dbenv, progname);
 195
 196         if ((cachesize != 0) && (ret =
 197             dbenv->set_cachesize(dbenv, (u_int32_t)0, cachesize, 1)) != 0) {
 198                 dbenv->err(dbenv, ret, "DB_ENV->set_cachesize:");
 199                 goto err;
 200         }
 201
 202         /*
 203          * If attaching to a pre-existing environment fails, create a
 204          * private one and try again.
 205          */
 206         if ((ret = dbenv->open(dbenv, home, DB_USE_ENVIRON, 0)) != 0 &&
 207             (ret == DB_VERSION_MISMATCH || (ret = dbenv->open(dbenv, home,
 208             DB_CREATE | DB_INIT_MPOOL | DB_USE_ENVIRON | DB_PRIVATE,
 209             0)) != 0)) {
 210                 dbenv->err(dbenv, ret, "DB_ENV->open:");
 211                 goto err;
 212         }
 213
 214         if ((ret = open_db(&dbp, dbenv, dbname, subdb)) != 0) {
 215                 dbenv->err(dbenv, ret, "open_db:");
 216                 goto err;
 217         }
 218
 219         if ((ret = dbp->get_type(dbp, &dbtype)) != 0) {
 220                 dbenv->err(dbenv, ret, "DB->get_type:");
 221                 goto err;
 222         }
 223
 224         switch (dbtype) {
 225         case DB_BTREE:
 226                 if ((ret = __tuner_analyze_btree(dbenv, dbp, verbose)) != 0)
 227                         dbenv->err(dbenv, ret, "__tuner_analyze_btree fails.");
 228                 break;
 229         default:
 230                 dbenv->errx(dbenv, DB_STR("5001",
 231                     "%s: Unsupported database type"), progname);
 232         }
 233
 234 err:
 235         if (dbp != NULL && (ret = dbp->close(dbp, 0)) != 0)
 236                 dbenv->err(dbenv, ret, "DB->close: %s", dbname);
 237
 238         if (dbenv != NULL && (ret = dbenv->close(dbenv, 0)) != 0)
 239                 fprintf(stderr, "%s: dbenv->close: %s", progname,
 240                     db_strerror(ret));
 241
 242         /* Resend any caught signal. */
 243         __db_util_sigresend();
 244
 245         return (ret == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 246 }
 247
 248 /*
 249  * Generate the simulated statistics for each different btree pagesize,
 250  * then print out this information if verbose enabled, finally make our
 251  * recommendation of our best pagesize based on our simulated results.
 252  */
 253 static int
 254 __tuner_analyze_btree(dbenv, dbp, verbose)
 255         DB_ENV *dbenv;
 256         DB *dbp;
 257         u_int32_t verbose;
 258 {
 259         TUNER_FF_STAT stats;
 260         int ret;
 261
 262         memset(&stats, 0, sizeof(TUNER_FF_STAT));
 263
 264         if ((ret = __tuner_generate_fillfactor_stats(dbenv, dbp,
 265             &stats)) != 0) {
 266                 dbenv->err(dbenv, ret,
 267                     "__tuner_generate_fillfactor_stats fails.");
 268                 return (ret);
 269         }
 270
 271         (void)__tuner_print_btree_fillfactor(verbose, &stats);
 272
 273         return (EXIT_SUCCESS);
 274 }
 275
 276 /* Traverse the database to gather simulated statistics for each pagesize.*/
 277 static int
 278 __tuner_generate_fillfactor_stats(dbenv, dbp, stats)
 279         DB_ENV *dbenv;
 280         DB *dbp;
 281         TUNER_FF_STAT *stats;
 282 {
 283         DBC *dbc;
 284         int i, ret, t_ret;
 285
 286         ret = t_ret = 0;
 287
 288         if ((ret = dbp->cursor(dbp, NULL, &dbc, 0)) != 0) {
 289                 dbenv->err(dbenv, ret, "DB_ENV->cursor:");
 290                 return (ret);
 291         }
 292
 293         /*
 294          * Call the internal Berkeley DB function, that triggers a callback
 295          * for each page in a btree database.
 296          */
 297         if ((ret = __bam_traverse(dbc, DB_LOCK_READ, PGNO_INVALID,
 298             __tuner_ff_stat_callback, (void *)stats)) != 0) {
 299                 dbenv->err(dbenv, ret, "__bam_traverse:");
 300                 goto err;
 301         }
 302
 303         /*
 304          * Record the last simulated page for leaf and dup page,
 305          * which ensure at least one page is used.
 306          */
 307         for (i = 0; i < NUM_PGSIZES; ++i) {
 308                 if (stats->pg_leaf_offset[i] > 0 &&
 309                     (ret = __tuner_record_leaf_pg(i, stats)) != 0) {
 310                         dbenv->err(dbenv, ret, "__tuner_record_leaf");
 311                         break;
 312                 }
 313
 314                 if (stats->pg_dup_offset[i] > 0 &&
 315                     (ret = __tuner_record_dup_pg(i, stats)) != 0) {
 316                         dbenv->err(dbenv, ret, "__tuner_record_dup_pg");
 317                         break;
 318                 }
 319         }
 320
 321 err:
 322         if(dbc != NULL && (t_ret = dbc->close(dbc)) != 0)
 323                 dbenv->err(dbenv, t_ret, "DBC->close:");
 324
 325         if (ret == 0 && t_ret != 0)
 326                 ret = t_ret;
 327
 328         return (ret);
 329 }
 330
 331 /*
 332  * This callback is used in __bam_traverse. When traversing each page in
 333  * the BTREE, it retrieves each record for simulation.
 334  */
 335 static int
 336 __tuner_ff_stat_callback(dbc, h, cookie, putp)
 337         DBC *dbc;
 338         PAGE *h;
 339         void *cookie;
 340         int *putp;
 341 {
 342         DB_ENV *dbenv;
 343         int ret;
 344
 345         dbenv = dbc->dbenv;
 346         *putp = 0;
 347
 348         switch (TYPE(h)) {
 349         case P_LBTREE:
 350                 if ((ret = __tuner_leaf_page(dbc, h, cookie)) != 0) {
 351                         dbenv->err(dbenv, ret, "__tuner_leaf_page");
 352                         return (ret);
 353                 }
 354                 break;
 355         case P_LDUP:
 356         case P_LRECNO:
 357                 /* Coming a new off-page duplicate set.*/
 358                 if (h->prev_pgno == PGNO_INVALID &&
 359                     (ret = __tuner_opd_page(dbc, h, cookie)) != 0) {
 360                         dbenv->err(dbenv, ret, "__tuner_opd_page:");
 361                         return (ret);
 362                 }
 363                 break;
 364         case P_IBTREE:
 365         case P_IRECNO:
 366         case P_OVERFLOW:
 367                 break;
 368         default:
 369                 return (EXIT_FAILURE);
 370         }
 371
 372         return (EXIT_SUCCESS);
 373 }
 374
 375 /*
 376  * Deal with the leaf page of existing database. This includes:
 377  * 1: determine the on-page duplicate set, and calculate its total size
 378  * 2: decise where should this set go (on-page or off-page) in the later
 379  *     simulation stage and do some "movement".
 380  * 3: "move" the unique key data pairs to the simulated leaf pages.
 381  */
 382 static int
 383 __tuner_leaf_page(dbc, h, cookie)
 384         DBC *dbc;
 385         PAGE *h;
 386         TUNER_FF_STAT *cookie;
 387 {
 388         DB *dbp;
 389         DB_ENV *dbenv;
 390         db_indx_t findx, lindx, indx, *inp, top;
 391         u_int32_t data_sz, key_sz, onpd_sz;
 392         int i, ret, in_data_type;
 393
 394         dbp = dbc->dbp;
 395         dbenv = dbp->dbenv;
 396         /*
 397          * Use some macros from db_page.h to retrieve information from the
 398          * page. P_INP retrieves the offset to the start of page index array.
 399          * NUM_ENT retrieves the number of items on the page.
 400          */
 401         inp = P_INP(dbp, h);
 402         top = NUM_ENT(h);
 403         ret = 0;
 404
 405         for (indx = 0; indx < top;) {
 406                 /*
 407                  * If on-page duplicate, first calculate the total size,
 408                  * including one key and all data.
 409                  */
 410                 onpd_sz = 0;
 411                 if ((indx + P_INDX) < top && inp[indx] == inp[indx + P_INDX]) {
 412
 413                         /* Ignore deleted items. */
 414                         if (B_DISSET(GET_BKEYDATA(dbp, h, indx)->type))
 415                                 continue;
 416
 417                         /*  Count the key once. */
 418                         onpd_sz += item_space(dbp, h, indx);
 419
 420                         for (findx = indx;
 421                             indx < top && inp[findx] == inp[indx];
 422                             indx += P_INDX) {
 423                                 /* Ignore deleted items. */
 424                                 if (B_DISSET(GET_BKEYDATA(dbp, h,
 425                                     indx + O_INDX)->type))
 426                                         continue;
 427                                 /* Count all the data items. */
 428                                 onpd_sz += item_space(dbp, h, indx + O_INDX);
 429                         }
 430
 431                         /*Indx range of on-page duplicate set: [findx, lindx)*/
 432                         lindx = indx;
 433
 434                         if (onpd_sz == 0)
 435                                 return (EXIT_INSERT_ZERO_ONPGDUP);
 436
 437                         /* "Move" on-page duplicate set to simualted pages.*/
 438                         if ((ret = __tuner_leaf_dupdata(dbc, h, findx, lindx,
 439                             onpd_sz, cookie)) != 0) {
 440                                 dbenv->err(dbenv, ret, "__tuner_leaf_dupdata");
 441                                 return (ret);
 442                         }
 443                 } else {
 444                         in_data_type = INSERT_NORMAL;
 445                         /* Ignore deleted items. */
 446                         if (B_DISSET(GET_BKEYDATA(dbp, h, indx)->type))
 447                                 continue;
 448
 449                         /* First consider key. */
 450                         key_sz = item_size(dbp, h, indx);
 451
 452                         /* Ignore deleted items. */
 453                         if (B_DISSET(GET_BKEYDATA(dbp, h, indx + O_INDX)->type))
 454                                 continue;
 455
 456                         /* next consider data.*/
 457                         if (B_TYPE(GET_BKEYDATA(dbp, h,
 458                             indx + O_INDX)->type) == B_DUPLICATE) {
 459                                 /*
 460                                  * Off-page duplicate set is not handled here
 461                                  * but on the duplicate pages.
 462                                  * Here the key is inserted into "simulated"
 463                                  * leaf_page.
 464                                  */
 465                                 in_data_type = INSERT_NOTHING;
 466                                 data_sz = 0;
 467                         } else
 468                                 data_sz = item_size(dbp, h, indx + O_INDX);
 469
 470                         for (i = 0; i < NUM_PGSIZES; ++i) {
 471                                 if ((ret = __tuner_insert_kvpair(dbp, key_sz,
 472                                     data_sz, i, INSERT_NORMAL, in_data_type,
 473                                     cookie)) != 0) {
 474                                         dbenv->err(dbenv, ret,
 475                                             "__tuner_insert_kvpair");
 476                                         break;
 477                                 }
 478                         }
 479
 480                         indx += P_INDX;
 481                 }
 482         }
 483
 484         return (ret);
 485 }
 486
 487 /*
 488  * "Move" the on-page duplicate data set from the specific page to our
 489  * simulated databases (Indx range of this on-page duplicate set:
 490  * [findx, lindx)), it includes following steps:
 491  *
 492  * First check where should this set go (on-page or off-page duplicate tree).
 493  *
 494  * This is determined as "If total size of duplicate data set is more than 25%
 495  * of a specific page size, then this set go to off-page duplicate tree.
 496  * Otherwise, it goes to on-page duplicate. "
 497  *
 498  * Then "move" this duplicate set to our simulated pages in each simulated
 499  * database.
 500  */
 501 static int
 502 __tuner_leaf_dupdata(dbc, h, findx, lindx, dup_sz, cookie)
 503         DBC *dbc;
 504         PAGE *h;
 505         int findx, lindx;
 506         u_int32_t dup_sz;
 507         TUNER_FF_STAT *cookie;
 508 {
 509         DB_ENV *dbenv;
 510         int i, is_opd, ret;
 511         u_int32_t pgsize;
 512
 513         dbenv = dbc->dbenv;
 514
 515         for (i = 0; i < NUM_PGSIZES; ++i) {
 516                 pgsize = (1 << i) * DB_MIN_PGSIZE;
 517
 518                 /* Check whether this duplicate set go to opd? */
 519                 is_opd = (dup_sz < (pgsize / 4)) ? 0 : 1;
 520
 521                 /* "Move" this on-page duplicate to our simulated pages. */
 522                 if ((ret = __tuner_leaf_dupdata_entries(dbc, h, findx,
 523                     lindx, i, is_opd, cookie)) != 0) {
 524                         dbenv->err(dbenv, ret, "__tuner_leaf_dupdata_entries");
 525                         return (ret);
 526                 }
 527
 528                 /*
 529                  * Record the last simulated duplicate pages for a finished
 530                  * off-page duplicate set then reset the offset to zero
 531                  * for next opd set.
 532                  */
 533                 if (is_opd &&
 534                     (ret = __tuner_record_last_opd(i, cookie)) != 0) {
 535                         dbenv->err(dbenv, ret, "__tuner_record_last_opd");
 536                         return (ret);
 537                 }
 538         }
 539
 540         return (EXIT_SUCCESS);
 541 }
 542
 543 /*
 544  * "Move" the on-page duplicate set [findx, lindx) on the specific page to
 545  * simulated database with pagesize = (1 << indx_pgsz) * DB_MIN_PGSIZE;
 546  */
 547 static int
 548 __tuner_leaf_dupdata_entries(dbc, h, findx, lindx, indx_pgsz, is_opd, cookie)
 549         DBC *dbc;
 550         PAGE *h;
 551         int findx, lindx, indx_pgsz, is_opd;
 552         TUNER_FF_STAT *cookie;
 553 {
 554         DB *dbp;
 555         DB_ENV *dbenv;
 556         db_indx_t indx;
 557         u_int32_t data_sz, key_sz;
 558         int ret, in_key_type;
 559
 560         dbp = dbc->dbp;
 561         dbenv = dbp->dbenv;
 562
 563         for (indx = findx; indx < lindx; indx += P_INDX) {
 564
 565                 key_sz = 0;
 566                 in_key_type = INSERT_SLOT;
 567                 /*
 568                  * For on-page duplicate data, the key is inserted once,
 569                  * then its corresponding data.
 570                  */
 571                 if (indx == findx) {
 572                         /* Ignore deleted items. */
 573                         if (B_DISSET(GET_BKEYDATA(dbp, h, indx)->type))
 574                                 continue;
 575
 576                         key_sz = item_size(dbp, h, indx);
 577                         in_key_type = INSERT_NORMAL;
 578
 579                         /*
 580                          * If is_opd, then insert a key + B_DUPLICATE pair for
 581                          * this on-page duplicate to simulated leaf page.
 582                          * INSERT_BDUPLICATE: B_DUPLICATE point.
 583                          */
 584                         if (is_opd && (ret =
 585                             __tuner_insert_kvpair(dbp, key_sz, 0, indx_pgsz,
 586                             INSERT_NORMAL, INSERT_BDUPLICATE, cookie)) != 0) {
 587                                 dbenv->err(dbenv, ret, "__tuner_insert_kvpair");
 588                                 return (ret);
 589                         }
 590                 }
 591
 592                 /* Ignore deleted items. */
 593                 if (B_DISSET(GET_BKEYDATA(dbp, h, indx + O_INDX)->type))
 594                         continue;
 595
 596                 data_sz = item_size(dbp, h, indx + O_INDX);
 597
 598                 if (is_opd) {
 599                         ret = __tuner_insert_dupdata(dbp, data_sz,
 600                             indx_pgsz, cookie);
 601                         if (ret != 0) {
 602                                 dbenv->err(dbenv, ret,
 603                                     "__tuner_insert_dupdata");
 604                                 return (ret);
 605                         }
 606                 } else {
 607                         ret = __tuner_insert_kvpair(dbp, key_sz, data_sz,
 608                             indx_pgsz, in_key_type, INSERT_NORMAL,
 609                             cookie);
 610
 611                         if (ret != 0) {
 612                                 dbenv->err(dbenv, ret, "__tuner_insert_kvpair");
 613                                 return (ret);
 614                         }
 615                 }
 616         }
 617         return (EXIT_SUCCESS);
 618 }
 619
 620 /* Tuner the off-page duplicate pages from existing database. */
 621 static int
 622 __tuner_opd_page(dbc, h, cookie)
 623         DBC *dbc;
 624         PAGE *h;
 625         TUNER_FF_STAT *cookie;
 626 {
 627         DB_ENV *dbenv;
 628         u_int32_t opd_sz, pgsize;
 629         int i, is_opd, ret;
 630
 631         dbenv = dbc->dbenv;
 632         ret = opd_sz = 0;
 633
 634         /* 1st calculate the total size of the duplicate set. */
 635         if ((ret = get_opd_size(dbc, h, &opd_sz)) != 0) {
 636                 dbenv->err(dbenv, ret, "get_opd_size:");
 637                 return (ret);
 638         }
 639
 640         /* 2nd insert this set into "simulated" pages for each page size.*/
 641         for (i = 0; i < NUM_PGSIZES; ++i) {
 642                 pgsize = (1 << i) * DB_MIN_PGSIZE;
 643
 644                 /* Check whether this duplicate set go to opd? */
 645                 is_opd = (opd_sz < (pgsize / 4)) ? 0 : 1;
 646
 647                 if ((ret = __tuner_opd_data(dbc, h, i, is_opd, cookie)) != 0) {
 648                         dbenv->err(dbenv, ret, "__tuner_opd_data:");
 649                         break;
 650                 }
 651         }
 652
 653         return (ret);
 654 }
 655
 656 /* "Move" all the off-page duplicate data into simulated on-page or off-page.*/
 657 static int
 658 __tuner_opd_data(dbc, h, indx_pgsz, is_opd, cookie)
 659         DBC *dbc;
 660         PAGE *h;
 661         int indx_pgsz, is_opd;
 662         TUNER_FF_STAT *cookie;
 663 {
 664         DB *dbp;
 665         DB_ENV *dbenv;
 666         DB_MPOOLFILE *mpf;
 667         PAGE *p;
 668         db_pgno_t next_pgno;
 669         u_int32_t pgsize;
 670         int ret;
 671
 672         dbp = dbc->dbp;
 673         dbenv = dbp->dbenv;
 674         mpf = dbp->mpf;
 675
 676         p = h;
 677         pgsize = (1 << indx_pgsz) * DB_MIN_PGSIZE;
 678
 679         /*
 680          * __tuner_leaf_page has inserted one key for each opd already,
 681          * so here only a B_DUPLICATE point is inserted into simulate
 682          * leaf page if this duplicate set goes to on-page.
 683          */
 684         if (is_opd) {
 685                 ret = __tuner_insert_kvpair(dbp, 0, 0, indx_pgsz,
 686                     INSERT_NOTHING, INSERT_BDUPLICATE, cookie);
 687
 688                 if (ret!= 0) {
 689                         dbenv->err(dbenv, ret, "__tuner_insert_kvpair");
 690                         return (ret);
 691                 }
 692         }
 693
 694         /* Next insert all the data of this duplicate set. */
 695         while (1) {
 696                 ret = __tuner_opd_data_entries(dbc, h, indx_pgsz, is_opd,
 697                     cookie);
 698                 if (ret != 0) {
 699                         dbenv->err(dbenv, ret, "__tuner_opd_data_entries");
 700                         return (ret);
 701                 }
 702
 703                 next_pgno = p->next_pgno;
 704
 705                 if (p != h && (ret = mpf->put(mpf, p, dbc->priority, 0)) != 0) {
 706                         dbenv->err(dbenv, ret, "DB_MPOOLFILE->put:");
 707                         return (ret);
 708                 }
 709
 710                 if (next_pgno == PGNO_INVALID)
 711                         break;
 712
 713                 if ((ret = mpf->get(mpf, &next_pgno, dbc->txn, 0, &p)) != 0) {
 714                         dbenv->err(dbenv, ret, "DB_MPOOLFILE->get:");
 715                         return (ret);
 716                 }
 717         }
 718
 719         /* Record the last simulate duplicate page if goto off-page duplicate*/
 720         if (is_opd && (ret = __tuner_record_last_opd(indx_pgsz, cookie)) != 0) {
 721                 dbenv->err(dbenv, ret, "__tuner_record_last_opd");
 722                 return (ret);
 723         }
 724
 725         return (EXIT_SUCCESS);
 726 }
 727
 728 /*
 729  * "Move" the off-page duplicate data set to our simulated on-page or
 730  * off-page.
 731  */
 732 static int
 733 __tuner_opd_data_entries(dbc, h, indx_pgsz, is_opd, cookie)
 734         DBC *dbc;
 735         PAGE *h;
 736         int indx_pgsz, is_opd;
 737         TUNER_FF_STAT *cookie;
 738 {
 739         DB *dbp;
 740         DB_ENV *dbenv;
 741         db_indx_t indx;
 742         u_int32_t data_sz;
 743         int ret;
 744
 745         dbp = dbc->dbp;
 746         dbenv = dbp->dbenv;
 747
 748         for (indx = 0; indx < NUM_ENT(h); indx += O_INDX) {
 749                 /* Ignore deleted items. */
 750                 if (B_DISSET(GET_BKEYDATA(dbp, h, indx)->type))
 751                         continue;
 752
 753                 data_sz = item_size(dbp, h, indx);
 754
 755                 if (is_opd) {
 756                         ret = __tuner_insert_dupdata(dbp, data_sz,
 757                             indx_pgsz, cookie);
 758
 759                         if (ret != 0) {
 760                                 dbenv->err(dbenv, ret,
 761                                     "__tuner_insert_dupdata");
 762                                 return (ret);
 763                         }
 764                 } else {
 765                         /*
 766                          * __tuner_leaf_page has inserted one key for each
 767                          * opd already (this will insert moment later),
 768                          * so only data items and key slots are inserted.
 769                          */
 770                         ret = __tuner_insert_kvpair(dbp, 0, data_sz,
 771                             indx_pgsz, INSERT_SLOT, INSERT_NORMAL,
 772                             cookie);
 773
 774                         if (ret != 0) {
 775                                 dbenv->err(dbenv, ret,
 776                                     "__tuner_insert_kvpair");
 777                                 return (ret);
 778                         }
 779                 }
 780         }
 781         return (EXIT_SUCCESS);
 782 }
 783
 784 /*
 785  * Try to insert a key and data pair into simulated leaf pages.
 786  * Key and data pairs are always stored (or referenced) on the same leaf page.
 787  */
 788 static int
 789 __tuner_insert_kvpair(dbp, key_sz, data_sz, indx_pgsz, in_key, in_data, stats)
 790         DB *dbp;
 791         u_int32_t key_sz, data_sz;
 792         int indx_pgsz, in_key, in_data;
 793         TUNER_FF_STAT *stats;
 794 {
 795         DB_ENV *dbenv;
 796         int is_big_data, is_big_key, ret;
 797         u_int32_t needed, pgsize;
 798
 799         dbenv = dbp->dbenv;
 800         is_big_data = is_big_key = 0;
 801         needed = 0;
 802         pgsize = (1 << indx_pgsz) * DB_MIN_PGSIZE;
 803
 804         if (key_sz > B_MINKEY_TO_OVFLSIZE(dbp, 2, pgsize))
 805                 is_big_key = 1;
 806
 807         if (data_sz > B_MINKEY_TO_OVFLSIZE(dbp, 2, pgsize))
 808                 is_big_data = 1;
 809
 810         if (is_big_key) {
 811                 needed += BOVERFLOW_PSIZE;
 812
 813                 /* Add big key into ovfl pages. */
 814                 if ((ret =
 815                     __tuner_record_ovfl_pg(key_sz, indx_pgsz, stats)) != 0) {
 816                         dbenv->err(dbenv, ret, "__tuner_record_ovfl_pg:key_sz");
 817                         return (ret);
 818                 }
 819         } else {
 820                 /*
 821                  * key_sz = INSERT_SLOT indicates no key is inserted
 822                  * but a slot in the inp array, e.g., on-page duplicate.
 823                  * key_sz = INSERT_NOTHING indicates no key no slot is
 824                  * inserted.
 825                  */
 826                 if (in_key == INSERT_NOTHING)
 827                         needed += 0;
 828                 else if (in_key == INSERT_SLOT)
 829                         needed += sizeof(db_indx_t);
 830                 else if (in_key == INSERT_NORMAL)
 831                         needed += BKEYDATA_PSIZE(key_sz);
 832         }
 833
 834         if (is_big_data) {
 835                 needed += BOVERFLOW_PSIZE;
 836
 837                 /* Add big data into ovfl pages. */
 838                 if ((ret =
 839                     __tuner_record_ovfl_pg(data_sz, indx_pgsz, stats)) != 0) {
 840                         dbenv->err(dbenv, ret, "__tuner_record_ovfl_pg");
 841                         return (ret);
 842                 }
 843         } else {
 844                 /*
 845                  * in_data = INSERT_BDUPLICATE indicates a B_DUPLICATE is
 846                  * inserted, e.g., off-page duplicate case.
 847                  * in_data = INSERT_NOTHING indicates nothing is inserted,
 848                  * happens when there is a key + B_DUPLICATE pair in
 849                  * __tuner_leaf_page, in which case, only the key is inserted
 850                  * but no data because the data will considered in
 851                  * __tuner_opd_page when an off-page
 852                  * duplicate set is coming.
 853                  */
 854                 if (in_data == INSERT_NOTHING)
 855                         needed += 0;
 856                 else if (in_data == INSERT_BDUPLICATE)
 857                         needed += BOVERFLOW_PSIZE;
 858                 else if (in_data == INSERT_NORMAL)
 859                         needed += BKEYDATA_PSIZE(data_sz);
 860         }
 861
 862         if (needed == 0)
 863                 return (EXIT_INSERT_ZERO_NEED);
 864
 865         /* 1st leaf page, add overhead size. */
 866         if (stats->pg_leaf_offset[indx_pgsz] == 0)
 867                 stats->pg_leaf_offset[indx_pgsz] = SIZEOF_PAGE;
 868
 869         if ((stats->pg_leaf_offset[indx_pgsz] + needed) > pgsize) {
 870                 /* No enough space, then record current page info. */
 871                 if ((ret = __tuner_record_leaf_pg(indx_pgsz, stats)) != 0) {
 872                         dbenv->err(dbenv, ret, "__tuner_record_leaf_pg");
 873                         return (ret);
 874                 }
 875
 876                 /* Insert pair into new page. */
 877                 stats->pg_leaf_offset[indx_pgsz] = needed + SIZEOF_PAGE;
 878         } else
 879                 stats->pg_leaf_offset[indx_pgsz]  += needed;
 880
 881         return (EXIT_SUCCESS);
 882 }
 883
 884 /* Try to insert a duplicate data into simulated off duplicate pages. */
 885 static int
 886 __tuner_insert_dupdata(dbp, data_sz, indx_pgsz, stats)
 887         DB *dbp;
 888         u_int32_t data_sz;
 889         int indx_pgsz;
 890         TUNER_FF_STAT *stats;
 891 {
 892         DB_ENV *dbenv;
 893         int is_big_data, ret;
 894         u_int32_t needed, pgsize;
 895
 896         dbenv = dbp->dbenv;
 897         is_big_data = 0;
 898         needed = 0;
 899         pgsize = (1 << indx_pgsz) * DB_MIN_PGSIZE;
 900
 901         if (data_sz > B_MINKEY_TO_OVFLSIZE(dbp, 2, pgsize))
 902                 is_big_data = 1;
 903
 904         if (is_big_data) {
 905                 needed = BOVERFLOW_PSIZE;
 906
 907                 /* Add big data into ovfl pages. */
 908                 if ((ret =
 909                     __tuner_record_ovfl_pg(data_sz, indx_pgsz, stats)) != 0) {
 910                         dbenv->err(dbenv, ret, "__tuner_record_ovfl_pg");
 911                         return (ret);
 912                 }
 913         } else
 914                 needed += BKEYDATA_PSIZE(data_sz);
 915
 916         if (needed == 0)
 917                 return (EXIT_INSERT_ZERO_NEED);
 918
 919         /* 1st opd page, add overhead size. */
 920         if (stats->pg_dup_offset[indx_pgsz] == 0)
 921                 stats->pg_dup_offset[indx_pgsz] = SIZEOF_PAGE;
 922
 923         if ((stats->pg_dup_offset[indx_pgsz] + needed) > pgsize) {
 924                 /* no enough space then record current page info. */
 925                 if ((ret = __tuner_record_dup_pg(indx_pgsz, stats)) != 0) {
 926                         dbenv->err(dbenv, ret, "__tuner_record_dup_pg");
 927                         return (ret);
 928                 }
 929
 930                 /* insert new item into new page. */
 931                 stats->pg_dup_offset[indx_pgsz] = needed + SIZEOF_PAGE;
 932         } else
 933                 stats->pg_dup_offset[indx_pgsz]  += needed;
 934
 935         return (EXIT_SUCCESS);
 936 }
 937
 938 /* Insert big item into simulated over flow pages. */
 939 static int
 940 __tuner_record_ovfl_pg(size, indx_pgsz, stats)
 941         u_int32_t size;
 942         int indx_pgsz;
 943         TUNER_FF_STAT *stats;
 944 {
 945         u_int32_t pgsize = (1 << indx_pgsz) * DB_MIN_PGSIZE;
 946         int dist;
 947
 948         /* Update OVFLPAGE list: 1. Add to "full" ovfl pages.*/
 949         stats->pgsize_ovfl_dist[indx_pgsz][DIST_DIVISION - 1] +=
 950             (size / (pgsize - SIZEOF_PAGE));
 951         /* Update OVFLPAGE list: 2. Add the remainder.*/
 952         size = size % (pgsize - SIZEOF_PAGE);
 953         dist = (int)(((double)(size + SIZEOF_PAGE) *
 954             (DIST_DIVISION - 1)) / pgsize);
 955
 956         /* assert(dist < DIST_DIVISION); */
 957         if (dist >= DIST_DIVISION)
 958                 return (EXIT_DIST_OUTRANGE);
 959
 960         ++stats->pgsize_ovfl_dist[indx_pgsz][dist];
 961
 962         return (EXIT_SUCCESS);
 963 }
 964
 965 /* Record simulated leaf page if it has no space to contain new record. */
 966 static int
 967 __tuner_record_leaf_pg(indx_pgsz, stats)
 968         int indx_pgsz;
 969         TUNER_FF_STAT *stats;
 970 {
 971         int dist;
 972         u_int32_t pgsize;
 973
 974         pgsize = (1 << indx_pgsz) * DB_MIN_PGSIZE;
 975
 976         /* First calculate its fill factor. */
 977         dist = (int)(((double)stats->pg_leaf_offset[indx_pgsz] *
 978             (DIST_DIVISION - 1)) / pgsize);
 979
 980         /* assert(dist < DIST_DIVISION); */
 981         if (dist >= DIST_DIVISION)
 982                 return (EXIT_DIST_OUTRANGE);
 983
 984         /* Then add one page to its corresponding distribution. */
 985         ++stats->pgsize_leaf_dist[indx_pgsz][dist];
 986
 987         return (EXIT_SUCCESS);
 988 }
 989
 990 /* Record simulated duplicate page if it has no enough space for new record. */
 991 static int
 992 __tuner_record_dup_pg(indx_pgsz, stats)
 993         int indx_pgsz;
 994         TUNER_FF_STAT *stats;
 995 {
 996         int dist;
 997         u_int32_t pgsize;
 998
 999         pgsize = (1 << indx_pgsz) * DB_MIN_PGSIZE;
1000
1001         /* First calculate its fill factor. */
1002         dist = (int)(((double)stats->pg_dup_offset[indx_pgsz] *
1003             (DIST_DIVISION - 1)) / pgsize);
1004
1005         /* assert(dist < DIST_DIVISION); */
1006         if (dist >= DIST_DIVISION)
1007                 return (EXIT_DIST_OUTRANGE);
1008
1009         /* Then add one page to its corresponding distribution. */
1010         ++stats->pgsize_dup_dist[indx_pgsz][dist];
1011
1012         return (EXIT_SUCCESS);
1013 }
1014
1015 /*
1016  * Record the last simulated duplicate page when an off-page duplicate set
1017  * is finished, also reset its offset to be zero for next set.
1018  */
1019 static int
1020 __tuner_record_last_opd(indx_pgsz, stats)
1021         int indx_pgsz;
1022         TUNER_FF_STAT *stats;
1023 {
1024         int ret;
1025         if (stats->pg_dup_offset[indx_pgsz] != 0 &&
1026             (ret = __tuner_record_dup_pg(indx_pgsz, stats)) != 0)
1027                 return (ret);
1028
1029         /* Reset offset to zero for new opd set. */
1030         stats->pg_dup_offset[indx_pgsz] = 0;
1031
1032         return (EXIT_SUCCESS);
1033 }
1034
1035 /*
1036  * When a new off-page duplicate set is coming, we first calculate its total
1037  * size, which will be used to determine whether this set should go to on-page
1038  * or off-page duplicate tree in our simulation part.
1039  *
1040  * As a off-page duplicate set is in a linked pages, we simply traverse this
1041  * link and sum up all the size of each data in each page.
1042  */
1043 static int
1044 get_opd_size(dbc, h, opd_sz)
1045         DBC *dbc;
1046         PAGE *h;
1047         u_int32_t *opd_sz;
1048 {
1049         DB *dbp;
1050         DB_ENV *dbenv;
1051         DB_MPOOLFILE *mpf;
1052         PAGE *p;
1053         db_pgno_t next_pgno;
1054         int  ret;
1055         u_int32_t dup_sz;
1056
1057         dbp = dbc->dbp;
1058         dbenv = dbp->dbenv;
1059         mpf = dbp->mpf;
1060         dup_sz = 0;
1061         ret = 0;
1062         p = h;
1063
1064         while (1) {
1065                 dup_sz += sum_opd_page_data_entries(dbp, p);
1066
1067                 next_pgno = p->next_pgno;
1068                 if (p != h && (ret =
1069                     mpf->put(mpf, p, dbc->priority, 0)) != 0) {
1070                         dbenv->err(dbenv, ret, "DB_MPOOLFILE->put:");
1071                         return (ret);
1072                 }
1073
1074                 if (next_pgno == PGNO_INVALID)
1075                         break;
1076
1077                 if ((ret =
1078                     mpf->get(mpf, &next_pgno, dbc->txn, 0, &p)) != 0) {
1079                         dbenv->err(dbenv, ret, "DB_MPOOLFILE->get:");
1080                         return (ret);
1081                 }
1082         }
1083
1084         *opd_sz = dup_sz;
1085
1086         return (EXIT_SUCCESS);
1087 }
1088
1089 /* Sum up the space used to contain all the data in a specific page.*/
1090 static int
1091 sum_opd_page_data_entries(dbp, h)
1092         DB *dbp;
1093         PAGE *h;
1094 {
1095         db_indx_t i;
1096         u_int32_t sz;
1097         sz = 0;
1098
1099         for (i = 0; i < NUM_ENT(h); i += O_INDX) {
1100                 /* Ignore deleted items. */
1101                 if (B_DISSET(GET_BKEYDATA(dbp, h, i)->type))
1102                         continue;
1103                 sz += item_space(dbp, h, i);
1104         }
1105
1106         return sz;
1107 }
1108
1109 /* The space used by one item in a page. */
1110 static int
1111 item_space(dbp, h, indx)
1112         DB *dbp;
1113         PAGE *h;
1114         db_indx_t indx;
1115 {
1116         return (B_TYPE(GET_BKEYDATA(dbp, h, indx)->type) == B_KEYDATA ?
1117             BKEYDATA_PSIZE(GET_BKEYDATA(dbp, h, indx)->len) :
1118             BKEYDATA_PSIZE(GET_BOVERFLOW(dbp, h, indx)->tlen));
1119 }
1120
1121 /* The actual length of a item. */
1122 static int
1123 item_size(dbp, h, indx)
1124         DB *dbp;
1125         PAGE *h;
1126         db_indx_t indx;
1127 {
1128         return (B_TYPE(GET_BKEYDATA(dbp, h, indx)->type) == B_KEYDATA ?
1129             GET_BKEYDATA(dbp, h, indx)->len : GET_BOVERFLOW(dbp, h,
1130             indx)->tlen);
1131 }
1132
1133 /* Print out the information according to user's options. */
1134 static int
1135 __tuner_print_btree_fillfactor(verbose, stats)
1136         u_int32_t verbose;
1137         TUNER_FF_STAT *stats;
1138 {
1139         const char * DIVIDE_LINE1 = "=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=";
1140         const char * DIVIDE_LINE2 = "-----------|";
1141         const char * DIVIDE_LINE3 = "---------------------------------------";
1142         double shift_point;
1143         int best_indx, i, j;
1144         u_int32_t pgsize;
1145         u_int64_t minispace, ttpgcnt[NUM_PGSIZES], ttspace[NUM_PGSIZES];
1146         uintmax_t dup_cnt[NUM_PGSIZES], leaf_cnt[NUM_PGSIZES],
1147             ovfl_cnt[NUM_PGSIZES];
1148
1149         shift_point = 0.099;
1150         best_indx = 0;
1151         minispace = UINT64_MAX;
1152
1153         for (i = 0; i < NUM_PGSIZES; ++i) {
1154                 pgsize = (1 << i) * DB_MIN_PGSIZE;
1155                 ovfl_cnt[i] = leaf_cnt[i] = dup_cnt[i] = ttpgcnt[i] = 0;
1156
1157                 for (j = 0; j < DIST_DIVISION; ++j) {
1158                         ovfl_cnt[i] += stats->pgsize_ovfl_dist[i][j];
1159                         leaf_cnt[i] += stats->pgsize_leaf_dist[i][j];
1160                         dup_cnt[i] += stats->pgsize_dup_dist[i][j];
1161                 }
1162
1163                 ttpgcnt[i] = ovfl_cnt[i] + leaf_cnt[i] + dup_cnt[i];
1164                 ttspace[i] = pgsize * ttpgcnt[i];
1165         }
1166
1167         if (verbose == 1) {
1168                 printf("\n %50s \n",
1169                     "===========Simulation Results===========");
1170                 printf("\n  %s\n  %s\n  %s\n",
1171                     "leaf_pg:\t percentage of leaf page in that range",
1172                     "dup_pg:\t percentage of duplicate page in that range",
1173                     "ovfl_pg:\t percentage of over flow page in that range");
1174
1175                 for (i = 0; i < NUM_PGSIZES; ++i) {
1176                         printf("\n\n%s%s\n", DIVIDE_LINE1, DIVIDE_LINE1);
1177                         printf("page size = %d\n", (1 << i) * DB_MIN_PGSIZE);
1178                         printf("%s%s\n", DIVIDE_LINE1, DIVIDE_LINE1);
1179                         printf("%s\n", DIVIDE_LINE3);
1180                         printf("%s   %s   %s   %s\n", "fill factor",
1181                             "leaf_pg", "dup_pg", "ovfl_pg");
1182
1183                         for (j = 0; j < DIST_DIVISION; ++j) {
1184                                 if (j == (DIST_DIVISION - 1))
1185                                         shift_point = 0.000;
1186                                 else
1187                                         shift_point = 0.099;
1188
1189                                 printf("\n[%2.1f-%4.3f]\t",
1190                                     (double)j/(DIST_DIVISION - 1),
1191                                     ((double)j/(DIST_DIVISION - 1) +
1192                                     shift_point));
1193
1194                                 if (leaf_cnt[i] == 0 ||
1195                                     stats->pgsize_leaf_dist[i][j] == 0)
1196                                         printf("%3.2f\t", (double)0);
1197                                 else
1198                                         printf("%3.2f%%\t", (double)
1199                                             (stats->pgsize_leaf_dist[i][j] *
1200                                             100) / leaf_cnt[i]);
1201
1202                                 if (dup_cnt[i] == 0 ||
1203                                     stats->pgsize_dup_dist[i][j] == 0)
1204                                         printf("%3.2f\t", (double)0);
1205                                 else
1206                                         printf("%3.2f%%\t", (double)
1207                                             (stats->pgsize_dup_dist[i][j] *
1208                                             100) / dup_cnt[i]);
1209
1210                                 if (ovfl_cnt[i] == 0 ||
1211                                     stats->pgsize_ovfl_dist[i][j] == 0)
1212                                         printf("%3.2f\t", (double)0);
1213                                 else
1214                                         printf("%3.2f%%\t", (double)
1215                                             (stats->pgsize_ovfl_dist[i][j] *
1216                                             100) / ovfl_cnt[i]);
1217                         }
1218                 }
1219
1220                 printf("\n\n\n\n %55s\n\n",
1221                     "=====Summary of simulated statistic=====");
1222                 printf("  %s\n  %s\n  %s\n  %s\n  %s\n  %s\n\n",
1223                     "pgsize: \tpage size", "storage: \ton-disk space",
1224                     "pgcnt: \ttotal number of all pages "
1225                     "(e.g, sum of ovflcnt, leafcnt, dupcnt)",
1226                     "ovflcnt: \tnumber of over flow pages",
1227                     "leafcnt: \tnumber of leaf pages",
1228                     "dupcnt: \tnumber of duplicate pages");
1229                 printf("%s%s%s%s%s%s\n", DIVIDE_LINE2, DIVIDE_LINE2,
1230                     DIVIDE_LINE2, DIVIDE_LINE2, DIVIDE_LINE2, DIVIDE_LINE2);
1231                 printf(" %10s| %10s| %10s| %10s| %10s| %10s|\n", "pgsize",
1232                     "storage", "pgcnt", "ovflcnt", "leafcnt", "dupcnt");
1233                 printf("%s%s%s%s%s%s\n", DIVIDE_LINE2, DIVIDE_LINE2,
1234                     DIVIDE_LINE2, DIVIDE_LINE2, DIVIDE_LINE2, DIVIDE_LINE2);
1235                 for (i = 0; i < NUM_PGSIZES; ++i) {
1236                         printf(" %10d|", (1 << i) * DB_MIN_PGSIZE);
1237                         printf(" %10u|", (u_int32_t)ttspace[i]);
1238                         if (ttspace[i] != (u_int32_t)ttspace[i])
1239                                 printf("(truncated value reported)");
1240                         printf(" %10u|", (u_int32_t)ttpgcnt[i]);
1241                         if (ttpgcnt[i] != (u_int32_t)ttpgcnt[i])
1242                                 printf("(truncated value reported)");
1243                         printf(" %10u|", (u_int32_t)ovfl_cnt[i]);
1244                         if (ovfl_cnt[i] != (u_int32_t)ovfl_cnt[i])
1245                                 printf("(truncated value reported)");
1246                         printf(" %10u|", (u_int32_t)leaf_cnt[i]);
1247                         if (leaf_cnt[i] != (u_int32_t)leaf_cnt[i])
1248                                 printf("(truncated value reported)");
1249                         printf(" %10u|", (u_int32_t)dup_cnt[i]);
1250                         if (dup_cnt[i] != (u_int32_t)dup_cnt[i])
1251                                 printf("(truncated value reported)");
1252                         printf("\n");
1253                 }
1254                 printf("%s%s%s%s%s%s\n", DIVIDE_LINE2, DIVIDE_LINE2,
1255                     DIVIDE_LINE2, DIVIDE_LINE2, DIVIDE_LINE2, DIVIDE_LINE2);
1256         }
1257
1258         /*
1259          * Choose a page size based on the overflow calculation. If there
1260          * is no overflow consideration, then use the smallest on-disk
1261          * space as a recommended page size.
1262          */
1263         if (ovfl_cnt[0] == 0) {
1264                 minispace =  ttspace[0];
1265                 for (i = 1; i < NUM_PGSIZES; ++i)
1266                         if ((ttspace[i] != 0) && (minispace > ttspace[i])) {
1267                                 minispace = ttspace[i];
1268                                 best_indx = i;
1269                         }
1270         } else
1271                 for (i = 1; i < NUM_PGSIZES; ++i)
1272                         if ((ovfl_cnt[i - 1] - ovfl_cnt[i]) > 0.02 * ttpgcnt[i])
1273                                 best_indx = i;
1274
1275         printf("\n\nFor your input database, we recommend page size = %d \n \t"
1276             "out of 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536 for you.\n",
1277             (1 << best_indx) * DB_MIN_PGSIZE);
1278
1279         return (EXIT_SUCCESS);
1280 }
1281
1282 /* Open the specific existing database. */
1283 static int
1284 open_db(dbpp, dbenv, dbname, subdb)
1285         DB **dbpp;
1286         DB_ENV *dbenv;
1287         char *dbname;
1288         char *subdb;
1289 {
1290         DB *dbp;
1291         int ret = 0;
1292
1293         if ((ret = db_create(&dbp, dbenv, 0)) != 0) {
1294                 dbenv->err(dbenv, ret, "db_create fails.\n");
1295                 return (ret);
1296         }
1297
1298         *dbpp = dbp;
1299
1300         /* Open a database for read-only.*/
1301         if ((ret =
1302             dbp->open(dbp, NULL, dbname, subdb, DB_UNKNOWN, DB_RDONLY, 0)) != 0)
1303                 dbenv->err(dbenv, ret, "DB->open");
1304
1305         return (ret);
1306 }
1307
1308 /* Usage flag information to indicate what can user query for given database.*/
1309 static int
1310 usage()
1311 {
1312         fprintf(stderr, "usage: %s %s\n", progname,
1313             "[-c cachesize] -d file [-h home] [-s database] [-v verbose]");
1314         exit(EXIT_FAILURE);
1315 }
1316
1317 /*Check the verion of Berkeley DB libaray, make sure it is the right version.*/
1318 static int
1319 version_check()
1320 {
1321         int v_major, v_minor, v_patch;
1322
1323         /* Make sure we're loaded with the right version of the DB library. */
1324         (void)db_version(&v_major, &v_minor, &v_patch);
1325         if (v_major != DB_VERSION_MAJOR || v_minor != DB_VERSION_MINOR) {
1326                 fprintf(stderr, DB_STR_A("5002",
1327                     "%s: version %d.%d doesn't match library version %d.%d\n",
1328                     "%s %d %d %d %d"), progname, DB_VERSION_MAJOR,
1329                     DB_VERSION_MINOR, v_major, v_minor);
1330
1331                 return (EXIT_FAILURE);
1332         }
1333
1334         return (EXIT_SUCCESS);
1335 }