Index out of order for IntFieldIndex

[danthegoodman1]

With the following code (slight modification of example code), I found results of the rows being out of order.

Based on the example I would assume that the results would be in order.

Code:

package main

import (
	"fmt"
	"time"

	"github.com/hashicorp/go-memdb"
	"github.com/segmentio/ksuid"
)

func main() {
	// Create a sample struct
	type Person struct {
		Email string
		Name  string
		Age   int
	}

	// Create the DB schema
	schema := &memdb.DBSchema{
		Tables: map[string]*memdb.TableSchema{
			"person": {
				Name: "person",
				Indexes: map[string]*memdb.IndexSchema{
					"id": {
						Name:    "id",
						Unique:  true,
						Indexer: &memdb.StringFieldIndex{Field: "Email"},
					},
					"age": {
						Name:    "age",
						Unique:  false,
						Indexer: &memdb.IntFieldIndex{Field: "Age"},
					},
				},
			},
		},
	}

	// Create a new data base
	db, err := memdb.NewMemDB(schema)
	if err != nil {
		panic(err)
	}

	// Create a write transaction
	txn := db.Txn(true)

	// Insert very many people
	for i := 0; i < 1000; i++ {
		p := &Person{
			Email: ksuid.New().String(),
			Age:   i,
		}
		if err := txn.Insert("person", p); err != nil {
			panic(err)
		}
		// fmt.Println("INserted", i)
	}
	fmt.Println("inserted")

	// Commit the transaction
	txn.Commit()

	// Create read-only transaction
	txn = db.Txn(false)
	defer txn.Abort()

	// Range scan over people with ages between 25 and 35 inclusive
	start := time.Now()
	it, err := txn.LowerBound("person", "age", 1)
	if err != nil {
		panic(err)
	}

	fmt.Println("People aged 25 - 35:")
	i := 0
	for obj := it.Next(); obj != nil; obj = it.Next() {
		p := obj.(*Person)
		fmt.Printf("  %s is aged %d\n", p.Email, p.Age)
		// if p.Age > 200 {
		// 	break
		// }
		i++
		if i == 100 {
			break
		}
	}
	fmt.Println(time.Since(start))
}

Output:

