home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / nobtree / nobtree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  11.4 KB  |  472 lines
  1. /*
  2.  *  btree.c -- Implementation of Lehman and Yao's btree management algorithm
  3.  *           for Postgres.
  4.  *
  5.  *    This file contains only the public interface routines.
  6.  */
  7.  
  8. #include "tmp/c.h"
  9.  
  10. #ifdef NOBTREE
  11. #include "tmp/postgres.h"
  12.  
  13. #include "storage/bufmgr.h"
  14. #include "storage/bufpage.h"
  15. #include "storage/page.h"
  16.  
  17. #include "utils/log.h"
  18. #include "utils/rel.h"
  19. #include "utils/excid.h"
  20.  
  21. #include "access/heapam.h"
  22. #include "access/genam.h"
  23. #include "access/ftup.h"
  24. #include "access/sdir.h"
  25. #include "access/isop.h"
  26. #include "access/nobtree.h"
  27. #include "access/funcindex.h"
  28.  
  29. #include "nodes/execnodes.h"
  30. #include "nodes/plannodes.h"
  31.  
  32. #include "executor/x_qual.h"
  33. #include "executor/x_tuples.h"
  34. #include "executor/tuptable.h"
  35.  
  36. #include "lib/index.h"
  37.  
  38. extern ExprContext RMakeExprContext();
  39.  
  40. RcsId("$Header: /private/postgres/src/access/nobtree/RCS/nobtree.c,v 1.11 1992/08/24 23:14:37 mao Exp $");
  41.  
  42. /* the global sequence number for insertions is defined here */
  43. uint32    NOBTCurrSeqNo = 0;
  44. bool    NOBT_Building = false;
  45. uint32  CurrentLinkToken = 0;
  46.  
  47. void
  48. nobtbuild(heap, index, natts, attnum, istrat, pcount, params, finfo, pred)
  49.     Relation heap;
  50.     Relation index;
  51.     AttributeNumber natts;
  52.     AttributeNumber *attnum;
  53.     IndexStrategy istrat;
  54.     uint16 pcount;
  55.     Datum *params;
  56.     FuncIndexInfo *finfo;
  57.     LispValue pred;
  58. {
  59.     HeapScanDesc hscan;
  60.     Buffer buffer;
  61.     HeapTuple htup;
  62.     IndexTuple itup;
  63.     TupleDescriptor htupdesc, itupdesc;
  64.     Datum *attdata;
  65.     Boolean *nulls;
  66.     InsertIndexResult res;
  67.     int nhtups, nitups;
  68.     int i;
  69.     NOBTLItem btitem;
  70.     TransactionId currxid;
  71.     ExprContext econtext;
  72.     TupleTable tupleTable;
  73.     TupleTableSlot slot;
  74.     extern TransactionId GetCurrentTransactionId();
  75.     ObjectId hrelid, irelid;
  76.  
  77.     /* don't bother with no-overwrite behavior for initial build */
  78.     NOBT_Building = true;
  79.  
  80.     /* first initialize the btree index metadata page */
  81.     _nobt_metapinit(index);
  82.  
  83.     /* get tuple descriptors for heap and index relations */
  84.     htupdesc = RelationGetTupleDescriptor(heap);
  85.     itupdesc = RelationGetTupleDescriptor(index);
  86.  
  87.     /* record current transaction id for uniqueness */
  88.     currxid = GetCurrentTransactionId();
  89.  
  90.     /* get space for data items that'll appear in the index tuple */
  91.     attdata = (Datum *) palloc(natts * sizeof(Datum));
  92.     nulls = (Boolean *) palloc(natts * sizeof(Boolean));
  93.  
  94.     /*
  95.      * If this is a predicate (partial) index, we will need to evaluate the
  96.      * predicate using ExecQual, which requires the current tuple to be in a
  97.      * slot of a TupleTable.  In addition, ExecQual must have an ExprContext
  98.      * referring to that slot.  Here, we initialize dummy TupleTable and
  99.      * ExprContext objects for this purpose. --Nels, Feb '92
  100.      */
  101.     if (pred != LispNil) {
  102.     tupleTable = ExecCreateTupleTable(1);
  103.     slot = (TupleTableSlot)
  104.         ExecGetTableSlot(tupleTable, ExecAllocTableSlot(tupleTable));
  105.     econtext = RMakeExprContext();
  106.     FillDummyExprContext(econtext, slot, htupdesc, buffer);
  107.     }
  108.  
  109.     /* start a heap scan */
  110.     hscan = heap_beginscan(heap, 0, NowTimeQual, 0, (ScanKey) NULL);
  111.     htup = heap_getnext(hscan, 0, &buffer);
  112.  
  113.     /* build the index */
  114.     nhtups = nitups = 0;
  115.  
  116.     for (; HeapTupleIsValid(htup); htup = heap_getnext(hscan, 0, &buffer)) {
  117.  
  118.     nhtups++;
  119.  
  120.     /* Skip this tuple if it doesn't satisfy the partial-index predicate */
  121.     if (pred != LispNil) {
  122.         SetSlotContents(slot, htup);
  123.         if (ExecQual(pred, econtext) == false)
  124.         continue;
  125.     }
  126.  
  127.     nitups++;
  128.  
  129.     /*
  130.      *  For the current heap tuple, extract all the attributes
  131.      *  we use in this index, and note which are null.
  132.      */
  133.  
  134.     for (i = 1; i <= natts; i++) {
  135.         AttributeOffset attoff;
  136.         Boolean attnull;
  137.  
  138.         /*
  139.          *  Offsets are from the start of the tuple, and are
  140.          *  zero-based; indices are one-based.  The next call
  141.          *  returns i - 1.  That's data hiding for you.
  142.          */
  143.  
  144.         attoff = AttributeNumberGetAttributeOffset(i);
  145.         attdata[attoff] = GetIndexValue(htup,
  146.                         htupdesc,
  147.                         attoff,
  148.                         attnum,
  149.                         finfo,
  150.                         &attnull,
  151.                         buffer);
  152.         nulls[attoff] = (attnull ? 'n' : ' ');
  153.     }
  154.  
  155.     /* form an index tuple and point it at the heap tuple */
  156.     itup = FormIndexTuple(natts, itupdesc, attdata, nulls);
  157.     itup->t_tid = htup->t_ctid;
  158.  
  159.     btitem = _nobt_formitem(itup);
  160.     _nobt_countstart();
  161.     res = _nobt_doinsert(index, btitem);
  162.     _nobt_countstop();
  163.     pfree(btitem);
  164.     pfree(itup);
  165.     pfree(res);
  166.     }
  167.  
  168.     /* okay, all heap tuples are indexed */
  169.     heap_endscan(hscan);
  170.  
  171.     if (pred != LispNil) {
  172.     ExecDestroyTupleTable(tupleTable, false);
  173.     }
  174.  
  175.     /*
  176.      *  Since we just counted the tuples in the heap, we update its
  177.      *  stats in pg_class to guarantee that the planner takes advantage
  178.      *  of the index we just created.  We have to close the relations
  179.      *  before calling UpdateStats() so that the relcache entries for
  180.      *  them, which are now incorrect, will be flushed by the call to
  181.      *  CommandCounterIncrement() in UpdateStats().
  182.      */
  183.  
  184.     hrelid = heap->rd_id;
  185.     irelid = index->rd_id;
  186.     heap_close(heap);
  187.     index_close(index);
  188.     UpdateStats(hrelid, nhtups, true);
  189.     UpdateStats(irelid, nitups, false);
  190.  
  191.     /* be tidy */
  192.     pfree(nulls);
  193.     pfree(attdata);
  194.  
  195.     NOBT_Building = false;
  196. }
  197.  
  198. /*
  199.  *  nobtinsert() -- insert an index tuple into a btree.
  200.  *
  201.  *    Descend the tree recursively, find the appropriate location for our
  202.  *    new tuple, put it there, set its sequence number as appropriate, and
  203.  *    return an InsertIndexResult to the caller.
  204.  */
  205.  
  206. InsertIndexResult
  207. nobtinsert(rel, itup)
  208.     Relation rel;
  209.     IndexTuple itup;
  210. {
  211.     NOBTLItem btitem;
  212.     int nbytes_btitem;
  213.     InsertIndexResult res;
  214.  
  215.     btitem = _nobt_formitem(itup);
  216.  
  217.     _nobt_countstart();
  218.     res = _nobt_doinsert(rel, btitem);
  219.     _nobt_countstop();
  220.     pfree(btitem);
  221.  
  222.     return (res);
  223. }
  224.  
  225. /*
  226.  *  nobtgettuple() -- Get the next tuple in the scan.
  227.  */
  228.  
  229. char *
  230. nobtgettuple(scan, dir)
  231.     IndexScanDesc scan;
  232.     ScanDirection dir;
  233. {
  234.     RetrieveIndexResult res;
  235.  
  236.     /*
  237.      *  If we've already initialized this scan, we can just advance it
  238.      *  in the appropriate direction.  If we haven't done so yet, we
  239.      *  call a routine to get the first item in the scan.
  240.      */
  241.  
  242.     _nobt_countstart();
  243.  
  244.     if (ItemPointerIsValid(&(scan->currentItemData)))
  245.     res = _nobt_next(scan, dir);
  246.     else
  247.     res = _nobt_first(scan, dir);
  248.  
  249.     _nobt_countstop();
  250.  
  251.     return ((char *) res);
  252. }
  253.  
  254. /*
  255.  *  nobtbeginscan() -- start a scan on a btree index
  256.  */
  257.  
  258. char *
  259. nobtbeginscan(rel, fromEnd, keysz, scankey)
  260.     Relation rel;
  261.     Boolean fromEnd;
  262.     uint16 keysz;
  263.     ScanKey scankey;
  264. {
  265.     IndexScanDesc scan;
  266.     StrategyNumber strat;
  267.     NOBTScanOpaque so;
  268.  
  269.     /* first order the keys in the qualification */
  270.     if (keysz > 0)
  271.     _nobt_orderkeys(rel, &keysz, scankey);
  272.  
  273.     /* now get the scan */
  274.     scan = RelationGetIndexScan(rel, fromEnd, keysz, scankey);
  275.     so = (NOBTScanOpaque) palloc(sizeof(NOBTScanOpaqueData));
  276.     so->nobtso_curbuf = so->nobtso_mrkbuf = InvalidBuffer;
  277.     scan->opaque = (Pointer) so;
  278.  
  279.     /* finally, be sure that the scan exploits the tree order */
  280.     scan->scanFromEnd = false;
  281.     scan->flags = 0x0;
  282.     if (keysz > 0) {
  283.     strat = _nobt_getstrat(scan->relation, 1 /* XXX */,
  284.                  scankey->data[0].procedure);
  285.  
  286.     if (strat == NOBTLessStrategyNumber
  287.         || strat == NOBTLessEqualStrategyNumber)
  288.         scan->scanFromEnd = true;
  289.     } else {
  290.     scan->scanFromEnd = true;
  291.     }
  292.  
  293.     /* register scan in case we change pages it's using */
  294.     _nobt_regscan(scan);
  295.  
  296.     return ((char *) scan);
  297. }
  298.  
  299. /*
  300.  *  nobtrescan() -- rescan an index relation
  301.  */
  302.  
  303. void
  304. nobtrescan(scan, fromEnd, scankey)
  305.     IndexScanDesc scan;
  306.     Boolean fromEnd;
  307.     ScanKey scankey;
  308. {
  309.     ItemPointer iptr;
  310.     NOBTScanOpaque so;
  311.  
  312.     so = (NOBTScanOpaque) scan->opaque;
  313.  
  314.     /* we hold a read lock on the current page in the scan */
  315.     if (ItemPointerIsValid(iptr = &(scan->currentItemData))) {
  316.     _nobt_relbuf(scan->relation, so->nobtso_curbuf, NOBT_READ);
  317.     so->nobtso_curbuf = InvalidBuffer;
  318.     ItemPointerSetInvalid(iptr);
  319.     }
  320.  
  321.     /* and we hold a read lock on the last marked item in the scan */
  322.     if (ItemPointerIsValid(iptr = &(scan->currentMarkData))) {
  323.     _nobt_relbuf(scan->relation, so->nobtso_mrkbuf, NOBT_READ);
  324.     so->nobtso_mrkbuf = InvalidBuffer;
  325.     ItemPointerSetInvalid(iptr);
  326.     }
  327.  
  328.     /* reset the scan key */
  329.     if (scan->numberOfKeys > 0) {
  330.     bcopy( (Pointer)&scankey->data[0],
  331.            (Pointer)&scan->keyData.data[0],
  332.            scan->numberOfKeys * sizeof(scankey->data[0])
  333.          );
  334.     }
  335. }
  336.  
  337. /*
  338.  *  nobtendscan() -- close down a scan
  339.  */
  340.  
  341. void
  342. nobtendscan(scan)
  343.     IndexScanDesc scan;
  344. {
  345.     ItemPointer iptr;
  346.     NOBTScanOpaque so;
  347.  
  348.     so = (NOBTScanOpaque) scan->opaque;
  349.  
  350.     /* release any locks we still hold */
  351.     if (ItemPointerIsValid(iptr = &(scan->currentItemData))) {
  352.     _nobt_relbuf(scan->relation, so->nobtso_curbuf, NOBT_READ);
  353.     so->nobtso_curbuf = InvalidBuffer;
  354.     ItemPointerSetInvalid(iptr);
  355.     }
  356.  
  357.     if (ItemPointerIsValid(iptr = &(scan->currentMarkData))) {
  358.     _nobt_relbuf(scan->relation, so->nobtso_mrkbuf, NOBT_READ);
  359.     so->nobtso_mrkbuf = InvalidBuffer;
  360.     ItemPointerSetInvalid(iptr);
  361.     }
  362.  
  363.     /* don't need scan registered anymore */
  364.     _nobt_dropscan(scan);
  365.  
  366.     /* be tidy */
  367.     pfree (scan->opaque);
  368. }
  369.  
  370. /*
  371.  *  nobtmarkpos() -- save current scan position
  372.  */
  373.  
  374. void
  375. nobtmarkpos(scan)
  376.     IndexScanDesc scan;
  377. {
  378.     ItemPointer iptr;
  379.     NOBTScanOpaque so;
  380.  
  381.     so = (NOBTScanOpaque) scan->opaque;
  382.  
  383.     /* release lock on old marked data, if any */
  384.     if (ItemPointerIsValid(iptr = &(scan->currentMarkData))) {
  385.     _nobt_relbuf(scan->relation, so->nobtso_mrkbuf, NOBT_READ);
  386.     so->nobtso_mrkbuf = InvalidBuffer;
  387.     ItemPointerSetInvalid(iptr);
  388.     }
  389.  
  390.     /* bump lock on currentItemData and copy to currentMarkData */
  391.     if (ItemPointerIsValid(&(scan->currentItemData))) {
  392.     so->nobtso_mrkbuf = _nobt_getbuf(scan->relation,
  393.                      BufferGetBlockNumber(so->nobtso_curbuf),
  394.                      NOBT_READ);
  395.     scan->currentMarkData = scan->currentItemData;
  396.     }
  397. }
  398.  
  399. /*
  400.  *  nobtrestrpos() -- restore scan to last saved position
  401.  */
  402.  
  403. void
  404. nobtrestrpos(scan)
  405.     IndexScanDesc scan;
  406. {
  407.     ItemPointer iptr;
  408.     NOBTScanOpaque so;
  409.  
  410.     so = (NOBTScanOpaque) scan->opaque;
  411.  
  412.     /* release lock on current data, if any */
  413.     if (ItemPointerIsValid(iptr = &(scan->currentItemData))) {
  414.     _nobt_relbuf(scan->relation, so->nobtso_curbuf, NOBT_READ);
  415.     so->nobtso_curbuf = InvalidBuffer;
  416.     ItemPointerSetInvalid(iptr);
  417.     }
  418.  
  419.     /* bump lock on currentMarkData and copy to currentItemData */
  420.     if (ItemPointerIsValid(&(scan->currentMarkData))) {
  421.     so->nobtso_curbuf = _nobt_getbuf(scan->relation,
  422.                      BufferGetBlockNumber(so->nobtso_mrkbuf),
  423.                      NOBT_READ);
  424.                      
  425.     scan->currentItemData = scan->currentMarkData;
  426.     }
  427. }
  428.  
  429. /* stubs */
  430. void
  431. nobtdelete(rel, tid)
  432.     Relation rel;
  433.     ItemPointer tid;
  434. {
  435.     /* adjust any active scans that will be affected by this deletion */
  436.     _nobt_adjscans(rel, tid);
  437.  
  438.     /* delete the data from the page */
  439.     _nobt_pagedel(rel, tid);
  440. }
  441.  
  442. ___MAO(limit)
  443.     int limit;
  444. {
  445.     int i;
  446.     int v;
  447.     IndexScanDesc s;
  448.     Relation index;
  449.     extern int getpid();
  450.     extern long random();
  451.     ScanKeyEntryData skey;
  452.  
  453.     srandom(getpid());
  454.     ScanKeyEntryInitialize(&skey, 0x0, 1, 65, 0);
  455.     index = index_openr("zzz");
  456.  
  457.     for (i = 0; i < 8000; i++) {
  458.     v = random() % limit;
  459.     skey.argument = Int32GetDatum(v);
  460.     s = (IndexScanDesc) nobtbeginscan(index, false, 1, &skey);
  461.     (void) nobtgettuple(s, ForwardScanDirection);
  462.     nobtendscan(s);
  463.     }
  464.  
  465.     index_close(index);
  466.  
  467.     _nobt_countout();
  468.     exitpg(0);
  469. }
  470.  
  471. #endif /* NOBTREE */
  472.