irelic.h
Go to the documentation of this file.
1 //File: $Id$
2 // Author: John Wu <John.Wu at ACM.org>
3 // Lawrence Berkeley National Laboratory
4 // Copyright (c) 2000-2016 the Regents of the University of California
5 #ifndef IBIS_IRELIC_H
6 #define IBIS_IRELIC_H
7 #if defined(_WIN32) && defined(_MSC_VER)
15 #pragma warning(disable:4786) // some identifier longer than 256 characters
16 #endif
17 #include "index.h"
18 
21 class ibis::relic : public ibis::index {
22 public:
23  virtual ~relic() {clear();};
24  relic(const relic&);
25  relic(const ibis::column* c, const char* f = 0);
26  relic(const ibis::column* c, uint32_t popu, uint32_t ntpl=0);
27  relic(const ibis::column* c, uint32_t card, array_t<uint32_t>& ints);
28  relic(const ibis::column* c, ibis::fileManager::storage* st,
29  size_t start = 8);
30  relic(const ibis::column* c, uint32_t nb, double *keys, int64_t *offs);
31  relic(const ibis::column* c, uint32_t nb, double *keys, int64_t *offs,
32  uint32_t *bms);
33  relic(const ibis::column* c, uint32_t nb, double *keys, int64_t *offs,
34  void *bms, FastBitReadBitmaps rd);
35 
36  virtual index* dup() const;
37  virtual void print(std::ostream& out) const;
38  virtual void serialSizes(uint64_t&, uint64_t&, uint64_t&) const;
39  virtual int write(ibis::array_t<double> &,
40  ibis::array_t<int64_t> &,
41  ibis::array_t<uint32_t> &) const;
42  virtual int write(const char* dt) const;
43  virtual int read(const char* idxfile);
44  virtual int read(ibis::fileManager::storage* st);
45  virtual long append(const char* dt, const char* df, uint32_t nnew);
46 
47  virtual long select(const ibis::qContinuousRange&, void*) const;
48  virtual long select(const ibis::qContinuousRange&, void*,
49  ibis::bitvector&) const;
50 
51  using ibis::index::estimate;
52  using ibis::index::estimateCost;
53  virtual long evaluate(const ibis::qContinuousRange& expr,
54  ibis::bitvector& hits) const;
55  virtual long evaluate(const ibis::qDiscreteRange& expr,
56  ibis::bitvector& hits) const;
57 
58  virtual void estimate(const ibis::qContinuousRange& expr,
59  ibis::bitvector& lower,
60  ibis::bitvector& upper) const {
61  (void) evaluate(expr, lower);
62  upper.clear();
63  }
64  virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
67  virtual float undecidable(const ibis::qContinuousRange &,
68  ibis::bitvector &iffy) const {
69  iffy.clear();
70  return 0.0;
71  }
72  virtual void estimate(const ibis::qDiscreteRange& expr,
73  ibis::bitvector& lower,
74  ibis::bitvector& upper) const {
75  evaluate(expr, lower);
76  upper.clear();
77  }
78  virtual uint32_t estimate(const ibis::qDiscreteRange&) const;
79  virtual float undecidable(const ibis::qDiscreteRange&,
80  ibis::bitvector& iffy) const {
81  iffy.clear();
82  return 0.0;
83  }
84 
85  virtual double estimateCost(const ibis::qContinuousRange& expr) const;
86  virtual double estimateCost(const ibis::qDiscreteRange& expr) const;
87 
90  virtual void estimate(const ibis::relic& idx2,
91  const ibis::deprecatedJoin& expr,
92  const ibis::bitvector& mask,
93  ibis::bitvector64& lower,
94  ibis::bitvector64& upper) const;
95  virtual void estimate(const ibis::relic& idx2,
96  const ibis::deprecatedJoin& expr,
97  const ibis::bitvector& mask,
98  const ibis::qRange* const range1,
99  const ibis::qRange* const range2,
100  ibis::bitvector64& lower,
101  ibis::bitvector64& upper) const;
104  virtual int64_t estimate(const ibis::relic& idx2,
105  const ibis::deprecatedJoin& expr,
106  const ibis::bitvector& mask) const;
107  virtual int64_t estimate(const ibis::relic& idx2,
108  const ibis::deprecatedJoin& expr,
109  const ibis::bitvector& mask,
110  const ibis::qRange* const range1,
111  const ibis::qRange* const range2) const;
112 
113  virtual INDEX_TYPE type() const {return RELIC;}
114  virtual const char* name() const {return "basic";}
115  // bin boundaries and counts of each bin
116  virtual void binBoundaries(std::vector<double>& b) const;
117  virtual void binWeights(std::vector<uint32_t>& b) const;
118 
119  virtual long getCumulativeDistribution(std::vector<double>& bds,
120  std::vector<uint32_t>& cts) const;
121  virtual long getDistribution(std::vector<double>& bds,
122  std::vector<uint32_t>& cts) const;
123  virtual double getMin() const {return (vals.empty()?DBL_MAX:vals[0]);}
124  virtual double getMax() const {return (vals.empty()?-DBL_MAX:vals.back());}
125  virtual double getSum() const;
126 
127  virtual void speedTest(std::ostream& out) const;
128  long append(const ibis::relic& tail);
129  long append(const array_t<uint32_t>& ind);
130  array_t<uint32_t>* keys(const ibis::bitvector& mask) const;
131 
133  template <typename T>
134  struct valpos {
136  T val;
138  bitvector::indexSet ind;
142  bitvector::word_t j;
143 
145  valpos<T>() : val(0), j(0) {}
147  valpos<T>(const T v, const bitvector& b)
148  : val(v), ind(b.firstIndexSet()), j(0) {
149  if (ind.nIndices() > 0 && ind.isRange())
150  j = *(ind.indices());
151  }
152 
154  bitvector::word_t position() const {
155  if (ind.isRange())
156  return j;
157  else
158  return ind.indices()[j];
159  }
160 
162  void next() {
163  ++ j;
164  if (ind.isRange()) {
165  if (j >= ind.indices()[1]) {
166  ++ ind;
167  if (ind.nIndices() > 0 && ind.isRange())
168  j = ind.indices()[0];
169  else
170  j = 0;
171  }
172  }
173  else if (j >= ind.nIndices()) {
174  ++ ind;
175  if (ind.nIndices() > 0 && ind.isRange())
176  j = ind.indices()[0];
177  else
178  j = 0;
179  }
180  }
181  }; // valpos
182 
184  template<typename T>
185  struct comparevalpos {
186  bool operator()(const valpos<T>* x, const valpos<T>* y) {
187  return (x->position() > y->position());
188  }
189  }; // comparevalpos
190 
191  void construct(const char* f = 0);
192  template <typename E>
193  void construct(const array_t<E>& arr);
194 
195  void locate(const ibis::qContinuousRange& expr,
196  uint32_t& hit0, uint32_t& hit1) const;
197 
198 protected:
199  // protected member variables
200  array_t<double> vals;
201 
202  // protected member functions
203  int write32(int fdes) const;
204  int write64(int fdes) const;
205  uint32_t locate(const double& val) const;
206 
207  // a dummy constructor
208  relic() : ibis::index() {}
209  // free current resources, re-initialized all member variables
210  virtual void clear();
211  virtual double computeSum() const;
212  virtual size_t getSerialSize() const throw();
213 
214  long mergeValues(uint32_t, uint32_t, void*) const;
215  template <typename T> static long
216  mergeValuesT(const array_t<T>& vs,
217  const array_t<const bitvector*>& ps,
218  array_t<T>& res);
219 
220  template <typename T> struct mappedValues;
221 
222 private:
223  // private member functions
224  int64_t equiJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
225  ibis::bitvector64& hits) const;
226  int64_t deprecatedJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
227  const double& delta, ibis::bitvector64& hits) const;
228  int64_t compJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
229  const ibis::math::term& delta,
230  ibis::bitvector64& hits) const;
231 
232  int64_t equiJoin(const ibis::relic& idx2,
233  const ibis::bitvector& mask) const;
234  int64_t deprecatedJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
235  const double& delta) const;
236  int64_t compJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
237  const ibis::math::term& delta) const;
238 
239  int64_t equiJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
240  const ibis::qRange* const range1,
241  const ibis::qRange* const range2,
242  ibis::bitvector64& hits) const;
243  int64_t deprecatedJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
244  const ibis::qRange* const range1,
245  const ibis::qRange* const range2,
246  const double& delta, ibis::bitvector64& hits) const;
249  int64_t compJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
250  const ibis::qRange* const range1,
251  const ibis::qRange* const range2,
252  const ibis::math::term& delta,
253  ibis::bitvector64& hits) const {
254  return compJoin(idx2, mask, delta, hits);
255  }
256 
257  int64_t equiJoin(const ibis::relic& idx2,
258  const ibis::bitvector& mask,
259  const ibis::qRange* const range1,
260  const ibis::qRange* const range2) const;
261  int64_t deprecatedJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
262  const ibis::qRange* const range1,
263  const ibis::qRange* const range2,
264  const double& delta) const;
267  int64_t compJoin(const ibis::relic& idx2, const ibis::bitvector& mask,
268  const ibis::qRange* const range1,
269  const ibis::qRange* const range2,
270  const ibis::math::term& delta) const {
271  return compJoin(idx2, mask, delta);
272  }
273 
274  relic& operator=(const relic&);
275 }; // ibis::relic
276 
283 class ibis::skive : public ibis::relic {
284 public:
285  virtual ~skive();
286  skive(const ibis::column* c = 0, const char* f = 0);
287  skive(const ibis::column* c, ibis::fileManager::storage* st,
288  size_t start = 8);
289 
290  virtual int write(const char* dt) const;
291  virtual void print(std::ostream& out) const;
292  virtual int read(const char* idxfile);
293  virtual int read(ibis::fileManager::storage* st);
294 
295  virtual long append(const char* dt, const char* df, uint32_t nnew);
296 
297  virtual long select(const ibis::qContinuousRange&, void*) const {
298  return -1;}
299  virtual long select(const ibis::qContinuousRange&, void*,
300  ibis::bitvector&) const {
301  return -1;}
302 
303  using ibis::relic::estimate;
304  using ibis::relic::estimateCost;
305  virtual long evaluate(const ibis::qContinuousRange& expr,
306  ibis::bitvector& hits) const;
307  virtual long evaluate(const ibis::qDiscreteRange& expr,
308  ibis::bitvector& hits) const;
309 
310  virtual void estimate(const ibis::qContinuousRange& expr,
311  ibis::bitvector& lower,
312  ibis::bitvector& upper) const;
313  virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
314  virtual INDEX_TYPE type() const {return SKIVE;}
315  virtual const char* name() const {return "binary-encoded";}
316  // number of records in each bin
317  virtual void binWeights(std::vector<uint32_t>& b) const;
318  virtual double getSum() const;
319 
320  virtual void speedTest(std::ostream& out) const;
321  virtual double estimateCost(const ibis::qContinuousRange&) const {
322  double ret;
323  if (offset64.size() > bits.size())
324  ret = offset64.back();
325  else if (offset32.size() > bits.size())
326  ret = offset32.back();
327  else
328  ret = 0.0;
329  return ret;
330  }
331  virtual double estimateCost(const ibis::qDiscreteRange& expr) const {
332  double ret;
333  if (offset64.size() > bits.size())
334  ret = offset64.back();
335  else if (offset32.size() > bits.size())
336  ret = offset32.back();
337  else
338  ret = 0.0;
339  return ret;
340  }
341 
342 protected:
343  virtual void clear();
344  virtual size_t getSerialSize() const throw();
345 
346  array_t<uint32_t> cnts; // the counts for each distinct value
347 
348  int write32(int fdes) const;
349  int write64(int fdes) const;
350  void evalGE(ibis::bitvector& res, uint32_t b) const;
351  void evalEQ(ibis::bitvector& res, uint32_t b) const;
352 
353 private:
354  skive(const skive&);
355  skive& operator=(const skive&);
356 
357  // private member functions
358  void construct1(const char* f = 0); // uses more temporary storage
359  void construct2(const char* f = 0); // passes through data twice
360  void setBit(const uint32_t i, const double val);
361 }; // ibis::skive
362 
365 class ibis::slice : public ibis::skive {
366 public:
367  virtual ~slice();
368  slice(const ibis::column* c = 0, const char* f = 0);
369  slice(const ibis::column* c, ibis::fileManager::storage* st,
370  size_t start = 8);
371  virtual INDEX_TYPE type() const {return SLICE;}
372  virtual const char* name() const {return "bit-slice";}
373 
374  virtual int write(const char* dt) const;
375  virtual void print(std::ostream& out) const;
376 
377  virtual long append(const char* dt, const char* df, uint32_t nnew);
378 
379  static bool isSuitable(const column&, const char*);
380 
381 private:
382  slice(const slice&);
383  slice& operator=(const slice&);
384 
385  // private member functions
386  int construct(const char* f = 0); // passes through data twice
387  template <typename T> int constructT(const char*);
388 }; // ibis::slice
389 
392 class ibis::fade : public ibis::relic {
393 public:
394  virtual ~fade() {clear();};
395  fade(const ibis::column* c = 0, const char* f = 0,
396  const uint32_t nbase = 2);
397  fade(const ibis::column* c, ibis::fileManager::storage* st,
398  size_t start = 8);
399 
400  virtual int write(const char* dt) const;
401  virtual void print(std::ostream& out) const;
402  virtual int read(const char* idxfile);
403  virtual int read(ibis::fileManager::storage* st);
404 
405  virtual long append(const char* dt, const char* df, uint32_t nnew);
406 
407  virtual long select(const ibis::qContinuousRange&, void*) const {
408  return -1;}
409  virtual long select(const ibis::qContinuousRange&, void*,
410  ibis::bitvector&) const {
411  return -1;}
412 
413  using ibis::relic::estimate;
414  using ibis::relic::estimateCost;
415  virtual long evaluate(const ibis::qContinuousRange& expr,
416  ibis::bitvector& hits) const;
417  virtual long evaluate(const ibis::qDiscreteRange& expr,
418  ibis::bitvector& hits) const;
419 
420  virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
421  virtual INDEX_TYPE type() const {return FADE;}
422  virtual const char* name() const {return "multi-level range";}
423 
424  virtual void speedTest(std::ostream& out) const;
425  // number of records in each bin
426  virtual void binWeights(std::vector<uint32_t>& b) const;
427  virtual double getSum() const;
428  virtual double estimateCost(const ibis::qContinuousRange& expr) const;
429  //virtual double estimateCost(const ibis::qDiscreteRange& expr) const;
430 
431 protected:
432  // protected member variables
433  array_t<uint32_t> cnts; // the counts for each distinct value
434  array_t<uint32_t> bases;// the values of the bases used
435 
436  // protected member functions to be used by derived classes
437  int write32(int fdes) const;
438  int write64(int fdes) const;
439  virtual void clear();
440  virtual size_t getSerialSize() const throw();
441 
442 private:
443  // private member functions
444  void setBit(const uint32_t i, const double val);
445  void construct1(const char* f = 0, const uint32_t nbase = 2);
446  void construct2(const char* f = 0, const uint32_t nbase = 2);
447 
448  void evalEQ(ibis::bitvector& res, uint32_t b) const;
449  void evalLE(ibis::bitvector& res, uint32_t b) const;
450  void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
451 
452  fade(const fade&);
453  fade& operator=(const fade&);
454 }; // ibis::fade
455 
458 class ibis::sbiad : public ibis::fade {
459 public:
460  virtual ~sbiad() {clear();};
461  sbiad(const ibis::column* c = 0, const char* f = 0,
462  const uint32_t nbase = 2);
463  sbiad(const ibis::column* c, ibis::fileManager::storage* st,
464  size_t start = 8);
465 
466  virtual int write(const char* dt) const;
467  virtual void print(std::ostream& out) const;
468  virtual long append(const char* dt, const char* df, uint32_t nnew);
469 
470  virtual long evaluate(const ibis::qContinuousRange& expr,
471  ibis::bitvector& hits) const;
472  virtual long evaluate(const ibis::qDiscreteRange& expr,
473  ibis::bitvector& hits) const;
474 
475  virtual INDEX_TYPE type() const {return SBIAD;}
476  virtual const char* name() const {return "multi-level interval";}
477 
478  virtual void speedTest(std::ostream& out) const;
479  //virtual double estimateCost(const ibis::qContinuousRange& expr) const;
480  //virtual double estimateCost(const ibis::qDiscreteRange& expr) const;
481 
482 private:
483  // private member functions
484  void setBit(const uint32_t i, const double val);
485  void construct1(const char* f = 0, const uint32_t nbase = 2);
486  void construct2(const char* f = 0, const uint32_t nbase = 2);
487 
488  void evalEQ(ibis::bitvector& res, uint32_t b) const;
489  void evalLE(ibis::bitvector& res, uint32_t b) const;
490  void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
491 
492  sbiad(const sbiad&);
493  sbiad& operator=(const sbiad&);
494 }; // ibis::sbiad
495 
497 class ibis::sapid : public ibis::fade {
498 public:
499  virtual ~sapid() {clear();};
500  sapid(const ibis::column* c = 0, const char* f = 0,
501  const uint32_t nbase = 2);
502  sapid(const ibis::column* c, ibis::fileManager::storage* st,
503  size_t start = 8);
504 
505  virtual int write(const char* dt) const;
506  virtual void print(std::ostream& out) const;
507  virtual long append(const char* dt, const char* df, uint32_t nnew);
508 
509  virtual long evaluate(const ibis::qContinuousRange& expr,
510  ibis::bitvector& hits) const;
511  virtual long evaluate(const ibis::qDiscreteRange& expr,
512  ibis::bitvector& hits) const;
513 
514  virtual INDEX_TYPE type() const {return SAPID;}
515  virtual const char* name() const {return "multi-level equality";}
516 
517  virtual void speedTest(std::ostream& out) const;
518  //virtual double estimateCost(const ibis::qContinuousRange& expr) const;
519  //virtual double estimateCost(const ibis::qDiscreteRange& expr) const;
520 
521 private:
522  // private member functions
523  void setBit(const uint32_t i, const double val);
524  void construct1(const char* f = 0, const uint32_t nbase = 2);
525  void construct2(const char* f = 0, const uint32_t nbase = 2);
526 
527  void addBits_(uint32_t ib, uint32_t ie, ibis::bitvector& res) const;
528  void evalEQ(ibis::bitvector& res, uint32_t b) const;
529  void evalLE(ibis::bitvector& res, uint32_t b) const;
530  void evalLL(ibis::bitvector& res, uint32_t b0, uint32_t b1) const;
531 
532  sapid(const sapid&);
533  sapid& operator=(const sapid&);
534 }; // ibis::sapid
535 
540 class ibis::fuzz : public ibis::relic {
541 public:
542  virtual ~fuzz() {clear();};
543  fuzz(const ibis::column* c = 0, const char* f = 0);
544  fuzz(const ibis::column* c, ibis::fileManager::storage* st,
545  size_t start = 8);
546 
547  virtual int write(const char* dt) const;
548  virtual void print(std::ostream& out) const;
549  virtual int read(const char* idxfile);
550  virtual int read(ibis::fileManager::storage* st);
551 
552  virtual long append(const char* dt, const char* df, uint32_t nnew);
553 
554  using ibis::relic::evaluate;
555  using ibis::relic::estimate;
556  using ibis::relic::estimateCost;
557  virtual long evaluate(const ibis::qContinuousRange& expr,
558  ibis::bitvector& hits) const;
559  virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
560  virtual double estimateCost(const ibis::qContinuousRange& expr) const;
561 
562  virtual INDEX_TYPE type() const {return FUZZ;}
563  virtual const char* name() const {return "interval-equality";}
564 
565 protected:
566  virtual void clear();
567  virtual size_t getSerialSize() const throw();
568 
569 private:
573  mutable array_t<bitvector*> cbits;
574  array_t<uint32_t> cbounds;
575  mutable array_t<int32_t> coffset32;
576  mutable array_t<int64_t> coffset64;
577 
578  void coarsen(); // given fine level, add coarse level
579  void activateCoarse() const; // activate all coarse level bitmaps
580  void activateCoarse(uint32_t i) const; // activate one bitmap
581  void activateCoarse(uint32_t i, uint32_t j) const;
582 
583  int writeCoarse32(int fdes) const;
584  int writeCoarse64(int fdes) const;
585  int readCoarse(const char *fn);
586  void clearCoarse();
587 
589  long coarseEstimate(uint32_t lo, uint32_t hi) const;
591  long coarseEvaluate(uint32_t lo, uint32_t hi, ibis::bitvector& res) const;
592 
593  fuzz(const fuzz&);
594  fuzz& operator=(const fuzz&);
595 }; // ibis::fuzz
596 
601 class ibis::bylt : public ibis::relic {
602 public:
603  virtual ~bylt() {clear();};
604  bylt(const ibis::column* c = 0, const char* f = 0);
605  bylt(const ibis::column* c, ibis::fileManager::storage* st,
606  size_t start = 8);
607 
608  virtual int write(const char* dt) const;
609  virtual void print(std::ostream& out) const;
610  virtual int read(const char* idxfile);
611  virtual int read(ibis::fileManager::storage* st);
612 
613  virtual long append(const char* dt, const char* df, uint32_t nnew);
614 
615  using ibis::relic::evaluate;
616  using ibis::relic::estimate;
617  using ibis::relic::estimateCost;
618  virtual long evaluate(const ibis::qContinuousRange& expr,
619  ibis::bitvector& hits) const;
620  virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
621  virtual double estimateCost(const ibis::qContinuousRange& expr) const;
622 
623  virtual INDEX_TYPE type() const {return BYLT;}
624  virtual const char* name() const {return "range-equality";}
625 
626 protected:
627  virtual void clear();
628  virtual size_t getSerialSize() const throw();
629 
630 private:
631  // the fine level is stored in ibis::relic, the parent class, only the
632  // coarse bins are stored here. The coarse bins use integer bin
633  // boundaries; these integers are indices to the array vals and bits.
634  mutable array_t<bitvector*> cbits;
635  array_t<uint32_t> cbounds;
636  mutable array_t<int32_t> coffset32;
637  mutable array_t<int64_t> coffset64;
638 
639  void coarsen(); // given fine level, add coarse level
640  void activateCoarse() const; // activate all coarse level bitmaps
641  void activateCoarse(uint32_t i) const; // activate one bitmap
642  void activateCoarse(uint32_t i, uint32_t j) const;
643 
644  int writeCoarse32(int fdes) const;
645  int writeCoarse64(int fdes) const;
646  int readCoarse(const char *fn);
647 
648  bylt(const bylt&);
649  bylt& operator=(const bylt&);
650 }; // ibis::bylt
651 
656 class ibis::zona : public ibis::relic {
657 public:
658  virtual ~zona() {clear();};
659  zona(const ibis::column* c = 0, const char* f = 0);
660  zona(const ibis::column* c, ibis::fileManager::storage* st,
661  size_t start = 8);
662 
663  virtual int write(const char* dt) const;
664  virtual void print(std::ostream& out) const;
665  virtual int read(const char* idxfile);
666  virtual int read(ibis::fileManager::storage* st);
667 
668  virtual long append(const char* dt, const char* df, uint32_t nnew);
669 
670  using ibis::relic::evaluate;
671  using ibis::relic::estimate;
672  using ibis::relic::estimateCost;
673  virtual long evaluate(const ibis::qContinuousRange& expr,
674  ibis::bitvector& hits) const;
675  virtual uint32_t estimate(const ibis::qContinuousRange& expr) const;
676  virtual double estimateCost(const ibis::qContinuousRange& expr) const;
677 
678  virtual INDEX_TYPE type() const {return ZONA;}
679  virtual const char* name() const {return "equality-equality";}
680 
681 protected:
682  virtual void clear();
683  virtual size_t getSerialSize() const throw();
684 
685 private:
686  // the fine level is stored in ibis::relic, the parent class, only the
687  // coarse bins are stored here. The coarse bins use integer bin
688  // boundaries; these integers are indices to the array vals and bits.
689  mutable array_t<bitvector*> cbits;
690  array_t<uint32_t> cbounds;
691  mutable array_t<int32_t> coffset32;
692  mutable array_t<int64_t> coffset64;
693 
694  void coarsen(); // given fine level, add coarse level
695  void activateCoarse() const; // activate all coarse level bitmaps
696  void activateCoarse(uint32_t i) const; // activate one bitmap
697  void activateCoarse(uint32_t i, uint32_t j) const;
698 
699  int writeCoarse32(int fdes) const;
700  int writeCoarse64(int fdes) const;
701  int readCoarse(const char *fn);
702 
703  zona(const zona&);
704  zona& operator=(const zona&);
705 }; // ibis::zona
706 
709 template <typename T>
710 struct ibis::relic::mappedValues {
711 }; // ibis::relic::mappedValues
712 #endif // IBIS_IRELIC_H
ibis::slice::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:371
ibis::index::BYLT
ibis::bylt, unbinned range-equality encoding.
Definition: index.h:140
ibis::sapid::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:515
ibis::skive::getSum
virtual double getSum() const
Compute the sum of all values of the column indexed.
Definition: iskive.cpp:1466
ibis::sapid
The multicomponent equality encoded index.
Definition: irelic.h:497
ibis::qRange
A class to represent simple range conditions.
Definition: qExpr.h:207
ibis::zona::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:679
ibis::relic::valpos
A single value with known positions.
Definition: irelic.h:134
ibis::fade::select
virtual long select(const ibis::qContinuousRange &, void *) const
Evaluate the range condition and select values.
Definition: irelic.h:407
ibis::bitvector::indexSet::nIndices
word_t nIndices() const
Number of indices.
Definition: bitvector.h:508
ibis::skive::binWeights
virtual void binWeights(std::vector< uint32_t > &b) const
Return the exact count for each distinct value.
Definition: iskive.cpp:1446
ibis::relic::select
virtual long select(const ibis::qContinuousRange &, void *) const
Evaluate the range condition and select values.
Definition: irelic.cpp:1811
ibis::relic::read
virtual int read(const char *idxfile)
Read the index contained from the speficied location.
Definition: irelic.cpp:690
ibis::skive::estimateCost
virtual double estimateCost(const ibis::qContinuousRange &) const
Estimate the cost of resolving the continuous range expression.
Definition: irelic.h:321
ibis::relic::dup
virtual index * dup() const
Duplicate the content of an index object.
Definition: irelic.cpp:348
ibis::array_t::size
size_t size() const
Definition: array_t.h:69
index.h
Definition of the common functions of an index.
ibis::relic::write32
int write32(int fdes) const
Write the content to a file already opened.
Definition: irelic.cpp:459
ibis::relic
The basic bitmap index.
Definition: irelic.h:21
ibis::qContinuousRange
Simple range condition.
Definition: qExpr.h:252
ibis::fileManager::storage
The storage class treats all memory as char*.
Definition: fileManager.h:237
ibis::index::bits
array_t< ibis::bitvector * > bits
A list of bitvectors.
Definition: index.h:414
ibis::relic::computeSum
virtual double computeSum() const
Compute the sum of all values of the column indexed.
Definition: irelic.cpp:2007
ibis::relic::comparevalpos
The comparator used to build a min-heap based on positions.
Definition: irelic.h:185
ibis::relic::append
virtual long append(const char *dt, const char *df, uint32_t nnew)
Create an index based on data in df and append the result to the index in dt.
Definition: irelic.cpp:1193
ibis::util::coarsen
double coarsen(const double in, unsigned prec=2)
Reduce the decimal precision of the incoming floating-point value to specified precision.
Definition: util.h:1633
ibis::relic::getCumulativeDistribution
virtual long getCumulativeDistribution(std::vector< double > &bds, std::vector< uint32_t > &cts) const
Compute a cumulative distribition.
Definition: irelic.cpp:2017
ibis
The current implementation of FastBit is code named IBIS; most data structures and functions are in t...
Definition: bord.h:16
ibis::slice::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:372
ibis::index::estimate
virtual void estimate(const ibis::qContinuousRange &, ibis::bitvector &lower, ibis::bitvector &upper) const
Computes an approximation of hits as a pair of lower and upper bounds.
Definition: index.h:191
ibis::column
The class to represent a column of a data partition.
Definition: column.h:65
ibis::bitvector::indexSet::indices
const word_t * indices() const
Pointer to the indices.
Definition: bitvector.h:506
ibis::fuzz
The precise version of two-level interval-equality index.
Definition: irelic.h:540
ibis::bitvector64
A data structure to represent a sequence of bits.
Definition: bitvector64.h:54
ibis::relic::speedTest
virtual void speedTest(std::ostream &out) const
Time some logical operations and print out their speed.
Definition: irelic.cpp:940
ibis::relic::print
virtual void print(std::ostream &out) const
The printing function.
Definition: irelic.cpp:1050
ibis::relic::getMax
virtual double getMax() const
The maximum value recorded in the index.
Definition: irelic.h:124
ibis::index::SAPID
ibis::sapid, multicomponent equality encoding (unbinned).
Definition: index.h:115
ibis::skive::write32
int write32(int fdes) const
Write the content to a file opened by the caller.
Definition: iskive.cpp:195
ibis::relic::valpos::position
bitvector::word_t position() const
Current position (RID).
Definition: irelic.h:154
ibis::index::SLICE
ibis::slice, bit-sliced index.
Definition: index.h:148
ibis::relic::serialSizes
virtual void serialSizes(uint64_t &, uint64_t &, uint64_t &) const
Compute the size of arrays that would be generated by the serializatioin function (write)...
Definition: irelic.cpp:669
ibis::skive
The binary encoded index with recoding of keyvalues.
Definition: irelic.h:283
ibis::relic::evaluate
virtual long evaluate(const ibis::qContinuousRange &expr, ibis::bitvector &hits) const
Compute the hits as a bitvector.
Definition: irelic.cpp:1827
ibis::relic::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:113
ibis::relic::keys
array_t< uint32_t > * keys(const ibis::bitvector &mask) const
Convert the bitvector mask into bin numbers.
Definition: irelic.cpp:1106
ibis::skive::clear
virtual void clear()
Free the memory hold by this object.
Definition: iskive.cpp:525
ibis::relic::mappedValues
A struct to hold a set of values and their positions.
Definition: irelic.h:220
ibis::relic::undecidable
virtual float undecidable(const ibis::qContinuousRange &, ibis::bitvector &iffy) const
This class and its derived classes should produce exact answers, therefore no undecidable rows...
Definition: irelic.h:67
ibis::relic::estimate
virtual void estimate(const ibis::qContinuousRange &expr, ibis::bitvector &lower, ibis::bitvector &upper) const
Computes an approximation of hits as a pair of lower and upper bounds.
Definition: irelic.h:58
ibis::index::ZONA
ibis::zona, unbinned equality-equality encoding.
Definition: index.h:144
ibis::skive::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:314
ibis::index
The base index class.
Definition: index.h:82
ibis::skive::evalEQ
void evalEQ(ibis::bitvector &res, uint32_t b) const
Compute the bitvector that is the answer for the query x = b.
Definition: iskive.cpp:1337
ibis::bylt::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:624
ibis::sbiad::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:476
ibis::relic::locate
void locate(const ibis::qContinuousRange &expr, uint32_t &hit0, uint32_t &hit1) const
Locate the bitmaps covered by the range expression.
Definition: irelic.cpp:1416
ibis::fade::select
virtual long select(const ibis::qContinuousRange &, void *, ibis::bitvector &) const
Evaluate the range condition, select values, and record the positions.
Definition: irelic.h:409
ibis::relic::valpos::next
void next()
Move to the next row.
Definition: irelic.h:162
ibis::index::INDEX_TYPE
INDEX_TYPE
The integer values of this enum type are used in the index files to differentiate the indexes...
Definition: index.h:86
ibis::skive::select
virtual long select(const ibis::qContinuousRange &, void *, ibis::bitvector &) const
Evaluate the range condition, select values, and record the positions.
Definition: irelic.h:299
ibis::relic::estimateCost
virtual double estimateCost(const ibis::qContinuousRange &expr) const
Estimate the cost of resolving the continuous range expression.
Definition: irelic.cpp:1858
ibis::index::estimateCost
virtual double estimateCost(const ibis::qContinuousRange &) const
Estimate the cost of evaluating a range condition.
Definition: index.h:263
ibis::relic::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:114
ibis::relic::getSum
virtual double getSum() const
Compute the sum of all values of the column indexed.
Definition: irelic.cpp:1985
ibis::relic::binBoundaries
virtual void binBoundaries(std::vector< double > &b) const
Return all distinct values as the bin boundaries.
Definition: irelic.cpp:1970
ibis::array_t< uint32_t >
ibis::fuzz::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:562
ibis::relic::getMin
virtual double getMin() const
The minimum value recorded in the index.
Definition: irelic.h:123
ibis::bylt
The precise version of the two-level range-equality index.
Definition: irelic.h:601
ibis::fade
The multicomponent range-encoded index.
Definition: irelic.h:392
ibis::skive::skive
skive(const ibis::column *c=0, const char *f=0)
Construct a bitmap index from current data.
Definition: iskive.cpp:23
ibis::relic::clear
virtual void clear()
Clear the existing content.
Definition: irelic.cpp:819
ibis::sbiad
The multicomponent interval encoded index.
Definition: irelic.h:458
ibis::index::offset64
array_t< int64_t > offset64
Starting positions of the bitvectors.
Definition: index.h:412
ibis::skive::getSerialSize
virtual size_t getSerialSize() const
Estimate the size of the index in a file.
Definition: iskive.cpp:1484
ibis::relic::valpos::val
T val
The value.
Definition: irelic.h:136
ibis::relic::getSerialSize
virtual size_t getSerialSize() const
Compute the size of the index in a file.
Definition: irelic.cpp:3158
ibis::fuzz::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:563
ibis::skive::read
virtual int read(const char *idxfile)
Read the index contained in the file f.
Definition: iskive.cpp:413
ibis::skive::evalGE
void evalGE(ibis::bitvector &res, uint32_t b) const
Compute the bitvector that is the answer for the query x >= b.
Definition: iskive.cpp:1296
ibis::relic::mergeValuesT
static long mergeValuesT(const array_t< T > &vs, const array_t< const bitvector * > &ps, array_t< T > &res)
A template function to merge list of values and a list of positions.
Definition: irelic.cpp:3249
ibis::relic::valpos::ind
bitvector::indexSet ind
The index set representing the positions with the given value.
Definition: irelic.h:138
ibis::bitvector::indexSet
The indexSet stores positions of bits that are one.
Definition: bitvector.h:421
ibis::bitvector::indexSet::isRange
bool isRange() const
Is the index set a consecutive range?
Definition: bitvector.h:504
ibis::slice
The bit-sliced index.
Definition: irelic.h:365
ibis::relic::estimate
virtual void estimate(const ibis::qDiscreteRange &expr, ibis::bitvector &lower, ibis::bitvector &upper) const
Estimate the hits for discrete ranges, i.e., those translated from 'a IN (x, y, ..)'.
Definition: irelic.h:72
ibis::index::SKIVE
ibis::skive, binary encoding with recoding of key values.
Definition: index.h:109
ibis::relic::write64
int write64(int fdes) const
Write the content to a file already opened.
Definition: irelic.cpp:552
ibis::relic::mergeValues
long mergeValues(uint32_t, uint32_t, void *) const
Merge the values in different bitmaps into a single list.
Definition: irelic.cpp:3170
ibis::skive::evaluate
virtual long evaluate(const ibis::qContinuousRange &expr, ibis::bitvector &hits) const
Compute the hits as a bitvector.
Definition: iskive.cpp:1359
ibis::math::term
The abstract base class for arithmetic terms.
Definition: qExpr.h:728
ibis::skive::speedTest
virtual void speedTest(std::ostream &out) const
Time some logical operations and print out their speed.
Definition: iskive.cpp:1232
ibis::index::offset32
array_t< int32_t > offset32
Starting positions of the bitvectors.
Definition: index.h:408
ibis::index::SBIAD
ibis::sbiad, multicomponent interval encoding (unbinned).
Definition: index.h:113
ibis::index::FADE
ibis::fade, multicomponent range encoding (unbinned).
Definition: index.h:111
ibis::index::RELIC
ibis::relic, the basic bitmap index.
Definition: index.h:105
ibis::relic::binWeights
virtual void binWeights(std::vector< uint32_t > &b) const
Return the exact count for each distinct value.
Definition: irelic.cpp:1977
ibis::bitvector
A data structure to represent a sequence of bits.
Definition: bitvector.h:62
ibis::relic::write
virtual int write(ibis::array_t< double > &, ibis::array_t< int64_t > &, ibis::array_t< uint32_t > &) const
Save index to three arrays. Serialize the index in memory.
Definition: irelic.cpp:644
ibis::fade::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:421
ibis::skive::estimate
virtual void estimate(const ibis::qContinuousRange &expr, ibis::bitvector &lower, ibis::bitvector &upper) const
Computes an approximation of hits as a pair of lower and upper bounds.
Definition: iskive.cpp:1411
ibis::zona
The precise version of the two-level equality-equality index.
Definition: irelic.h:656
ibis::bylt::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:623
ibis::skive::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:315
FastBitReadBitmaps
int(* FastBitReadBitmaps)(void *context, uint64_t start, uint64_t count, uint32_t *data)
A function prototype for delayed index reconstruction.
Definition: const.h:341
ibis::skive::write64
int write64(int fdes) const
Write the content to a file opened by the caller.
Definition: iskive.cpp:304
ibis::skive::write
virtual int write(const char *dt) const
Write the content of the index to the specified location.
Definition: iskive.cpp:109
ibis::skive::print
virtual void print(std::ostream &out) const
The printing function.
Definition: iskive.cpp:1263
ibis::bitvector::clear
void clear()
Remove the existing content of a bitvector.
Definition: bitvector.cpp:243
ibis::qDiscreteRange
A discrete range expression.
Definition: qExpr.h:337
ibis::relic::valpos::j
bitvector::word_t j
The current index value inside the index set.
Definition: irelic.h:142
ibis::zona::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:678
ibis::relic::getDistribution
virtual long getDistribution(std::vector< double > &bds, std::vector< uint32_t > &cts) const
Compute a histogram.
Definition: irelic.cpp:2075
ibis::sbiad::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:475
ibis::index::FUZZ
ibis::fuzz, unbinned interval-equality encoding.
Definition: index.h:142
ibis::skive::append
virtual long append(const char *dt, const char *df, uint32_t nnew)
Create index based data in dt. Have to start from data directly.
Definition: iskive.cpp:1288
ibis::sapid::type
virtual INDEX_TYPE type() const
Returns an index type identifier.
Definition: irelic.h:514
ibis::skive::estimateCost
virtual double estimateCost(const ibis::qDiscreteRange &expr) const
Estimate the cost of resolving the discrete range expression.
Definition: irelic.h:331
ibis::skive::select
virtual long select(const ibis::qContinuousRange &, void *) const
Evaluate the range condition and select values.
Definition: irelic.h:297
ibis::relic::construct
void construct(const char *f=0)
Construct a new index in memory.
Definition: irelic.cpp:831
ibis::deprecatedJoin
A join is defined by two names and a numerical expression.
Definition: qExpr.h:1240
ibis::fade::name
virtual const char * name() const
Returns the name of the index, similar to the function type, but returns a string instead...
Definition: irelic.h:422

Make It A Bit Faster
Contact us
Disclaimers
FastBit source code
FastBit mailing list archive