//cost estimation:
//  sequential small block  = 10
//  sequential medium block = 11
//  sequential large block  = 12
//  random small block      = 30
//  random medium block     = 31
//  random large block      = 32

//reference disk #1: seagate ST31200N:
//  1G
//  2700 cylinders     
//  9 heads
//  bytes per track 1G/2700/9 = 41152
//  5400 rpm = 1000/(5400/60) / 2 = 5.56ms avg rotational latency
//  8.5ms avg seek time
//  readtime(512)  = (1000/(5400/60))/(41152/512) = 0.138
//  readtime(2048) = (1000/(5400/60))/(41152/2048) = 0.553
//  readtime(4096) = (1000/(5400/60))/(41152/4096) = 1.106
//reference disk #2: Quantum Atlas III
//  7200 rpm = 1000/(7200/60) / 2 = 4.17ms avg rotational latency
//  4.5GB
//  5 heads
//  7.5ms
//  estimated bytes per track 100000
//  readtime(512)  = (1000/(7200/60))/(100000/512) = 0.043
//  readtime(2048) = (1000/(7200/60))/(100000/2048) = 0.171
//  readtime(4096) = (1000/(7200/60))/(100000/4096) = 0.342

1000 512-byte blocks
  sequential small block:
    seek
    1000 {
      rotational latency
      readtime 512
    }
    = 1*8.5 + 1000*(5.56+0.138) =     5706.5ms
    = 1*7.5 + 1000*(4.17+0.043) =     4220.5ms
  sequential medium block:
    seek
    250 {
      rotational latency
      readtime 2048
    }
    = 1*8.5 + 250*(5.56+0.553)  =     1536.8ms
    = 1*7.5 + 250*(4.17+0.171)  =     1092.8ms
  sequential large block:
    seek
    125 {
      rotational latency
      readtime 4096
    }
    = 1*8.5 + 125*(5.56+1.106)  =      841.8ms
    = 1*7.5 + 125*(4.17+0.342)  =      571.5ms
  random small block:
    1000 {
      seek
      rotational latency
      readtime 512
    }
    = 1000*(8.5+5.56+0.138)     =    14198ms
    = 1000*(7.5+4.17+0.043)     =    11683ms
  random medium block:
    250 {
      seek
      rotational latency
      readtime 2048
    }
    = 250*(8.5+5.56+0.553)      =     3653ms
    = 250*(7.5+4.17+0.171)      =     2960ms
  random large block:
    125 {
      seek
      rotational latency
      readtime 4096
    }
    = 125*(8.5+5.56+1.106)      =     1895ms
    = 125*(7.5+4.17+0.342)      =     1501ms

class ConditionSet;

typedef int (*recidcallback_t)(recid *r[], int recids,    const ConditionSet *cs, void *extra);

class Index {
public:
        enum operation {
                op_exist,
                op_cardinality,
                op_count_approx,
                op_count_exact,
                op_select
        };
        virtual unsigned long cost(operation op, const ConditionSet *cs);
        
        virtual int           exist(const ConditionSet *cs)        =0;
        virtual int           cardinality(const ConditionSet *cs)  =0;
        virtual unsigned long count_approx(const ConditionSet *cs) =0;
        virtual unsigned long count_exact(const ConditionSet *cs)  =0;

        virtual int           iterate(recidcallback_t func,
                                      const ConditionSet *cs,
                                      void *extra)                 =0;
};