This Bugzilla instance is a read-only archive of historic NetBeans bug reports. To report a bug in NetBeans please follow the project's instructions for reporting issues.

Bug 52090 - btree slow for multivalued indexes
Summary: btree slow for multivalued indexes
Status: CLOSED FIXED
Alias: None
Product: java
Classification: Unclassified
Component: Unsupported (show other bugs)
Version: 4.x
Hardware: All All
: P2 blocker (vote)
Assignee: issues@java
URL:
Keywords: PERFORMANCE
Depends on:
Blocks:
 
Reported: 2004-12-06 08:22 UTC by Petr Nejedly
Modified: 2006-03-24 10:29 UTC (History)
1 user (show)

See Also:
Issue Type: DEFECT
Exception Reporter:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this bug.
Description Petr Nejedly 2004-12-06 08:22:12 UTC 
The Btree implementation does (in searchPage) only
partial binary search, stopping immediatelly on a
matching entry.
This means it rarely finds the leftmost entry for
multivalued indexes, but it needs to. This is
"solved" by iterating previous entries one-by-one,
while they still match the key instead of simply
doing full binary search in the page (which would
guarantee the leftmost entry in the page).

Unfortunately this is not enough, as the sequence
of entries with the same key can span several pages.

Here comes in another bug which causes that pages
fully populated with single key are not ordered
by their prevPage/nextPage order in their parent page.
Comment 1 Daniel Prusa 2004-12-07 09:34:26 UTC 
Checking in BtreePage.java;
/cvs/mdr/src/org/netbeans/mdr/persistence/btreeimpl/btreeindex/BtreePage.java,v
 <--  BtreePage.java
new revision: 1.12; previous revision: 1.11
Comment 2 Petr Nejedly 2004-12-07 15:47:30 UTC 
The number of calls to BtreePage.getPrevious and
ShrinkablePage.compare was reduced heavily.