home *** CD-ROM | disk | FTP | other *** search
/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre4.z / postgre4 / src / access / nbtree / nbtree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-08-27  |  11.2 KB  |  459 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. #include "tmp/postgres.h"
  10.  
  11. #include "storage/bufmgr.h"
  12. #include "storage/bufpage.h"
  13. #include "storage/page.h"
  14.  
  15. #include "utils/log.h"
  16. #include "utils/rel.h"
  17. #include "utils/excid.h"
  18.  
  19. #include "access/heapam.h"
  20. #include "access/genam.h"
  21. #include "access/ftup.h"
  22. #include "access/sdir.h"
  23. #include "access/isop.h"
  24. #include "access/nbtree.h"
  25. #include "access/funcindex.h"
  26.  
  27. #include "nodes/execnodes.h"
  28. #include "nodes/plannodes.h"
  29.  
  30. #include "executor/x_qual.h"
  31. #include "executor/x_tuples.h"
  32. #include "executor/tuptable.h"
  33.  
  34. #include "lib/index.h"
  35.  
  36. extern ExprContext RMakeExprContext();
  37.  
  38. bool    BuildingBtree = false;
  39.  
  40. RcsId("$Header: /private/postgres/src/access/nbtree/RCS/nbtree.c,v 1.20 1992/08/24 23:14:31 mao Exp $");
  41.  
  42. /*
  43.  *  btbuild() -- build a new btree index.
  44.  *
  45.  *    We use a global variable to record the fact that we're creating
  46.  *    a new index.  This is used to avoid high-concurrency locking,
  47.  *    since the index won't be visible until this transaction commits
  48.  *    and since building is guaranteed to be single-threaded.
  49.  */
  50.  
  51. void
  52. btbuild(heap, index, natts, attnum, istrat, pcount, params, finfo, pred)
  53.     Relation heap;
  54.     Relation index;
  55.     AttributeNumber natts;
  56.     AttributeNumber *attnum;
  57.     IndexStrategy istrat;
  58.     uint16 pcount;
  59.     Datum *params;
  60.     FuncIndexInfo *finfo;
  61.     LispValue pred;
  62. {
  63.     HeapScanDesc hscan;
  64.     Buffer buffer;
  65.     HeapTuple htup;
  66.     IndexTuple itup;
  67.     TupleDescriptor htupdesc, itupdesc;
  68.     Datum *attdata;
  69.     Boolean *nulls;
  70.     InsertIndexResult res;
  71.     int nhtups, nitups;
  72.     int i;
  73.     BTItem btitem;
  74.     TransactionId currxid;
  75.     ExprContext econtext;
  76.     TupleTable tupleTable;
  77.     TupleTableSlot slot;
  78.     ObjectId hrelid, irelid;
  79.  
  80.     /* note that this is a new btree */
  81.     BuildingBtree = true;
  82.  
  83.     /* first initialize the btree index metadata page */
  84.     _bt_metapinit(index);
  85.  
  86.     /* get tuple descriptors for heap and index relations */
  87.     htupdesc = RelationGetTupleDescriptor(heap);
  88.     itupdesc = RelationGetTupleDescriptor(index);
  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 = _bt_formitem(itup);
  160.     res = _bt_doinsert(index, btitem);
  161.     pfree(btitem);
  162.     pfree(itup);
  163.     pfree(res);
  164.     }
  165.  
  166.     /* okay, all heap tuples are indexed */
  167.     heap_endscan(hscan);
  168.  
  169.     if (pred != LispNil) {
  170.     ExecDestroyTupleTable(tupleTable, false);
  171.     }
  172.  
  173.     /*
  174.      *  Since we just counted the tuples in the heap, we update its
  175.      *  stats in pg_class to guarantee that the planner takes advantage
  176.      *  of the index we just created. Finally, only update statistics
  177.      *  during normal index definitions, not for indices on system catalogs
  178.      *  created during bootstrap processing.  We must close the relations
  179.      *  before updatings statistics to guarantee that the relcache entries
  180.      *  are flushed when we increment the command counter in UpdateStats().
  181.      */
  182.     if (IsNormalProcessingMode())
  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.  
  192.     /* be tidy */
  193.     pfree(nulls);
  194.     pfree(attdata);
  195.  
  196.     /* all done */
  197.     BuildingBtree = false;
  198. }
  199.  
  200. /*
  201.  *  btinsert() -- insert an index tuple into a btree.
  202.  *
  203.  *    Descend the tree recursively, find the appropriate location for our
  204.  *    new tuple, put it there, set its unique OID as appropriate, and
  205.  *    return an InsertIndexResult to the caller.
  206.  */
  207.  
  208. InsertIndexResult
  209. btinsert(rel, itup)
  210.     Relation rel;
  211.     IndexTuple itup;
  212. {
  213.     BTItem btitem;
  214.     int nbytes_btitem;
  215.     InsertIndexResult res;
  216.  
  217.     btitem = _bt_formitem(itup);
  218.  
  219.     res = _bt_doinsert(rel, btitem);
  220.     pfree(btitem);
  221.  
  222.     return (res);
  223. }
  224.  
  225. /*
  226.  *  btgettuple() -- Get the next tuple in the scan.
  227.  */
  228.  
  229. char *
  230. btgettuple(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.     if (ItemPointerIsValid(&(scan->currentItemData)))
  243.     res = _bt_next(scan, dir);
  244.     else
  245.     res = _bt_first(scan, dir);
  246.  
  247.     return ((char *) res);
  248. }
  249.  
  250. /*
  251.  *  btbeginscan() -- start a scan on a btree index
  252.  */
  253.  
  254. char *
  255. btbeginscan(rel, fromEnd, keysz, scankey)
  256.     Relation rel;
  257.     Boolean fromEnd;
  258.     uint16 keysz;
  259.     ScanKey scankey;
  260. {
  261.     IndexScanDesc scan;
  262.     StrategyNumber strat;
  263.     BTScanOpaque so;
  264.  
  265.     /* first order the keys in the qualification */
  266.     if (keysz > 1)
  267.     _bt_orderkeys(rel, &keysz, scankey);
  268.  
  269.     /* now get the scan */
  270.     scan = RelationGetIndexScan(rel, fromEnd, keysz, scankey);
  271.     so = (BTScanOpaque) palloc(sizeof(BTScanOpaqueData));
  272.     so->btso_curbuf = so->btso_mrkbuf = InvalidBuffer;
  273.     scan->opaque = (Pointer) so;
  274.  
  275.     /* finally, be sure that the scan exploits the tree order */
  276.     scan->scanFromEnd = false;
  277.     scan->flags = 0x0;
  278.     if (keysz > 0) {
  279.     strat = _bt_getstrat(scan->relation, 1 /* XXX */,
  280.                  scankey->data[0].procedure);
  281.  
  282.     if (strat == BTLessStrategyNumber
  283.         || strat == BTLessEqualStrategyNumber)
  284.         scan->scanFromEnd = true;
  285.     } else {
  286.     scan->scanFromEnd = true;
  287.     }
  288.  
  289.     /* register scan in case we change pages it's using */
  290.     _bt_regscan(scan);
  291.  
  292.     return ((char *) scan);
  293. }
  294.  
  295. /*
  296.  *  btrescan() -- rescan an index relation
  297.  */
  298.  
  299. void
  300. btrescan(scan, fromEnd, scankey)
  301.     IndexScanDesc scan;
  302.     Boolean fromEnd;
  303.     ScanKey scankey;
  304. {
  305.     ItemPointer iptr;
  306.     BTScanOpaque so;
  307.  
  308.     so = (BTScanOpaque) scan->opaque;
  309.  
  310.     /* we hold a read lock on the current page in the scan */
  311.     if (ItemPointerIsValid(iptr = &(scan->currentItemData))) {
  312.     _bt_relbuf(scan->relation, so->btso_curbuf, BT_READ);
  313.     so->btso_curbuf = InvalidBuffer;
  314.     ItemPointerSetInvalid(iptr);
  315.     }
  316.  
  317.     /* and we hold a read lock on the last marked item in the scan */
  318.     if (ItemPointerIsValid(iptr = &(scan->currentMarkData))) {
  319.     _bt_relbuf(scan->relation, so->btso_mrkbuf, BT_READ);
  320.     so->btso_mrkbuf = InvalidBuffer;
  321.     ItemPointerSetInvalid(iptr);
  322.     }
  323.  
  324.     /* reset the scan key */
  325.     if (scan->numberOfKeys > 0) {
  326.     bcopy( (Pointer)&scankey->data[0],
  327.            (Pointer)&scan->keyData.data[0],
  328.            scan->numberOfKeys * sizeof(scankey->data[0])
  329.          );
  330.     }
  331. }
  332.  
  333. void
  334. btmovescan(scan, v)
  335.     IndexScanDesc scan;
  336.     Datum v;
  337. {
  338.     ItemPointer iptr;
  339.     BTScanOpaque so;
  340.  
  341.     so = (BTScanOpaque) scan->opaque;
  342.  
  343.     /* release any locks we still hold */
  344.     if (ItemPointerIsValid(iptr = &(scan->currentItemData))) {
  345.     _bt_relbuf(scan->relation, so->btso_curbuf, BT_READ);
  346.     so->btso_curbuf = InvalidBuffer;
  347.     ItemPointerSetInvalid(iptr);
  348.     }
  349.  
  350.     scan->keyData.data[0].argument = v;
  351. }
  352. /*
  353.  *  btendscan() -- close down a scan
  354.  */
  355.  
  356. void
  357. btendscan(scan)
  358.     IndexScanDesc scan;
  359. {
  360.     ItemPointer iptr;
  361.     BTScanOpaque so;
  362.  
  363.     so = (BTScanOpaque) scan->opaque;
  364.  
  365.     /* release any locks we still hold */
  366.     if (ItemPointerIsValid(iptr = &(scan->currentItemData))) {
  367.     _bt_relbuf(scan->relation, so->btso_curbuf, BT_READ);
  368.     so->btso_curbuf = InvalidBuffer;
  369.     ItemPointerSetInvalid(iptr);
  370.     }
  371.  
  372.     if (ItemPointerIsValid(iptr = &(scan->currentMarkData))) {
  373.     if (BufferIsValid(so->btso_mrkbuf))
  374.         _bt_relbuf(scan->relation, so->btso_mrkbuf, BT_READ);
  375.     so->btso_mrkbuf = InvalidBuffer;
  376.     ItemPointerSetInvalid(iptr);
  377.     }
  378.  
  379.     /* don't need scan registered anymore */
  380.     _bt_dropscan(scan);
  381.  
  382.     /* be tidy */
  383. #ifdef PERFECT_MMGR
  384.     pfree (scan->opaque);
  385. #endif /* PERFECT_MMGR */
  386. }
  387.  
  388. /*
  389.  *  btmarkpos() -- save current scan position
  390.  */
  391.  
  392. void
  393. btmarkpos(scan)
  394.     IndexScanDesc scan;
  395. {
  396.     ItemPointer iptr;
  397.     BTScanOpaque so;
  398.  
  399.     so = (BTScanOpaque) scan->opaque;
  400.  
  401.     /* release lock on old marked data, if any */
  402.     if (ItemPointerIsValid(iptr = &(scan->currentMarkData))) {
  403.     _bt_relbuf(scan->relation, so->btso_mrkbuf, BT_READ);
  404.     so->btso_mrkbuf = InvalidBuffer;
  405.     ItemPointerSetInvalid(iptr);
  406.     }
  407.  
  408.     /* bump lock on currentItemData and copy to currentMarkData */
  409.     if (ItemPointerIsValid(&(scan->currentItemData))) {
  410.     so->btso_mrkbuf = _bt_getbuf(scan->relation,
  411.                      BufferGetBlockNumber(so->btso_curbuf),
  412.                      BT_READ);
  413.     scan->currentMarkData = scan->currentItemData;
  414.     }
  415. }
  416.  
  417. /*
  418.  *  btrestrpos() -- restore scan to last saved position
  419.  */
  420.  
  421. void
  422. btrestrpos(scan)
  423.     IndexScanDesc scan;
  424. {
  425.     ItemPointer iptr;
  426.     BTScanOpaque so;
  427.  
  428.     so = (BTScanOpaque) scan->opaque;
  429.  
  430.     /* release lock on current data, if any */
  431.     if (ItemPointerIsValid(iptr = &(scan->currentItemData))) {
  432.     _bt_relbuf(scan->relation, so->btso_curbuf, BT_READ);
  433.     so->btso_curbuf = InvalidBuffer;
  434.     ItemPointerSetInvalid(iptr);
  435.     }
  436.  
  437.     /* bump lock on currentMarkData and copy to currentItemData */
  438.     if (ItemPointerIsValid(&(scan->currentMarkData))) {
  439.     so->btso_curbuf = _bt_getbuf(scan->relation,
  440.                      BufferGetBlockNumber(so->btso_mrkbuf),
  441.                      BT_READ);
  442.                      
  443.     scan->currentItemData = scan->currentMarkData;
  444.     }
  445. }
  446.  
  447. /* stubs */
  448. void
  449. btdelete(rel, tid)
  450.     Relation rel;
  451.     ItemPointer tid;
  452. {
  453.     /* adjust any active scans that will be affected by this deletion */
  454.     _bt_adjscans(rel, tid);
  455.  
  456.     /* delete the data from the page */
  457.     _bt_pagedel(rel, tid);
  458. }
  459.