Merge pull request #162 from Shopify/nested_stats2

Recursive/aggregate bucket stats

1 files changed, 154 insertions, 37 deletions

diff --git a/bucket_test.go b/bucket_test.go
index b87031b..f6bd13f 100644
--- a/bucket_test.go
+++ b/bucket_test.go
@@ -560,15 +560,15 @@ func TestBucket_Put_KeyTooLarge(t *testing.T) {
 // Ensure a bucket can calculate stats.
 func TestBucket_Stats(t *testing.T) {
 	withOpenDB(func(db *DB, path string) {
+		big_key := []byte("really-big-value")
 		db.Update(func(tx *Tx) error {
 			// Add bucket with fewer keys but one big value.
-			_, err := tx.CreateBucket([]byte("woojits"))
+			b, err := tx.CreateBucket([]byte("woojits"))
 			assert.NoError(t, err)
-			b := tx.Bucket([]byte("woojits"))
 			for i := 0; i < 500; i++ {
-				b.Put([]byte(strconv.Itoa(i)), []byte(strconv.Itoa(i)))
+				b.Put([]byte(fmt.Sprintf("%03d", i)), []byte(strconv.Itoa(i)))
 			}
-			b.Put([]byte("really-big-value"), []byte(strings.Repeat("*", 10000)))
+			b.Put(big_key, []byte(strings.Repeat("*", 10000)))
 
 			return nil
 		})
@@ -576,19 +576,33 @@ func TestBucket_Stats(t *testing.T) {
 		db.View(func(tx *Tx) error {
 			b := tx.Bucket([]byte("woojits"))
 			stats := b.Stats()
-			assert.Equal(t, stats.BranchPageN, 1)
-			assert.Equal(t, stats.BranchOverflowN, 0)
-			assert.Equal(t, stats.LeafPageN, 6)
-			assert.Equal(t, stats.LeafOverflowN, 2)
-			assert.Equal(t, stats.KeyN, 501)
-			assert.Equal(t, stats.Depth, 2)
-			if os.Getpagesize() != 4096 {
+			assert.Equal(t, 1, stats.BranchPageN, "BranchPageN")
+			assert.Equal(t, 0, stats.BranchOverflowN, "BranchOverflowN")
+			assert.Equal(t, 6, stats.LeafPageN, "LeafPageN")
+			assert.Equal(t, 2, stats.LeafOverflowN, "LeafOverflowN")
+			assert.Equal(t, 501, stats.KeyN, "KeyN")
+			assert.Equal(t, 2, stats.Depth, "Depth")
+
+			branchInuse := pageHeaderSize            // branch page header
+			branchInuse += 6 * branchPageElementSize // branch elements
+			branchInuse += 6 * 3                     // branch keys (6 3-byte keys)
+			assert.Equal(t, branchInuse, stats.BranchInuse, "BranchInuse")
+
+			leafInuse := 6 * pageHeaderSize          // leaf page header
+			leafInuse += 501 * leafPageElementSize   // leaf elements
+			leafInuse += 500*3 + len(big_key)        // leaf keys
+			leafInuse += 1*10 + 2*90 + 3*400 + 10000 // leaf values
+			assert.Equal(t, leafInuse, stats.LeafInuse, "LeafInuse")
+
+			if os.Getpagesize() == 4096 {
 				// Incompatible page size
-				assert.Equal(t, stats.BranchInuse, 125)
-				assert.Equal(t, stats.BranchAlloc, 4096)
-				assert.Equal(t, stats.LeafInuse, 20908)
-				assert.Equal(t, stats.LeafAlloc, 32768)
+				assert.Equal(t, 4096, stats.BranchAlloc, "BranchAlloc")
+				assert.Equal(t, 32768, stats.LeafAlloc, "LeafAlloc")
 			}
+
+			assert.Equal(t, 1, stats.BucketN, "BucketN")
+			assert.Equal(t, 0, stats.InlineBucketN, "InlineBucketN")
+			assert.Equal(t, 0, stats.InlineBucketInuse, "InlineBucketInuse")
 			return nil
 		})
 	})
@@ -610,19 +624,119 @@ func TestBucket_Stats_Small(t *testing.T) {
 		db.View(func(tx *Tx) error {
 			b := tx.Bucket([]byte("whozawhats"))
 			stats := b.Stats()
-			assert.Equal(t, 0, stats.BranchPageN)
-			assert.Equal(t, 0, stats.BranchOverflowN)
-			assert.Equal(t, 1, stats.LeafPageN)
-			assert.Equal(t, 0, stats.LeafOverflowN)
-			assert.Equal(t, 1, stats.KeyN)
-			assert.Equal(t, 1, stats.Depth)
-			if os.Getpagesize() != 4096 {
+			assert.Equal(t, 0, stats.BranchPageN, "BranchPageN")
+			assert.Equal(t, 0, stats.BranchOverflowN, "BranchOverflowN")
+			assert.Equal(t, 0, stats.LeafPageN, "LeafPageN")
+			assert.Equal(t, 0, stats.LeafOverflowN, "LeafOverflowN")
+			assert.Equal(t, 1, stats.KeyN, "KeyN")
+			assert.Equal(t, 1, stats.Depth, "Depth")
+			assert.Equal(t, 0, stats.BranchInuse, "BranchInuse")
+			assert.Equal(t, 0, stats.LeafInuse, "LeafInuse")
+			if os.Getpagesize() == 4096 {
+				// Incompatible page size
+				assert.Equal(t, 0, stats.BranchAlloc, "BranchAlloc")
+				assert.Equal(t, 0, stats.LeafAlloc, "LeafAlloc")
+			}
+			assert.Equal(t, 1, stats.BucketN, "BucketN")
+			assert.Equal(t, 1, stats.InlineBucketN, "InlineBucketN")
+			assert.Equal(t, pageHeaderSize+leafPageElementSize+6, stats.InlineBucketInuse, "InlineBucketInuse")
+			return nil
+		})
+	})
+}
+
+func TestBucket_Stats_EmptyBucket(t *testing.T) {
+
+	withOpenDB(func(db *DB, path string) {
+		db.Update(func(tx *Tx) error {
+			// Add a bucket that fits on a single root leaf.
+			_, err := tx.CreateBucket([]byte("whozawhats"))
+			assert.NoError(t, err)
+			return nil
+		})
+		mustCheck(db)
+		db.View(func(tx *Tx) error {
+			b := tx.Bucket([]byte("whozawhats"))
+			stats := b.Stats()
+			assert.Equal(t, 0, stats.BranchPageN, "BranchPageN")
+			assert.Equal(t, 0, stats.BranchOverflowN, "BranchOverflowN")
+			assert.Equal(t, 0, stats.LeafPageN, "LeafPageN")
+			assert.Equal(t, 0, stats.LeafOverflowN, "LeafOverflowN")
+			assert.Equal(t, 0, stats.KeyN, "KeyN")
+			assert.Equal(t, 1, stats.Depth, "Depth")
+			assert.Equal(t, 0, stats.BranchInuse, "BranchInuse")
+			assert.Equal(t, 0, stats.LeafInuse, "LeafInuse")
+			if os.Getpagesize() == 4096 {
+				// Incompatible page size
+				assert.Equal(t, 0, stats.BranchAlloc, "BranchAlloc")
+				assert.Equal(t, 0, stats.LeafAlloc, "LeafAlloc")
+			}
+			assert.Equal(t, 1, stats.BucketN, "BucketN")
+			assert.Equal(t, 1, stats.InlineBucketN, "InlineBucketN")
+			assert.Equal(t, pageHeaderSize, stats.InlineBucketInuse, "InlineBucketInuse")
+			return nil
+		})
+	})
+}
+
+// Ensure a bucket can calculate stats.
+func TestBucket_Stats_Nested(t *testing.T) {
+	withOpenDB(func(db *DB, path string) {
+		db.Update(func(tx *Tx) error {
+			b, err := tx.CreateBucket([]byte("foo"))
+			assert.NoError(t, err)
+			for i := 0; i < 100; i++ {
+				b.Put([]byte(fmt.Sprintf("%02d", i)), []byte(fmt.Sprintf("%02d", i)))
+			}
+			bar, err := b.CreateBucket([]byte("bar"))
+			assert.NoError(t, err)
+			for i := 0; i < 10; i++ {
+				bar.Put([]byte(strconv.Itoa(i)), []byte(strconv.Itoa(i)))
+			}
+			baz, err := bar.CreateBucket([]byte("baz"))
+			assert.NoError(t, err)
+			for i := 0; i < 10; i++ {
+				baz.Put([]byte(strconv.Itoa(i)), []byte(strconv.Itoa(i)))
+			}
+			return nil
+		})
+
+		mustCheck(db)
+
+		db.View(func(tx *Tx) error {
+			b := tx.Bucket([]byte("foo"))
+			stats := b.Stats()
+			assert.Equal(t, 0, stats.BranchPageN, "BranchPageN")
+			assert.Equal(t, 0, stats.BranchOverflowN, "BranchOverflowN")
+			assert.Equal(t, 2, stats.LeafPageN, "LeafPageN")
+			assert.Equal(t, 0, stats.LeafOverflowN, "LeafOverflowN")
+			assert.Equal(t, 122, stats.KeyN, "KeyN")
+			assert.Equal(t, 3, stats.Depth, "Depth")
+			assert.Equal(t, 0, stats.BranchInuse, "BranchInuse")
+
+			foo := pageHeaderSize            // foo
+			foo += 101 * leafPageElementSize // foo leaf elements
+			foo += 100*2 + 100*2             // foo leaf key/values
+			foo += 3 + bucketHeaderSize      // foo -> bar key/value
+
+			bar := pageHeaderSize           // bar
+			bar += 11 * leafPageElementSize // bar leaf elements
+			bar += 10 + 10                  // bar leaf key/values
+			bar += 3 + bucketHeaderSize     // bar -> baz key/value
+
+			baz := pageHeaderSize           // baz (inline)
+			baz += 10 * leafPageElementSize // baz leaf elements
+			baz += 10 + 10                  // baz leaf key/values
+
+			assert.Equal(t, foo+bar+baz, stats.LeafInuse, "LeafInuse")
+			if os.Getpagesize() == 4096 {
 				// Incompatible page size
-				assert.Equal(t, 0, stats.BranchInuse)
-				assert.Equal(t, 0, stats.BranchAlloc)
-				assert.Equal(t, 38, stats.LeafInuse)
-				assert.Equal(t, 4096, stats.LeafAlloc)
+				assert.Equal(t, 0, stats.BranchAlloc, "BranchAlloc")
+				assert.Equal(t, 8192, stats.LeafAlloc, "LeafAlloc")
 			}
+			assert.Equal(t, 3, stats.BucketN, "BucketN")
+			assert.Equal(t, 1, stats.InlineBucketN, "InlineBucketN")
+			assert.Equal(t, baz, stats.InlineBucketInuse, "InlineBucketInuse")
 			return nil
 		})
 	})
@@ -652,19 +766,22 @@ func TestBucket_Stats_Large(t *testing.T) {
 		db.View(func(tx *Tx) error {
 			b := tx.Bucket([]byte("widgets"))
 			stats := b.Stats()
-			assert.Equal(t, 19, stats.BranchPageN)
-			assert.Equal(t, 0, stats.BranchOverflowN)
-			assert.Equal(t, 1291, stats.LeafPageN)
-			assert.Equal(t, 0, stats.LeafOverflowN)
-			assert.Equal(t, 100000, stats.KeyN)
-			assert.Equal(t, 3, stats.Depth)
-			if os.Getpagesize() != 4096 {
+			assert.Equal(t, 19, stats.BranchPageN, "BranchPageN")
+			assert.Equal(t, 0, stats.BranchOverflowN, "BranchOverflowN")
+			assert.Equal(t, 1291, stats.LeafPageN, "LeafPageN")
+			assert.Equal(t, 0, stats.LeafOverflowN, "LeafOverflowN")
+			assert.Equal(t, 100000, stats.KeyN, "KeyN")
+			assert.Equal(t, 3, stats.Depth, "Depth")
+			assert.Equal(t, 27007, stats.BranchInuse, "BranchInuse")
+			assert.Equal(t, 2598436, stats.LeafInuse, "LeafInuse")
+			if os.Getpagesize() == 4096 {
 				// Incompatible page size
-				assert.Equal(t, 27289, stats.BranchInuse)
-				assert.Equal(t, 61440, stats.BranchAlloc)
-				assert.Equal(t, 2598276, stats.LeafInuse)
-				assert.Equal(t, 5246976, stats.LeafAlloc)
+				assert.Equal(t, 77824, stats.BranchAlloc, "BranchAlloc")
+				assert.Equal(t, 5287936, stats.LeafAlloc, "LeafAlloc")
 			}
+			assert.Equal(t, 1, stats.BucketN, "BucketN")
+			assert.Equal(t, 0, stats.InlineBucketN, "InlineBucketN")
+			assert.Equal(t, 0, stats.InlineBucketInuse, "InlineBucketInuse")
 			return nil
 		})
 	})