FastBit: query.h Source File

00001 //File: $Id$
00002 // Author: John Wu <John.Wu at ACM.org>
00003 //         Lawrence Berkeley National Laboratory
00004 // Copyright 2000-2008 the Regents of the University of California
00005 #ifndef IBIS_QUERY_H
00006 #define IBIS_QUERY_H
00010 #include "part.h"       // class part
00011 
00046 class FASTBIT_CXX_DLLSPEC ibis::query {
00047 public:
00048     enum QUERY_STATE {
00049         UNINITIALIZED,  //< The query object is currently empty.
00050         SET_COMPONENTS, //< The query object has a select clause.
00051         SET_RIDS,       //< The query object contains a list of RIDs.
00052         SET_PREDICATE,  //< The query object has a where clause.
00053         SPECIFIED,      //< SET_COMPONENTS & (SET_RIDS | SET_PREDICATE).
00054         QUICK_ESTIMATE, //< A upper and a lower bound are computed.
00055         FULL_EVALUATE,  //< The exact hits are computed.
00056         BUNDLES_TRUNCATED,      //< Only top-K results are stored.
00057         HITS_TRUNCATED  //< The hit vector has been updated to match bundles.
00058     };
00059 
00060     virtual ~query();
00064     query(const char* dir, const ibis::partList& tl);
00066     query(const char* uid=0, const part* et=0, const char* pref=0);
00067 
00069     const char* id() const {return myID;};      
00070     const char* dir() const {return myDir;}     
00071     const char* userName() const {return user;} 
00072 
00073     time_t timestamp() const {return dstime;}
00075     const part* partition() const {return table0;}
00077     const selected& components() const {return comps;};
00078 
00081     int setRIDs(const RIDSet& set);
00083     int setWhereClause(const char *str);
00085     int setWhereClause(const std::vector<const char*>& names,
00086                        const std::vector<double>& lbounds,
00087                        const std::vector<double>& rbounds);
00089     int setWhereClause(const ibis::qExpr* qexp);
00098     virtual int setSelectClause(const char *str);
00101     int setTable(const ibis::part* tbl);
00103     virtual const char* getWhereClause() const {return condition;}
00105     virtual const char* getSelectClause() const {return *comps;}
00106 
00110     void expandQuery();
00114     void contractQuery();
00115 
00117     const RIDSet* getUserRIDs() const {return rids_in;}
00118 
00129     std::string removeComplexConditions();
00130 
00131     // Functions to perform estimation.
00132 
00139     int estimate();
00141     long getMinNumHits() const;
00143     long getMaxNumHits() const;
00144 
00145     // Functions related to full evaluation.
00146 
00163     int evaluate(const bool evalSelect=false);
00166     const ibis::bitvector* getHitVector() const {return hits;}
00168     long getNumHits() const;
00171     long countHits() const;
00175     RIDSet* getRIDs() const;
00179     RIDSet* getRIDs(const ibis::bitvector& mask) const;
00181     const RIDSet* getRIDsInBundle(const uint32_t bid) const;
00182 
00188     int orderby(const char *names, int direction) const;
00189 
00201     long int limit(const char *names, int direction, uint32_t keep,
00202                    bool updateHits = true);
00203 
00218     array_t<int32_t>* getQualifiedInts(const char* column_name);
00219     array_t<uint32_t>* getQualifiedUInts(const char* column_name);
00220     array_t<float>* getQualifiedFloats(const char* column_name);
00221     array_t<double>* getQualifiedDoubles(const char* column_name);
00222 
00229     void printSelected(std::ostream& out) const;
00233     void printSelectedWithRID(std::ostream& out) const;
00234 
00240     long sequentialScan(ibis::bitvector& bv) const;
00241 
00245     long getExpandedHits(ibis::bitvector&) const;
00246 
00247     // used by ibis::bundle
00248     RIDSet* readRIDs() const;
00249     void writeRIDs(const RIDSet* rids) const;
00250 
00253     void logMessage(const char* event, const char* fmt, ...) const;
00254 
00255     // Functions for cleaning up, retrieving query states
00256     // and error messages.
00257 
00260     void clear();
00262     QUERY_STATE getState() const;
00264     const char* getLastError() const {return lastError;}
00266     void clearErrorMessage() const {*lastError=0;}
00267 
00270     static bool isValidToken(const char* tok);
00272     // *** the value 16 is hard coded in functions newToken and ***
00273     // *** isValidToken ***
00274     static unsigned tokenLength() {return 16;}
00275 
00277     static void removeQueryRecords()
00278     {ibis::gParameters().add("query.purgeTempFiles", "true");}
00280     static void keepQueryRecords()
00281     {ibis::gParameters().add("query.purgeTempFiles", "false");}
00282 
00283     class result; // Forward declaration only
00284 
00285 protected:
00286     char* user;         
00287     char* condition;    
00288     selected comps;     
00289     QUERY_STATE state;  
00290     ibis::bitvector* hits;
00291     ibis::bitvector* sup;
00292     mutable ibis::part::readLock* dslock;       
00293     mutable char lastError[MAX_LINE+PATH_MAX];  
00294 
00295     void logError(const char* event, const char* fmt, ...) const;
00296     void logWarning(const char* event, const char* fmt, ...) const;
00297 
00298     void reorderExpr(); // reorder query expression
00299 
00300     bool hasBundles() const;
00301     int  verifyPredicate(qExpr*& qexpr);
00302     int  computeHits();   // generate the hit vector for range queries
00303     void getBounds();     // get the upper and lower bounds for range queries
00304     // use index only to come up with a upper bound and a lower bound
00305     void doEstimate(const qExpr* term, ibis::bitvector& low,
00306                     ibis::bitvector& high) const;
00307     // assume the mask contains information from the indexes already, read the
00308     // data table to resolve the query
00309     int doScan(const qExpr* term, const ibis::bitvector& mask,
00310                ibis::bitvector& hits) const;
00311     // only read the data table to resolve the query
00312     int doScan(const qExpr* term, ibis::bitvector& hits) const;
00313     // attempt evaluate one predicate condition at a time by using both
00314     // index and raw data table
00315     int doEvaluate(const qExpr* term, ibis::bitvector& hits) const;
00316     int doEvaluate(const qExpr* term, const ibis::bitvector& mask,
00317                    ibis::bitvector& hits) const;
00318 
00320     int64_t processJoin();
00322     void addJoinConstraints(ibis::qExpr*& exp0) const;
00323 
00324     // read/write the basic information about the query and its state
00325     virtual void writeQuery();
00326     void readQuery(const ibis::partList& tl);
00327     void removeFiles(); // remove the files written by this object
00328 
00329     // read/write the results of the query processing (hits, fids, rids,
00330     // file bundles)
00331     void readHits();
00332     void writeHits() const;
00333     void printRIDs(const RIDSet& ridset) const;
00334     // count the number of pages might be accessed to retrieve every value
00335     // in the hit vector
00336     uint32_t countPages(unsigned wordsize) const;
00337 
00338     // expand/contract query expression
00339     int doExpand(ibis::qExpr* exp0) const;
00340     int doContract(ibis::qExpr* exp0) const;
00341 
00342     // A group of functions to count the number of pairs
00343     // satisfying the join conditions.
00344     int64_t sortJoin(const std::vector<const ibis::rangeJoin*>& terms,
00345                      const ibis::bitvector& mask) const;
00346     int64_t sortJoin(const ibis::rangeJoin& cmp,
00347                      const ibis::bitvector& mask) const;
00348     int64_t sortEquiJoin(const ibis::rangeJoin& cmp,
00349                          const ibis::bitvector& mask) const;
00350     int64_t sortRangeJoin(const ibis::rangeJoin& cmp,
00351                           const ibis::bitvector& mask) const;
00352     int64_t sortEquiJoin(const ibis::rangeJoin& cmp,
00353                          const ibis::bitvector& mask,
00354                          const char* pairfile) const;
00355     int64_t sortRangeJoin(const ibis::rangeJoin& cmp,
00356                           const ibis::bitvector& mask,
00357                           const char* pairfile) const;
00358     void orderPairs(const char* pairfile) const;
00359     int64_t mergePairs(const char* pairfile) const;
00360 
00361     template <typename T1, typename T2>
00362     int64_t countEqualPairs(const array_t<T1>& val1,
00363                             const array_t<T2>& val2) const;
00364     template <typename T1, typename T2>
00365     int64_t countDeltaPairs(const array_t<T1>& val1,
00366                             const array_t<T2>& val2, const T1& delta) const;
00367     template <typename T1, typename T2>
00368     int64_t recordEqualPairs(const array_t<T1>& val1,
00369                              const array_t<T2>& val2,
00370                              const array_t<uint32_t>& ind1,
00371                              const array_t<uint32_t>& ind2,
00372                              const char* pairfile) const;
00373     template <typename T1, typename T2>
00374     int64_t recordDeltaPairs(const array_t<T1>& val1,
00375                              const array_t<T2>& val2,
00376                              const array_t<uint32_t>& ind1,
00377                              const array_t<uint32_t>& ind2,
00378                              const T1& delta, const char* pairfile) const;
00379 
00380     // functions for access control
00381     void gainReadAccess(const char* mesg) const {
00382         if (ibis::gVerbose > 10)
00383             logMessage("gainReadAccess", "acquiring a read lock for %s",
00384                        mesg);
00385         if (0 != pthread_rwlock_rdlock(&lock))
00386             logMessage("gainReadAccess",
00387                        "unable to gain read access to rwlock for %s", mesg);
00388     }
00389     void gainWriteAccess(const char* mesg) const {
00390         if (ibis::gVerbose > 10)
00391             logMessage("gainWriteAccess", "acquiring a write lock for %s",
00392                        mesg);
00393         if (0 != pthread_rwlock_wrlock(&lock))
00394             logMessage("gainWriteAccess",
00395                        "unable to gain write access to rwlock for %s", mesg);
00396     }
00397     void releaseAccess(const char* mesg) const {
00398         if (ibis::gVerbose > 10)
00399             logMessage("releaseAccess", "releasing rwlock for %s", mesg);
00400         if (0 != pthread_rwlock_unlock(&lock))
00401             logMessage("releaseAccess", "unable to unlock the rwlock for %s",
00402                        mesg);
00403     }
00404 
00405     // these two simple class are needed in order to ensure locks are
00406     // properly released even if the functions using them do not properly
00407     // terminate in particular, if the caller encounters an exception, the
00408     // destructor will be called automatically to ensure the locks are
00409     // released.
00410     class readLock {
00411     public:
00412         readLock(const query* q, const char* m) : theQuery(q), mesg(m) {
00413             theQuery->gainReadAccess(m);
00414         };
00415         ~readLock() {theQuery->releaseAccess(mesg);}
00416     private:
00417         const query* theQuery;
00418         const char* mesg;
00419 
00420         readLock() {}; // no default constructor
00421         readLock(const readLock&) {}; // can not copy
00422     };
00423 
00424     class writeLock {
00425     public:
00426         writeLock(const query* q, const char* m) : theQuery(q), mesg(m) {
00427             theQuery->gainWriteAccess(m);
00428         };
00429         ~writeLock() {theQuery->releaseAccess(mesg);}
00430     private:
00431         const query* theQuery;
00432         const char* mesg;
00433 
00434         writeLock() {}; // no default constructor
00435         writeLock(const writeLock&) {}; // can not copy
00436     };
00437     friend class readLock;
00438     friend class writeLock;
00439 
00440     // a class to be used for reordering the terms in the where clauses
00441     class weight : public ibis::qExpr::weight {
00442     public:
00443         virtual double operator()(const ibis::qExpr* ex) const;
00444         weight(const ibis::part* ds) : dataset(ds) {}
00445 
00446     private:
00447         const ibis::part* dataset;
00448     };
00449 
00450 private:
00451     char* myID;         // The unique ID of this query object
00452     char* myDir;        // Name of the directory containing the query record
00453     RIDSet* rids_in;    // Rid list specified in an RID query
00454     qExpr* expr;        // Query expression (pointer to the root of the tree)
00455     const part* table0; // Default table used to process the query
00456     time_t dstime;              // When query evaluation started
00457     mutable pthread_rwlock_t lock; // Rwlock for access control
00458 
00459     // private functions
00460     static char* newToken(const char*); 
00461 
00462     void setMyDir(const char *pref);
00463 
00464     query(const query&);
00465     const query& operator=(const query&);
00466 }; // class ibis::query
00467 
00468 namespace ibis {
00476     template <>
00477     int64_t query::countEqualPairs(const array_t<int32_t>& val1,
00478                                    const array_t<uint32_t>& val2) const;
00479     template <>
00480     int64_t query::countEqualPairs(const array_t<uint32_t>& val1,
00481                                    const array_t<int32_t>& val2) const;
00482     template <>
00483     int64_t query::countDeltaPairs(const array_t<int32_t>& val1,
00484                                    const array_t<uint32_t>& val2,
00485                                    const int32_t& delta) const;
00486     template <>
00487     int64_t query::countDeltaPairs(const array_t<uint32_t>& val1,
00488                                    const array_t<int32_t>& val2,
00489                                    const uint32_t& delta) const;
00490     template <>
00491     int64_t query::recordEqualPairs(const array_t<int32_t>& val1,
00492                                     const array_t<uint32_t>& val2,
00493                                     const array_t<uint32_t>& ind1,
00494                                     const array_t<uint32_t>& ind2,
00495                                     const char *pairfile) const;
00496     template <>
00497     int64_t query::recordEqualPairs(const array_t<uint32_t>& val1,
00498                                     const array_t<int32_t>& val2,
00499                                     const array_t<uint32_t>& ind1,
00500                                     const array_t<uint32_t>& ind2,
00501                                     const char *pairfile) const;
00502     template <>
00503     int64_t query::recordDeltaPairs(const array_t<int32_t>& val1,
00504                                     const array_t<uint32_t>& val2,
00505                                     const array_t<uint32_t>& ind1,
00506                                     const array_t<uint32_t>& ind2,
00507                                     const int32_t& delta,
00508                                     const char *pairfile) const;
00509     template <>
00510     int64_t query::recordDeltaPairs(const array_t<uint32_t>& val1,
00511                                     const array_t<int32_t>& val2,
00512                                     const array_t<uint32_t>& ind1,
00513                                     const array_t<uint32_t>& ind2,
00514                                     const uint32_t& delta,
00515                                     const char *pairfile) const;
00517 }
00518 #endif // IBIS_QUERY_H