KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > store > access > btree > BTreeController


1 /*
2
3    Derby - Class org.apache.derby.impl.store.access.btree.BTreeController
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.store.access.btree;
23
24 import java.io.IOException JavaDoc;
25 import java.util.Properties JavaDoc;
26
27 import org.apache.derby.iapi.reference.SQLState;
28
29 import org.apache.derby.iapi.services.sanity.SanityManager;
30
31 import org.apache.derby.iapi.services.io.Storable;
32
33 import org.apache.derby.iapi.error.StandardException;
34 import org.apache.derby.iapi.store.access.conglomerate.Conglomerate;
35 import org.apache.derby.iapi.store.access.conglomerate.LogicalUndo;
36 import org.apache.derby.iapi.store.access.conglomerate.TransactionManager;
37 import org.apache.derby.iapi.store.access.AccessFactoryGlobals;
38 import org.apache.derby.iapi.store.access.ConglomerateController;
39 import org.apache.derby.iapi.store.access.DynamicCompiledOpenConglomInfo;
40 import org.apache.derby.iapi.store.access.RowLocationRetRowSource;
41 import org.apache.derby.iapi.store.access.RowUtil;
42 import org.apache.derby.iapi.store.access.ScanController;
43 import org.apache.derby.iapi.store.access.StaticCompiledOpenConglomInfo;
44 import org.apache.derby.iapi.store.access.TransactionController;
45
46 import org.apache.derby.iapi.store.raw.ContainerHandle;
47 import org.apache.derby.iapi.store.raw.FetchDescriptor;
48 import org.apache.derby.iapi.store.raw.LockingPolicy;
49 import org.apache.derby.iapi.store.raw.Page;
50 import org.apache.derby.iapi.store.raw.RecordHandle;
51 import org.apache.derby.iapi.store.raw.Transaction;
52
53 import org.apache.derby.iapi.types.DataValueDescriptor;
54
55 import org.apache.derby.iapi.types.RowLocation;
56
57 import org.apache.derby.iapi.services.io.FormatableBitSet;
58 import org.apache.derby.impl.store.access.conglomerate.ConglomerateUtil;
59 import org.apache.derby.impl.store.access.conglomerate.TemplateRow;
60
61
62
63 /**
64
65   A b-tree controller corresponds to an instance of an open b-tree conglomerate.
66   <P>
67   <B>Concurrency Notes<\B>
68   <P>
69   The concurrency rules are derived from OpenBTree.
70   <P>
71   @see OpenBTree
72
73 **/
74
75 public class BTreeController extends OpenBTree implements ConglomerateController
76 {
77
78     transient DataValueDescriptor[] scratch_template = null;
79
80     /**
81      * Whether to get lock on the row being inserted, usually this lock
82      * has already been gotten when the row was inserted into the base table.
83      **/
84     boolean get_insert_row_lock;
85
86     /* Constructors: */
87
88     public BTreeController()
89     {
90     }
91
92     /*
93     ** private Methods of BTreeController
94     */
95
96     /**
97      * Attempt to reclaim committed deleted rows from the page.
98      * <p>
99      * Get exclusive latch on page, and then loop backward through
100      * page searching for deleted rows which are committed. The routine
101      * assumes that it is called from a transaction which cannot have
102      * deleted any rows on the page. For each deleted row on the page
103      * it attempts to get an exclusive lock on the deleted row, NOWAIT.
104      * If it succeeds, and since this row did not delete the row then the
105      * row must have been deleted by a transaction which has committed, so
106      * it is safe to purge the row. It then purges the row from the page.
107      * <p>
108      * Note that this routine may remove all rows from the page, it will not
109      * attempt a merge in this situation. This is because this routine is
110      * called from split which is attempting an insert on the given page, so
111      * it would be a waste to merge the page only to split it again to allow
112      * the insert of the row causing the split.
113      *
114      * @return true if at least one row was purged.
115      *
116      * @param open_btree The already open btree to use to get latch on page.
117      * @param pageno The page number of the leaf to attempt the reclaim on.
118      *
119      * @exception StandardException Standard exception policy.
120      **/
121     private boolean reclaim_deleted_rows(
122     OpenBTree open_btree,
123     long pageno)
124         throws StandardException
125     {
126         boolean purged_at_least_one_row = false;
127         ControlRow controlRow = null;
128
129         try
130         {
131
132             if ((controlRow = ControlRow.Get(open_btree, pageno)) == null)
133                 return(false);
134
135             LeafControlRow leaf = (LeafControlRow) controlRow;
136
137             BTreeLockingPolicy btree_locking_policy =
138                 open_btree.getLockingPolicy();
139
140
141             // The number records that can be reclaimed is:
142 // total recs - control row - recs_not_deleted
143 int num_possible_commit_delete =
144                 leaf.page.recordCount() - 1 - leaf.page.nonDeletedRecordCount();
145
146             if ((num_possible_commit_delete > 0) &&
147                 (btree_locking_policy.lockScanForReclaimSpace(leaf)))
148             {
149                 // Need to get an exclusive scan lock on the page before we can
150 // do any sort of purges, otherwise other concurrent scans would
151 // not work. If we can't get the lock NOWAIT, just give up on
152 // purging rows and do the split without reclaiming rows.
153
154                 Page page = leaf.page;
155
156
157                 // RowLocation column is in last column of template.
158 FetchDescriptor lock_fetch_desc =
159                     RowUtil.getFetchDescriptorConstant(
160                         scratch_template.length - 1);
161
162                 // loop backward so that purges which affect the slot table
163 // don't affect the loop (ie. they only move records we
164 // have already looked at).
165 for (int slot_no = page.recordCount() - 1;
166                      slot_no > 0;
167                      slot_no--)
168                 {
169                     if (page.isDeletedAtSlot(slot_no))
170                     {
171                         // try to get an exclusive lock on the row, if we can
172 // then the row is a committed deleted row and it is
173 // safe to purge it.
174 if (btree_locking_policy.lockScanCommittedDeletedRow(
175                                 open_btree, leaf, scratch_template,
176                                 lock_fetch_desc, slot_no))
177                         {
178                             // the row is a committed deleted row, purge it.
179 page.purgeAtSlot(slot_no, 1, true);
180
181                             purged_at_least_one_row = true;
182                         }
183                     }
184                 }
185
186             }
187         }
188         catch (java.lang.ClassCastException JavaDoc cce)
189         {
190             // because we give up the latch on the leaf before entering this
191 // routine, the page might change from a leaf to branch. If that
192 // happens this routine will get a ClassCastException, and we
193 // just give up trying to reclaim space.
194 }
195         finally
196         {
197             if (controlRow != null)
198                 controlRow.release();
199
200             return(purged_at_least_one_row);
201         }
202     }
203
204     /**
205      * Start an internal transaction and do the split.
206      * <p>
207      * This routine starts a new transaction, and handles any errors that
208      * may come during the transaction. This transation must not obtain any
209      * locks as they are likely to conflict with the current user transaction.
210      * <p>
211      * If attempt_to_reclaim_deleted_rows is true this routine will
212      * attempt to reclaim space on the leaf page input, by purging
213      * committed deleted rows from the leaf. If it succeeds in purging at
214      * least one row, then it will commit the internal transaction and return
215      * without actually performing a split.
216      *
217      * @param scratch_template A scratch template used to search a page.
218      * @param rowToInsert The row to insert, make sure during split to
219      * make room for this row.
220      *
221      * @exception StandardException Standard exception policy.
222      **/
223     private long
224     start_xact_and_dosplit(
225     boolean attempt_to_reclaim_deleted_rows,
226     long leaf_pageno,
227     DataValueDescriptor[] scratch_template,
228     DataValueDescriptor[] rowToInsert,
229     int flag)
230         throws StandardException
231     {
232         TransactionManager split_xact = null;
233         OpenBTree split_open_btree = null;
234         ControlRow root = null;
235
236         // Get an internal transaction to be used for the split.
237 split_xact = this.init_open_user_scans.getInternalTransaction();
238
239         // open the btree again so that actions on it take place in the
240 // split_xact, don't get any locks in this transaction.
241
242         if (SanityManager.DEBUG)
243         {
244             if (((getOpenMode() & ContainerHandle.MODE_FORUPDATE) !=
245                                    ContainerHandle.MODE_FORUPDATE))
246             {
247                 SanityManager.THROWASSERT(
248                     "Container not opened with update should not cause split");
249             }
250         }
251
252
253         boolean do_split = true;
254         if (attempt_to_reclaim_deleted_rows)
255         {
256             // Get lock on base table.
257
258             ConglomerateController base_cc = null;
259
260             try
261             {
262                 base_cc =
263                     this.getConglomerate().lockTable(
264                         split_xact,
265                         (ContainerHandle.MODE_FORUPDATE |
266                          ContainerHandle.MODE_LOCK_NOWAIT),
267                         TransactionController.MODE_RECORD,
268                         TransactionController.ISOLATION_REPEATABLE_READ);
269             }
270             catch (StandardException se)
271             {
272                 // any error just don't try to reclaim deleted rows. The
273 // expected error is that we can't get the lock, which the
274 // current interface throws as a containerNotFound exception.
275 }
276
277             if (base_cc != null)
278             {
279                 // we got IX lock on the base table, so can try reclaim space.
280
281
282                 // We can only reclaim space by opening the btree in row lock
283 // mode. Table level lock row recovery is hard as we can't
284 // determine if the deleted rows we encounter have been
285 // deleted by our parent caller and have been committed or
286 // not. We will have to get those rows offline.
287 split_open_btree = new OpenBTree();
288                 split_open_btree.init(
289                     this.init_open_user_scans,
290                     split_xact,
291                     null, // open the container.
292 split_xact.getRawStoreXact(),
293                     false,
294                     (ContainerHandle.MODE_FORUPDATE |
295                      ContainerHandle.MODE_LOCK_NOWAIT),
296                     TransactionManager.MODE_RECORD,
297                     this.getConglomerate().getBtreeLockingPolicy(
298                         split_xact.getRawStoreXact(),
299                         TransactionController.MODE_RECORD,
300                         LockingPolicy.MODE_RECORD,
301                         TransactionController.ISOLATION_REPEATABLE_READ,
302                         (ConglomerateController) base_cc,
303                         split_open_btree),
304                     this.getConglomerate(),
305                     (LogicalUndo) null,
306                     (DynamicCompiledOpenConglomInfo) null);
307
308                 // don't split if we reclaim any rows.
309 do_split = !reclaim_deleted_rows(split_open_btree, leaf_pageno);
310
311                 split_open_btree.close();
312             }
313         }
314
315         long new_leaf_pageno = leaf_pageno;
316         if (do_split)
317         {
318             split_open_btree = new OpenBTree();
319             split_open_btree.init(
320                 this.init_open_user_scans,
321                 split_xact,
322                 null, // open the container.
323 split_xact.getRawStoreXact(),
324                 false,
325                 getOpenMode(), // use same mode this controller
326 // was opened with
327 TransactionManager.MODE_NONE,
328                 this.getConglomerate().getBtreeLockingPolicy(
329                     split_xact.getRawStoreXact(),
330                     this.init_lock_level,
331                     LockingPolicy.MODE_RECORD,
332                     TransactionController.ISOLATION_REPEATABLE_READ,
333                     (ConglomerateController) null, // no base row locks during split
334 split_open_btree),
335                 this.getConglomerate(),
336                 (LogicalUndo) null,
337                 (DynamicCompiledOpenConglomInfo) null);
338
339
340             // Get the root page back, and perform a split following the
341 // to-be-inserted key. The split releases the root page latch.
342 root = ControlRow.Get(split_open_btree, BTree.ROOTPAGEID);
343
344             if (SanityManager.DEBUG)
345                 SanityManager.ASSERT(root.page.isLatched());
346
347             new_leaf_pageno =
348                 root.splitFor(
349                     split_open_btree, scratch_template,
350                     null, rowToInsert, flag);
351
352             split_open_btree.close();
353         }
354
355         split_xact.commit();
356
357         split_xact.destroy();
358
359         return(new_leaf_pageno);
360     }
361
362     /**
363     Insert a row into the conglomerate.
364
365     @param rowToInsert The row to insert into the conglomerate. The stored
366     representations of the row's columns are copied into a new row
367     somewhere in the conglomerate.
368
369     @return Returns 0 if insert succeeded. Returns
370     ConglomerateController.ROWISDUPLICATE if conglomerate supports uniqueness
371     checks and has been created to disallow duplicates, and the row inserted
372     had key columns which were duplicate of a row already in the table. Other
373     insert failures will raise StandardException's.
374
375     @exception StandardException Standard exception policy.
376     **/
377     private int doIns(DataValueDescriptor[] rowToInsert)
378         throws StandardException
379     {
380         LeafControlRow targetleaf = null;
381         LeafControlRow save_targetleaf = null;
382         int insert_slot = 0;
383         int result_slot = 0;
384         int ret_val = 0;
385         boolean reclaim_deleted_rows_attempted = false;
386
387         if (scratch_template == null)
388             scratch_template = runtime_mem.get_template();
389
390         if (SanityManager.DEBUG)
391             this.isIndexableRowConsistent(rowToInsert);
392
393         // Create the objects needed for the insert.
394 // RESOLVE (mikem) - should we cache this in the controller?
395 SearchParameters sp =
396             new SearchParameters(
397                 rowToInsert,
398                 SearchParameters.POSITION_LEFT_OF_PARTIAL_KEY_MATCH,
399                 scratch_template, this, false);
400
401         // RowLocation column is in last column of template.
402 FetchDescriptor lock_fetch_desc =
403             RowUtil.getFetchDescriptorConstant(
404                 scratch_template.length - 1);
405         RowLocation lock_row_loc =
406             (RowLocation) scratch_template[scratch_template.length - 1];
407
408         // Row locking - lock the row being inserted.
409
410         if (get_insert_row_lock)
411         {
412             // I don't hold any latch yet so I can wait on this lock, so I
413 // don't care about return value from this call. This
414 // lock can only wait if the base table row was inserted in a
415 // separate transaction which never happens in sql tables, but
416 // does happen in the sparse indexes that synchronization builds.
417
418             this.getLockingPolicy().lockNonScanRow(
419                 this.getConglomerate(),
420                 (LeafControlRow) null,
421                 (LeafControlRow) null,
422                 rowToInsert,
423                 (ConglomerateController.LOCK_INS |
424                  ConglomerateController.LOCK_UPD));
425         }
426
427         while (true)
428         {
429             // Search the location at which the new row should be inserted.
430 if (SanityManager.DEBUG)
431                 SanityManager.ASSERT(this.container != null);
432
433             targetleaf = (LeafControlRow)
434                 ControlRow.Get(this, BTree.ROOTPAGEID).search(sp);
435
436
437             // Row locking - first lock row previous to row being inserted:
438 // o if (sp.resultExact) then the row must be deleted and
439 // we will be replacing it with the new row, lock
440 // the row before the slot as the previous key.
441 // o else
442 // we will be inserting after the current slot so
443 // lock the current slot as the previous key.
444 //
445 int slot_after_previous =
446                 (sp.resultExact ? sp.resultSlot : sp.resultSlot + 1);
447
448             boolean latch_released = false;
449
450             latch_released =
451                 !this.getLockingPolicy().lockNonScanPreviousRow(
452                     this.getConglomerate(),
453                     targetleaf,
454                     slot_after_previous,
455                     lock_fetch_desc,
456                     scratch_template,
457                     lock_row_loc,
458                     this,
459                     (ConglomerateController.LOCK_INS_PREVKEY |
460                      ConglomerateController.LOCK_UPD),
461                     TransactionManager.LOCK_INSTANT_DURATION);
462
463             // special test to see if latch release code works
464 if (SanityManager.DEBUG)
465             {
466                 latch_released =
467                     test_errors(
468                         this,
469                         "BTreeController_doIns", false,
470                         this.getLockingPolicy(),
471                         targetleaf, latch_released);
472             }
473
474             if (latch_released)
475             {
476                 // Had to release latch in order to get the lock, probably
477 // because of a forward scanner, research tree, and try again.
478 targetleaf = null;
479                 continue;
480             }
481
482             // If the row is there already, simply undelete it.
483 // The rationale for this is, since the index does
484 // not support duplicates, the only way we could
485 // find a duplicate is if we found a deleted row.
486 // If we could lock it, then no other transaction
487 // is deleting it; either this transaction deleted
488 // it earlier, or it's simply a row that the space
489 // reclaimer hasn't reclaimed yet.
490 // Since inserts are done directly (i.e., not to a
491 // location provided by a scan, we will see the
492 // deleted row).
493 if (sp.resultExact)
494             {
495                 result_slot = insert_slot = sp.resultSlot;
496
497                 if (this.getConglomerate().nKeyFields !=
498                         this.getConglomerate().nUniqueColumns)
499                 {
500                     // The key fields match, but not the row location. We
501 // must wait on the lock on the other row location before
502 // preceding, so as to serialize behind any work being done
503 // to the row as part of another transaction.
504
505                     latch_released =
506                         !this.getLockingPolicy().lockNonScanRowOnPage(
507                             this.getConglomerate(), targetleaf, insert_slot,
508                             lock_fetch_desc, scratch_template, lock_row_loc,
509                             ConglomerateController.LOCK_UPD);
510
511                     if (latch_released)
512                     {
513                         // Had to release latch in order to get the lock,
514 // probably to wait for deleting xact to commit or
515 // abort. Research tree, and try again.
516 targetleaf = null;
517                         continue;
518                     }
519                 }
520
521                 // The row better be deleted, or something is very wrong.
522
523                 if (!(targetleaf.page.isDeletedAtSlot(insert_slot)))
524                 {
525                     // attempt to insert a duplicate into the index.
526 ret_val = ConglomerateController.ROWISDUPLICATE;
527                     break;
528                 }
529                 else
530                 {
531                     if (this.getConglomerate().nKeyFields ==
532                         this.getConglomerate().nUniqueColumns)
533                     {
534                         // The row that we found deleted is exactly the new row.
535 targetleaf.page.deleteAtSlot(
536                             insert_slot, false, this.btree_undo);
537
538                         break;
539                     }
540                     else if (this.getConglomerate().nUniqueColumns ==
541                              (this.getConglomerate().nKeyFields - 1))
542                     {
543                         // The row that we found deleted has matching keys
544 // which form the unique key fields,
545 // but the nonkey fields may differ (for now the
546 // heap rowlocation is the only nonkey field
547 // allowed).
548
549                         // RESOLVE BT39 (mikem) - when/if heap row location
550 // is not fixed we must handle update failing for
551 // out of space and split if it does. For now
552 // if the update fails because of lack of space
553 // an exception is thrown and the statement is
554 // backed out. Should not happen very often.
555 targetleaf.page.deleteAtSlot(
556                             insert_slot, false, this.btree_undo);
557
558                         boolean update_succeeded = true;
559
560                         try
561                         {
562                             int rowloc_index =
563                                 this.getConglomerate().nKeyFields - 1;
564                             targetleaf.page.updateFieldAtSlot(
565                                 insert_slot, rowloc_index,
566                                 (DataValueDescriptor) RowUtil.getColumn(
567                                     rowToInsert,
568                                     (FormatableBitSet) null, rowloc_index),
569                                 this.btree_undo);
570                         }
571                         catch (StandardException se)
572                         {
573                             // check if the exception is for out of space
574 if (!se.getMessageId().equals(SQLState.DATA_NO_SPACE_FOR_RECORD))
575                             {
576                                 throw se;
577                             }
578
579                             // The statement exception is
580 // because the update failed for out of
581 // space (ie. the field got longer and there
582 // is no room on the page for the expanded
583 // field). Address this error by falling
584 // through the code and doing a split.
585 update_succeeded = false; // update failed.
586 targetleaf.page.deleteAtSlot(
587                                 insert_slot, true, this.btree_undo);
588                         }
589
590                         if (update_succeeded)
591                             break;
592                     }
593                     else
594                     {
595                         // Can only happen with non key fields in the btree.
596 throw(
597                             StandardException.newException(
598                                 SQLState.BTREE_UNIMPLEMENTED_FEATURE));
599                     }
600                 }
601             }
602             else if (targetleaf.page.recordCount() - 1 <
603                     this.getConglomerate().maxRowsPerPage)
604             {
605                 // The row wasn't there, so try to insert it
606 // on the page returned by the search.
607 insert_slot = sp.resultSlot + 1;
608                 result_slot = insert_slot + 1;
609
610                 // By default maxRowsPerPage is set to MAXINT, some tests
611 // set it small to cause splitting to happen quicker with
612 // less data.
613
614                 if (targetleaf.page.insertAtSlot(
615                         insert_slot,
616                         rowToInsert, (FormatableBitSet) null,
617                         this.btree_undo,
618                         Page.INSERT_DEFAULT,
619                         AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD) != null)
620                 {
621                     // Insert succeeded, so we're done.
622
623                     break;
624                 }
625
626                 // RESOLVE (mikem) - another long row issue.
627 // For now if a row does not fit on a page and there
628 // is only the control row on the page and at most one
629 // other row on the page, throw an exception
630
631                 if (targetleaf.page.recordCount() <= 2)
632                 {
633                     throw StandardException.newException(
634                             SQLState.BTREE_NO_SPACE_FOR_KEY);
635                 }
636
637                 // start splitting ...
638 }
639
640             
641             // Create some space by splitting pages.
642
643             // determine where in page/table row causing split would go
644 int flag = 0;
645             if (insert_slot == 1)
646             {
647                 flag |= ControlRow.SPLIT_FLAG_FIRST_ON_PAGE;
648                 if (targetleaf.isLeftmostLeaf())
649                     flag |= ControlRow.SPLIT_FLAG_FIRST_IN_TABLE;
650             }
651             else if (insert_slot == targetleaf.page.recordCount())
652             {
653                 flag |= ControlRow.SPLIT_FLAG_LAST_ON_PAGE;
654                 if (targetleaf.isRightmostLeaf())
655                     flag |= ControlRow.SPLIT_FLAG_LAST_IN_TABLE;
656             }
657
658             long targetleaf_pageno = targetleaf.page.getPageNumber();
659
660             if ((targetleaf.page.recordCount() -
661                  targetleaf.page.nonDeletedRecordCount()) <= 0)
662             {
663                 // Don't do reclaim work if there are no deleted records.
664 reclaim_deleted_rows_attempted = true;
665             }
666
667             BranchRow branchrow =
668                 BranchRow.createBranchRowFromOldLeafRow(
669                     rowToInsert, targetleaf_pageno);
670
671             // Release the target page because (a) it may change as a
672 // result of the split, (b) the latch ordering requires us
673 // to acquire latches from top to bottom, and (c) this
674 // loop should be done in a system transaction.
675 targetleaf.release();
676             targetleaf = null;
677
678             start_xact_and_dosplit(
679                 !reclaim_deleted_rows_attempted, targetleaf_pageno,
680                 scratch_template, branchrow.getRow(), flag);
681
682             // only attempt to reclaim deleted rows once, otherwise the
683 // split loop could loop forever, trying to reclaim a deleted
684 // row that was not committed.
685 reclaim_deleted_rows_attempted = true;
686
687             // RESOLVE (mikem) possible optimization could be to save
688 // split location and look there first, if this has
689 // already caused a split. Or even return a latched page
690 // from splitFor(). For now just execute the loop again
691 // searching the tree for somewhere to put the row.
692 }
693
694         // set in-memory hint of where last row on page was inserted.
695 targetleaf.last_search_result = result_slot;
696
697         // Check that page just updated is consistent.
698 if (SanityManager.DEBUG)
699         {
700             if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
701             {
702                 targetleaf.checkConsistency(this, null, true);
703             }
704         }
705
706         // Done with the target page.
707 targetleaf.release();
708         targetleaf = null;
709
710         // return the status about insert - 0 is ok, or duplicate status.
711 return(ret_val);
712     }
713
714     /**
715      * Just insert the row on the current page/slot if it fits.
716      * <p>
717      * @exception StandardException Standard exception policy.
718      **/
719     private boolean do_load_insert(
720     DataValueDescriptor[] rowToInsert,
721     LeafControlRow leaf,
722     int insert_slot)
723         throws StandardException
724     {
725         LeafControlRow old_leaf = null;
726         boolean row_inserted = false;
727         int num_rows_on_page = leaf.page.recordCount() - 1;
728
729
730         if (SanityManager.DEBUG)
731         {
732             SanityManager.ASSERT(insert_slot == leaf.page.recordCount());
733             SanityManager.ASSERT(
734                 leaf.getrightSiblingPageNumber() ==
735                     ContainerHandle.INVALID_PAGE_NUMBER);
736             this.isIndexableRowConsistent(rowToInsert);
737         }
738
739         if (num_rows_on_page < this.getConglomerate().maxRowsPerPage)
740         {
741             // By default maxRowsPerPage is set to MAXINT, some tests
742 // set it small to cause splitting to happen quicker with
743 // less data.
744
745             if (SanityManager.DEBUG)
746             {
747                 // Caller should have sorted and done duplicate checking.
748
749                 if (insert_slot > 1)
750                 {
751                     // verify that the row inserted is >= than previous row.
752 int compare_result =
753                         ControlRow.CompareIndexRowFromPageToKey(
754                             leaf,
755                             insert_slot - 1,
756                             scratch_template,
757                             rowToInsert,
758                             this.getConglomerate().nUniqueColumns,
759                             0,
760                             this.getConglomerate().ascDescInfo);
761                     
762                     if (compare_result >= 0)
763                     {
764                         // Rows must be presented in order, so the row we are
765 // inserting must always be greater than the previous
766 // row on the page.
767 SanityManager.THROWASSERT("result = " + compare_result);
768                     }
769                 }
770             }
771
772
773             if (leaf.page.insertAtSlot(
774                     insert_slot,
775                     rowToInsert,
776                     (FormatableBitSet) null,
777                     this.btree_undo,
778                     Page.INSERT_DEFAULT,
779                     AccessFactoryGlobals.BTREE_OVERFLOW_THRESHOLD) != null)
780             {
781                 // Insert succeeded, so we're done.
782 row_inserted = true;
783             }
784             else
785             {
786                 // RESOLVE (mikem) - another long row issue.
787 // For now if a row does not fit on a page and there
788 // is only the control row on the page and at most one
789 // other row on the page, throw an exception
790
791                 if (leaf.page.recordCount() <= 2)
792                 {
793                     throw StandardException.newException(
794                             SQLState.BTREE_NO_SPACE_FOR_KEY);
795                 }
796             }
797         }
798
799         // Check that page just updated is consistent.
800 if (SanityManager.DEBUG)
801         {
802             if (SanityManager.DEBUG_ON("enableBtreeConsistencyCheck"))
803             {
804                 leaf.checkConsistency(this, null, true);
805             }
806         }
807
808         return(row_inserted);
809     }
810
811     /**
812      * Create room to insert a row to the right of the largest key in table.
813      * <p>
814      * Perform a split pass on the tree which will move the largest key in
815      * leaf right to a new leaf, splitting parent branch pages as necessary.
816      *
817      * @exception StandardException Standard exception policy.
818      **/
819     private LeafControlRow do_load_split(
820     DataValueDescriptor[] rowToInsert,
821     LeafControlRow leaf)
822         throws StandardException
823     {
824         LeafControlRow new_leaf = null;
825
826         BranchRow branchrow =
827             BranchRow.createBranchRowFromOldLeafRow(
828                 rowToInsert, leaf.page.getPageNumber());
829
830         // Release the target page because (a) it may change as a
831 // result of the split, (b) the latch ordering requires us
832 // to acquire latches from top to bottom, and (c) this
833 // loop should be done in a system transaction.
834 long old_leafpage = leaf.page.getPageNumber();
835
836         leaf.release();
837         leaf = null;
838         
839         long new_leaf_pageno =
840             start_xact_and_dosplit(
841                 false /* don't try to reclaim deleted rows */,
842                 old_leafpage,
843                 scratch_template,
844                 branchrow.getRow(),
845                 (ControlRow.SPLIT_FLAG_LAST_ON_PAGE |
846                     ControlRow.SPLIT_FLAG_LAST_IN_TABLE));
847
848         new_leaf = (LeafControlRow) ControlRow.Get(this, new_leaf_pageno);
849
850         // The leaf must be the rightmost leaf in the table, the first time
851 // the root grows from leaf to branch it will be a leaf with many
852 // rows which will probably have to be split soon, after that it will
853 // be a leaf with only one row. The current algorithm requires that
854 // there be at least one row for duplicate checking (the duplicate
855 // checking code does not handle going left to the previous leaf) -
856 // this is the way the split at rightmost leaf row works currently.
857 if (SanityManager.DEBUG)
858         {
859             if (new_leaf.getrightSiblingPageNumber() !=
860                     ContainerHandle.INVALID_PAGE_NUMBER)
861             {
862                 SanityManager.THROWASSERT(
863                     "new_leaf.getrightSiblingPageNumber() = " +
864                         new_leaf.getrightSiblingPageNumber());
865             }
866             if (new_leaf.page.recordCount() <= 1)
867             {
868                 SanityManager.THROWASSERT(
869                     "new_leaf.page.recordCount() = " +
870                     new_leaf.page.recordCount());
871             }
872         }
873
874         return(new_leaf);
875     }
876
877
878
879     /*
880     ** public Methods of BTreeController
881     */
882
883     /**
884     Initialize the controller for use.
885     <p>
886     Any changes to this method will probably have to be reflected in close as
887     well.
888     <p>
889     Currently delegates to OpenBTree. If the btree controller ends up not
890     having any state of its own, we can remove this method (the VM will
891     dispatch to OpenBTree), gaining some small efficiency. For now, this
892     method remains for clarity.
893
894     @exception StandardException Standard exception policy.
895     **/
896     public void init(
897     TransactionManager xact_manager,
898     boolean hold,
899     ContainerHandle container,
900     Transaction rawtran,
901     int open_mode,
902     int lock_level,
903     BTreeLockingPolicy btree_locking_policy,
904     BTree conglomerate,
905     LogicalUndo undo,
906     StaticCompiledOpenConglomInfo static_info,
907     DynamicCompiledOpenConglomInfo dynamic_info)
908         throws StandardException
909     {
910         get_insert_row_lock =
911             ((open_mode &
912               TransactionController.OPENMODE_BASEROW_INSERT_LOCKED) == 0);
913
914         super.init(
915             xact_manager, xact_manager,
916             container, rawtran, hold, open_mode,
917             lock_level, btree_locking_policy,
918             conglomerate, undo, dynamic_info);
919     }
920
921     /*
922     ** Methods of ConglomerateController
923     */
924
925     /**
926     Close the conglomerate controller.
927     <p>
928     Any changes to this method will probably have to be reflected in close as
929     well.
930     <p>
931     Currently delegates to OpenBTree. If the btree controller ends up not
932     having any state of its own, we can remove this method (the VM will
933     dispatch to OpenBTree), gaining some small efficiency. For now, this
934     method remains for clarity.
935
936     @see ConglomerateController#close
937     **/
938     public void close()
939         throws StandardException
940     {
941         super.close();
942
943         // If we are closed due to catching an error in the middle of init,
944 // xact_manager may not be set yet.
945 if (getXactMgr() != null)
946             getXactMgr().closeMe(this);
947     }
948
949     /**
950      * Close conglomerate controller as part of terminating a transaction.
951      * <p>
952      * Use this call to close the conglomerate controller resources as part of
953      * committing or aborting a transaction. The normal close() routine may
954      * do some cleanup that is either unnecessary, or not correct due to the
955      * unknown condition of the controller following a transaction ending error.
956      * Use this call when closing all controllers as part of an abort of a
957      * transaction.
958      * <p)
959      * This call is meant to only be used internally by the Storage system,
960      * clients of the storage system should use the simple close() interface.
961      * <p>
962      * RESOLVE (mikem) - move this call to ConglomerateManager so it is
963      * obvious that non-access clients should not call this.
964      *
965      * @param closeHeldScan If true, means to close controller even if
966      * it has been opened to be kept opened
967      * across commit. This is
968      * used to close these controllers on abort.
969      *
970      * @return boolean indicating that the close has resulted in a real close
971      * of the controller. A held scan will return false if
972      * called by closeForEndTransaction(false), otherwise it
973      * will return true. A non-held scan will always return
974      * true.
975      *
976      * @exception StandardException Standard exception policy.
977      **/
978     public boolean closeForEndTransaction(boolean closeHeldScan)
979         throws StandardException
980     {
981         super.close();
982
983         if ((!getHold()) || closeHeldScan)
984         {
985             // If we are closed due to catching an error in the middle of init,
986 // xact_manager may not be set yet.
987 if (getXactMgr() != null)
988                 getXactMgr().closeMe(this);
989
990             return(true);
991         }
992         else
993         {
994             return(false);
995         }
996     }
997
998     /**
999     Insert a row into the conglomerate.
1000    @see ConglomerateController#insert
1001
1002    @param row The row to insert into the conglomerate. The stored
1003    representations of the row's columns are copied into a new row
1004    somewhere in the conglomerate.
1005
1006    @return Returns 0 if insert succeeded. Returns
1007    ConglomerateController.ROWISDUPLICATE if conglomerate supports uniqueness
1008    checks and has been created to disallow duplicates, and the row inserted
1009    had key columns which were duplicate of a row already in the table. Other
1010    insert failures will raise StandardException's.
1011
1012    @exception StandardException Standard exception policy.
1013    **/
1014    public int insert(DataValueDescriptor[] row)
1015         throws StandardException
1016    {
1017
1018        if (isClosed())
1019        {
1020            if (getHold())
1021            {
1022                reopen();
1023            }
1024            else
1025            {
1026                throw StandardException.newException(
1027                            SQLState.BTREE_IS_CLOSED,
1028                            new Long JavaDoc(err_containerid));
1029            }
1030        }
1031
1032        if (SanityManager.DEBUG)
1033        {
1034            SanityManager.ASSERT(this.container != null);
1035
1036            TemplateRow.checkPartialColumnTypes(
1037                this.getConglomerate().format_ids,
1038                (FormatableBitSet) null, (int []) null, row);
1039        }
1040
1041        return doIns(row);
1042    }
1043
1044    /**
1045    Return whether this is a keyed conglomerate.
1046    <p>
1047    All b-trees are keyed.
1048    @see ConglomerateController#isKeyed
1049    **/
1050    public boolean isKeyed()
1051    {
1052        return(true);
1053    }
1054
1055    /*
1056     * Request the system properties associated with a table.
1057     * <p>
1058     * Request the value of properties that are associated with a table. The
1059     * following properties can be requested:
1060     * derby.storage.pageSize
1061     * derby.storage.pageReservedSpace
1062     * derby.storage.minimumRecordSize
1063     * derby.storage.initialPages
1064     * <p>
1065     * To get the value of a particular property add it to the property list,
1066     * and on return the value of the property will be set to it's current
1067     * value. For example:
1068     *
1069     * get_prop(ConglomerateController cc)
1070     * {
1071     * Properties prop = new Properties();
1072     * prop.put("derby.storage.pageSize", "");
1073     * cc.getTableProperties(prop);
1074     *
1075     * System.out.println(
1076     * "table's page size = " +
1077     * prop.getProperty("derby.storage.pageSize");
1078     * }
1079     *
1080     * @param prop Property list to fill in.
1081     *
1082     * @exception StandardException Standard exception policy.
1083     **/
1084    public void getTableProperties(Properties JavaDoc prop)
1085        throws StandardException
1086    {
1087        if (this.container == null)
1088        {
1089            throw StandardException.newException(
1090                        SQLState.BTREE_IS_CLOSED,
1091                        new Long JavaDoc(err_containerid));
1092        }
1093
1094        container.getContainerProperties(prop);
1095
1096        return;
1097    }
1098
1099    /**
1100     * Request set of properties associated with a table.
1101     * <p>
1102     * Returns a property object containing all properties that the store
1103     * knows about, which are stored persistently by the store. This set
1104     * of properties may vary from implementation to implementation of the
1105     * store.
1106     * <p>
1107     * This call is meant to be used only for internal query of the properties
1108     * by jbms, for instance by language during bulk insert so that it can
1109     * create a new conglomerate which exactly matches the properties that
1110     * the original container was created with. This call should not be used
1111     * by the user interface to present properties to users as it may contain
1112     * properties that are meant to be internal to jbms. Some properties are
1113     * meant only to be specified by jbms code and not by users on the command
1114     * line.
1115     * <p>
1116     * Note that not all properties passed into createConglomerate() are stored
1117     * persistently, and that set may vary by store implementation.
1118     *
1119     * @param prop Property list to add properties to. If null, routine will
1120     * create a new Properties object, fill it in and return it.
1121     *
1122     * @exception StandardException Standard exception policy.
1123     **/
1124    public Properties JavaDoc getInternalTablePropertySet(Properties JavaDoc prop)
1125        throws StandardException
1126    {
1127        Properties JavaDoc ret_properties =
1128            ConglomerateUtil.createRawStorePropertySet(prop);
1129
1130        getTableProperties(ret_properties);
1131
1132        return(ret_properties);
1133    }
1134
1135    /**
1136     * Load rows from rowSource into the opened btree.
1137     * <p>
1138     * Efficiently load rows into the already opened btree. The btree must
1139     * be table locked, as no row locks will be requested by this routine.
1140     * On exit from this routine the conglomerate will be closed (on both
1141     * error or success).
1142     * <p>
1143     * This routine does an almost bottom up build of a btree. It assumes
1144     * all rows arrive in sorted order, and inserts them directly into the
1145     * next (to the right) spot in the current leaf until there is no space.
1146     * Then it calls the generic split code to add the next leaf (RESOLVE -
1147     * in the future we could optimize this to split bottom up rather than
1148     * top down for create index).
1149     *
1150     * @exception StandardException Standard exception policy. If conglomerate
1151     * supports uniqueness checks and has been
1152     * created to disallow duplicates, and one of
1153     * the rows being loaded had key columns which
1154     * were duplicate of a row already in the
1155     * conglomerate, then raise
1156     * SQLState.STORE_CONGLOMERATE_DUPLICATE_KEY_EXCEPTION.
1157     *
1158     * @see Conglomerate#load
1159     **/
1160    public long load(
1161    TransactionManager xact_manager,
1162    boolean createConglom,
1163    RowLocationRetRowSource rowSource)
1164         throws StandardException
1165    {
1166        long num_rows_loaded = 0;
1167
1168        if (SanityManager.DEBUG)
1169        {
1170            SanityManager.ASSERT(createConglom,
1171                "Cannot load a btree incrementally - it must either be entirely logged, or entirely not logged. Doesn't make sense to log only the allocation when one cannot guarantee to not touch any pre-existing pages");
1172        }
1173
1174        if (scratch_template == null)
1175            scratch_template = runtime_mem.get_template();
1176
1177        LeafControlRow current_leaf = null;
1178
1179        try
1180        {
1181            // Btree must just have been created and empty, so there must
1182 // be one root leaf page which is empty except for the control row.
1183 current_leaf =
1184                (LeafControlRow) ControlRow.Get(this, BTree.ROOTPAGEID);
1185            int current_insert_slot = 1;
1186
1187            if (SanityManager.DEBUG)
1188            {
1189                // root must be empty except for the control row.
1190 SanityManager.ASSERT(current_leaf.page.recordCount() == 1);
1191            }
1192           
1193            // now loop thru the row source and insert into the btree
1194 FormatableBitSet validColumns = rowSource.getValidColumns();
1195            
1196            // get the next row and its valid columns from the rowSource
1197 DataValueDescriptor[] row;
1198            while ((row = rowSource.getNextRowFromRowSource()) != null)
1199            {
1200                num_rows_loaded++;
1201
1202                if (SanityManager.DEBUG)
1203                {
1204                    SanityManager.ASSERT(
1205                        validColumns == null, "Does not support partial row");
1206                }
1207
1208                while (true)
1209                {
1210                    if (do_load_insert(row, current_leaf, current_insert_slot))
1211                    {
1212                        // row inserted successfully.
1213 break;
1214                    }
1215                    else
1216                    {
1217                        // if insert fails, do a split pass. There is an edge
1218 // case where multiple split passes are necessary if
1219 // branch splits are necessary, thus the loop. It is
1220 // most likely that only a single split pass will be
1221 // necessary.
1222 current_leaf = do_load_split(row, current_leaf);
1223
1224                        current_insert_slot = current_leaf.page.recordCount();
1225                    }
1226                }
1227                current_insert_slot++;
1228            }
1229
1230            current_leaf.release();
1231            current_leaf = null;
1232
1233            // Loading done, must flush all pages to disk since it is unlogged.
1234 if (!this.getConglomerate().isTemporary())
1235                container.flushContainer();
1236        }
1237        finally
1238        {
1239            this.close();
1240        }
1241
1242        return(num_rows_loaded);
1243    }
1244
1245    /*
1246    ** Methods of ConglomerateController which are not supported.
1247    */
1248
1249    /**
1250    Delete a row from the conglomerate.
1251    @see ConglomerateController#delete
1252
1253    @exception StandardException Standard exception policy.
1254    **/
1255    public boolean delete(RowLocation loc)
1256        throws StandardException
1257    {
1258        throw(StandardException.newException(
1259                SQLState.BTREE_UNIMPLEMENTED_FEATURE));
1260    }
1261
1262    /**
1263    Fetch the row at the given location.
1264    @see ConglomerateController#fetch
1265
1266    @exception StandardException Standard exception policy.
1267    **/
1268    public boolean fetch(
1269    RowLocation loc,
1270    DataValueDescriptor[] row,
1271    FormatableBitSet validColumns)
1272        throws StandardException
1273    {
1274        throw(StandardException.newException(
1275                SQLState.BTREE_UNIMPLEMENTED_FEATURE));
1276    }
1277
1278    /**
1279    Fetch the row at the given location.
1280    @see ConglomerateController#fetch
1281
1282    @exception StandardException Standard exception policy.
1283    **/
1284    public boolean fetch(
1285    RowLocation loc,
1286    DataValueDescriptor[] row,
1287    FormatableBitSet validColumns,
1288    boolean waitForLock)
1289        throws StandardException
1290    {
1291        throw(StandardException.newException(
1292                SQLState.BTREE_UNIMPLEMENTED_FEATURE));
1293    }
1294
1295    /**
1296    Insert a row into the conglomerate, and store its location in the
1297    provided template row location.
1298
1299    Unimplemented by btree.
1300
1301    @see ConglomerateController#insertAndFetchLocation
1302
1303    @exception StandardException Standard exception policy.
1304    **/
1305    public void insertAndFetchLocation(
1306    DataValueDescriptor[] row,
1307    RowLocation templateRowLocation)
1308        throws StandardException
1309    {
1310        throw StandardException.newException(
1311                SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1312    }
1313
1314    /**
1315    Return a row location object of the correct type to be
1316    used in calls to insertAndFetchLocation.
1317
1318    @see ConglomerateController#newRowLocationTemplate
1319
1320    @exception StandardException Standard exception policy.
1321    **/
1322    public RowLocation newRowLocationTemplate()
1323        throws StandardException
1324    {
1325        throw StandardException.newException(
1326                SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1327    }
1328
1329    /**
1330     * Lock the given row location.
1331     * <p>
1332     * Should only be called by access.
1333     * <p>
1334     * This call can be made on a ConglomerateController that was opened
1335     * for locking only.
1336     * <p>
1337     * RESOLVE (mikem) - move this call to ConglomerateManager so it is
1338     * obvious that non-access clients should not call this.
1339     *
1340     * @return true if lock was granted, only can be false if wait was false.
1341     *
1342     * @param loc The "RowLocation" which describes the exact row to lock.
1343     * @param wait Should the lock call wait to be granted?
1344     *
1345     * @exception StandardException Standard exception policy.
1346     **/
1347    public boolean lockRow(
1348    RowLocation loc,
1349    int lock_operation,
1350    boolean wait,
1351    int lock_duration)
1352        throws StandardException
1353    {
1354        throw StandardException.newException(
1355                SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1356    }
1357
1358    public boolean lockRow(
1359    long page_num,
1360    int record_id,
1361    int lock_operation,
1362    boolean wait,
1363    int lock_duration)
1364        throws StandardException
1365    {
1366        throw StandardException.newException(
1367                SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1368    }
1369
1370    public void unlockRowAfterRead(
1371    RowLocation loc,
1372    boolean forUpdate,
1373    boolean row_qualifies)
1374        throws StandardException
1375    {
1376        throw StandardException.newException(
1377                SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1378    }
1379
1380    /**
1381    Replace the entire row at the given location.
1382    @see ConglomerateController#replace
1383
1384    @exception StandardException Standard exception policy.
1385    **/
1386    public boolean replace(
1387    RowLocation loc,
1388    DataValueDescriptor[] row,
1389    FormatableBitSet validColumns)
1390        throws StandardException
1391    {
1392        throw StandardException.newException(
1393                SQLState.BTREE_UNIMPLEMENTED_FEATURE);
1394    }
1395}
1396
Popular Tags