inserted
People aged 25 - 35:
  21ZfMMKi3eIPU3bZOXN2MueNVFC is aged 1
  21ZfMLObHa1548szSMA4t4stgMh is aged 2
  21ZfMG9Wn7AQttLuhv54A3wcjdq is aged 3
  21ZfMMoydQX1MocpnLR9koVsbOO is aged 4
  21ZfMLbElyEiw8oqSoLoP6CcTtU is aged 5
  21ZfMIHZfEqLar18hb6MyVTptSz is aged 6
  21ZfMNNDLrsrUp4CsQvVyzE9hO1 is aged 7
  21ZfMGGz9D84sx0lGNZNM4KefFU is aged 8
  21ZfMLX1HPc9luyo3qEA4D92mh4 is aged 9
  21ZfMMkFCvTqD3h0eLKyytVyL9l is aged 10
  21ZfMFkBm7dwi3EPln2VLHnwob5 is aged 11
  21ZfMFgIMjvt8m3Kt7OcGcrFSNi is aged 12
  21ZfMJw348zQ0zzdtfB7wuAnZ0n is aged 13
  21ZfMJEKCmOyyDpYWYsPsB4TYT4 is aged 14
  21ZfMFhfwNq5DsB7b8yTwL8e242 is aged 15
  21ZfMIiklNhWrfZKSw85J5lB88n is aged 16
  21ZfMIEjiSS5OF0jL45zo4uw4cN is aged 17
  21ZfMKR0phJOhwcQw1uVgwUw58z is aged 18
  21ZfMJn8F8ix9vQ3eXz9TmeP8Jr is aged 19
  21ZfMMuJdacG1Ns3XRzx1fiWyio is aged 20
  21ZfMJsT309ghr2UJdgWNxfYif6 is aged 21
  21ZfMGMNrW7a1fpLnjQYK5goMLK is aged 22
  21ZfMMBC5d7fRGRZHBygY8p0RVH is aged 23
  21ZfMFyUVofmkDOXXjsT0yf2NaC is aged 24
  21ZfMLeEhUXKeI1LdCDOUung68u is aged 25
  21ZfML3QnDhUkNLDP59rma1lS7z is aged 26
  21ZfMNBtH47fZLVjyrZekP2d7ju is aged 27
  21ZfMJTWv9u2VbqR4F5B7wXIpIx is aged 28
  21ZfMJO8NbfsEF7Xu6PzbyP3lw3 is aged 29
  21ZfMJ56lOXMV8WdWnBPgzW9kYO is aged 30
  21ZfMFvSItxvMvuJh8Z5el0x0vC is aged 31
  21ZfMKc7cTdDKxFaigQ6csXlT9f is aged 32
  21ZfMI5njSIOtmeZPYEaw0VUKVk is aged 33
  21ZfMIKLK4BH9k2j8oJGnnLgDDl is aged 34
  21ZfMJKu6LaogaZzvS57AIOTWa3 is aged 35
  21ZfMGOd9lcMDdRVWlFR9yyvMHz is aged 36
  21ZfMFwONDqAfh5UuSKQyFyo6mV is aged 37
  21ZfMK5TXeFVLJVjsANXidatBic is aged 38
  21ZfMHSkeVxEETr3b04mPSVjUQl is aged 39
  21ZfMIvFosiaEHQXEV3IqLWpHNl is aged 40
  21ZfMJjYKiHHUeqTcWKw1oWKIE2 is aged 41
  21ZfMKMujeeCzJziK1IltGV9ZrQ is aged 42
  21ZfMLPQLmwcbCpntzxQLl9AY2e is aged 43
  21ZfMJOsp4XWqQ5GxL6449nbPq0 is aged 44
  21ZfMKarrJ8pJqlRELJV2ztyzMb is aged 45
  21ZfMIKgiiMJGcxFhQKndcOO9QX is aged 46
  21ZfMKYxGCJxHvjtjJcEB9AHrxA is aged 47
  21ZfMMlBDe4CiAc2ncX0TQYWEX6 is aged 48
  21ZfMHIL1Z9dALZStOJIXPss1ie is aged 49
  21ZfMMsh7dvzqXTV5j0YchSXQ0p is aged 50
  21ZfMIjHK4KTWpRnOYkopppzfIF is aged 51
  21ZfMLkemfP2f7dCDk8k2XcvZHY is aged 52
  21ZfMIlLYbF5fesjH71qUm8L1Tu is aged 53
  21ZfMJaAhu5RXB31xJaWmy0rYSu is aged 54
  21ZfMGT8a1WsoXvaVy7aCni8WLk is aged 55
  21ZfMNJLw41lx23iLOvM3vlabjF is aged 56
  21ZfMMi8MYqnrvCa4EWUTKQNAGC is aged 57
  21ZfMJPplhdf1TbVtymnB6a0AHd is aged 58
  21ZfMLJtnT5jnRKYljfFN7gAIIC is aged 59
  21ZfMHbs0SDoDCSxbku7toPGPhR is aged 60
  21ZfMIB9QE49c3AtVg7qvN8yDZ7 is aged 61
  21ZfMMeGTeuUU6KAJ8h8LRb5XNM is aged 62
  21ZfMIE9od85kp89U4y7vB2hAVl is aged 63
  21ZfMMxNoT5kyDNB7OVq2BL2foB is aged 64
  21ZfMGa0JbhDYTS2N4HoqB1C6p0 is aged 128
  21ZfMK4v8dJ7h1M3xDuoabZU6QD is aged 192
  21ZfMGDbQjaFYpJ9LJ89kQIb5tp is aged 256
  21ZfMIujwXJU8xfjkRWTScnNTHp is aged 320
  21ZfMICYjUJ3kz5X1cSONVwtx0g is aged 384
  21ZfMMVcMMpLrnaapM4VxMx1fSF is aged 448
  21ZfMGbTsmgYg0MHea4fsmV5XCn is aged 512
  21ZfMKC9iUdS7fXNHCGrgiENnCu is aged 576
  21ZfMHsvapaO4Ho97oMQrTaktw1 is aged 640
  21ZfMICIqVxOcp4OfEea915Q46r is aged 704
  21ZfMGUDI2fyVdYcm0WwdgdfUQV is aged 768
  21ZfMImVF18NB7GXncR0gec7haO is aged 832
  21ZfMKDCnGRv1BnDqad14rzmwpb is aged 896
  21ZfMNNtiBWhwOn2gDpqAc7EZSb is aged 960
  21ZfMKnGTiF8YRMycIFpq0tRzxa is aged 65
  21ZfMJjxf82foQmcCom66hXoEaC is aged 129
  21ZfMJk0PVaUlns8z00OHsczZz5 is aged 193
  21ZfMM1PKTQaktWBzc7ahOKlLzT is aged 257
  21ZfMJ2yhE6qKVJJvL65NeCdnjz is aged 321
  21ZfMHsCDeOcVgn6RINlxjbeIMi is aged 385
  21ZfMMLYCd2kBKMXCMLYqGV7y69 is aged 449
  21ZfMHxl2gIZIE1KRSnEAck7WCm is aged 513
  21ZfMNEBTld9vkQIhteZVoOuYeh is aged 577
  21ZfMLVNVbHOsf8lKiCw6Aw5ria is aged 641
  21ZfMMthuNgtsUQgU0gGea4UMqq is aged 705
  21ZfMGbBbTLAOCIFxZGwS5qsS0N is aged 769
  21ZfMIlfnhTPrheY3PqiUoZKWpE is aged 833
  21ZfMHD4e4yLZEQ2N3j5DJ2KU8x is aged 897
  21ZfMFeW56O1TAh9LeMZdCWEMSw is aged 961
  21ZfMKZwIouXKp8N4TvVPdGe1ga is aged 66
  21ZfMKx1NyfYTI8z4HFplydPO1C is aged 130
  21ZfMKrhq9yyi76X10tTjBIUzDz is aged 194
  21ZfMLlD8q6MHLh42HLcIK4OemN is aged 258
  21ZfMNJjsfcA3Y5WLItkLSN1Uyt is aged 322
  21ZfMJTy6LNDMhhB22VZ1P2YW1i is aged 386
  21ZfMI5oGGhoFF33enXVvBTCL3f is aged 450

[dnephin]

Thank you for the bug report! I suspect this issue is related to #96 and #77. They may be all the same underlying issue. The values are sorted based on how the they are stored in the index.

PR #93 recently fixed a similar problem for the uint indexer. Looking at the implementation I suspect the IntFieldIndex has the same problem. It uses binary.PutVarint instead of ensuring that the correct number of bytes every time. A PR that makes a similar change for the IntFieldIndexer would be great!

[jakedt]

FWIW I initially tried to fix this in #93, but since int is two's complement it's much harder to rely on binary byte ordering to correctly order sequences that include negative numbers. I played around with it a bit before realizing that it was taking too much time and I needed to solve my own problem.

[jakedt]

I had a flash of inspiration that just flipping the most significant bit should scale them into the proper range for byte-wise comparison.

[danthegoodman1]

Awesome!