You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@couchdb.apache.org by "Jan Lehnardt (JIRA)" <ji...@apache.org> on 2009/01/23 22:05:59 UTC
[jira] Created: (COUCHDB-224) Improve B-Tree implementation
Improve B-Tree implementation
-----------------------------
Key: COUCHDB-224
URL: https://issues.apache.org/jira/browse/COUCHDB-224
Project: CouchDB
Issue Type: Improvement
Components: Database Core
Affects Versions: 0.8
Reporter: Jan Lehnardt
Fix For: 0.9
Also, the current Btree implementation isn't completely self balanacing. It
misses a balancing condition, partially for efficiency (it's an expensive
balancing operation), and for expediency. It was easier to not implement it and
gets the general case perormance boost.
The thing about this is, the btree code can remain as is if the indexing
compaction just recopies the map values (and back indexes) and recomputes the
reduction values. That's a very simple design, however, if the btree is
completely self balancing, then the btree can be copied on a node by node basis,
instead of a value by value basis, and the reduction values need not be
recomputed all. This will make the compaction significantly faster overall.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COUCHDB-224) Improve B-Tree implementation
Posted by "Jan Lehnardt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COUCHDB-224?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jan Lehnardt updated COUCHDB-224:
---------------------------------
Fix Version/s: (was: 0.10)
0.11
bump to 0.11
> Improve B-Tree implementation
> -----------------------------
>
> Key: COUCHDB-224
> URL: https://issues.apache.org/jira/browse/COUCHDB-224
> Project: CouchDB
> Issue Type: Improvement
> Components: Database Core
> Affects Versions: 0.8
> Reporter: Jan Lehnardt
> Assignee: Damien Katz
> Priority: Blocker
> Fix For: 0.11
>
>
> Also, the current Btree implementation isn't completely self balanacing. It
> misses a balancing condition, partially for efficiency (it's an expensive
> balancing operation), and for expediency. It was easier to not implement it and
> gets the general case perormance boost.
> The thing about this is, the btree code can remain as is if the indexing
> compaction just recopies the map values (and back indexes) and recomputes the
> reduction values. That's a very simple design, however, if the btree is
> completely self balancing, then the btree can be copied on a node by node basis,
> instead of a value by value basis, and the reduction values need not be
> recomputed all. This will make the compaction significantly faster overall.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COUCHDB-224) Improve B-Tree implementation
Posted by "Jan Lehnardt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COUCHDB-224?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jan Lehnardt updated COUCHDB-224:
---------------------------------
Priority: Major (was: Blocker)
Fix Version/s: (was: 0.11)
1.0
bumping to 1.1. for what it's worth, Robert Newson did some practical benchmaks and didn't see any performance issues with uncompacted databases. removing blocker status, too.
> Improve B-Tree implementation
> -----------------------------
>
> Key: COUCHDB-224
> URL: https://issues.apache.org/jira/browse/COUCHDB-224
> Project: CouchDB
> Issue Type: Improvement
> Components: Database Core
> Affects Versions: 0.8
> Reporter: Jan Lehnardt
> Assignee: Damien Katz
> Fix For: 1.0
>
>
> Also, the current Btree implementation isn't completely self balanacing. It
> misses a balancing condition, partially for efficiency (it's an expensive
> balancing operation), and for expediency. It was easier to not implement it and
> gets the general case perormance boost.
> The thing about this is, the btree code can remain as is if the indexing
> compaction just recopies the map values (and back indexes) and recomputes the
> reduction values. That's a very simple design, however, if the btree is
> completely self balancing, then the btree can be copied on a node by node basis,
> instead of a value by value basis, and the reduction values need not be
> recomputed all. This will make the compaction significantly faster overall.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COUCHDB-224) Improve B-Tree implementation
Posted by "Paul Joseph Davis (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COUCHDB-224?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Paul Joseph Davis updated COUCHDB-224:
--------------------------------------
Skill Level: Committers Level (Medium to Hard)
> Improve B-Tree implementation
> -----------------------------
>
> Key: COUCHDB-224
> URL: https://issues.apache.org/jira/browse/COUCHDB-224
> Project: CouchDB
> Issue Type: Improvement
> Components: Database Core
> Affects Versions: 0.8
> Reporter: Jan Lehnardt
> Assignee: Damien Katz
> Fix For: 1.0.2
>
>
> Also, the current Btree implementation isn't completely self balanacing. It
> misses a balancing condition, partially for efficiency (it's an expensive
> balancing operation), and for expediency. It was easier to not implement it and
> gets the general case perormance boost.
> The thing about this is, the btree code can remain as is if the indexing
> compaction just recopies the map values (and back indexes) and recomputes the
> reduction values. That's a very simple design, however, if the btree is
> completely self balancing, then the btree can be copied on a node by node basis,
> instead of a value by value basis, and the reduction values need not be
> recomputed all. This will make the compaction significantly faster overall.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COUCHDB-224) Improve B-Tree implementation
Posted by "Noah Slater (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COUCHDB-224?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Noah Slater updated COUCHDB-224:
--------------------------------
Fix Version/s: 1.0.1
(was: 1.0)
> Improve B-Tree implementation
> -----------------------------
>
> Key: COUCHDB-224
> URL: https://issues.apache.org/jira/browse/COUCHDB-224
> Project: CouchDB
> Issue Type: Improvement
> Components: Database Core
> Affects Versions: 0.8
> Reporter: Jan Lehnardt
> Assignee: Damien Katz
> Fix For: 1.0.1
>
>
> Also, the current Btree implementation isn't completely self balanacing. It
> misses a balancing condition, partially for efficiency (it's an expensive
> balancing operation), and for expediency. It was easier to not implement it and
> gets the general case perormance boost.
> The thing about this is, the btree code can remain as is if the indexing
> compaction just recopies the map values (and back indexes) and recomputes the
> reduction values. That's a very simple design, however, if the btree is
> completely self balancing, then the btree can be copied on a node by node basis,
> instead of a value by value basis, and the reduction values need not be
> recomputed all. This will make the compaction significantly faster overall.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COUCHDB-224) Improve B-Tree implementation
Posted by "Jan Lehnardt (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COUCHDB-224?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jan Lehnardt updated COUCHDB-224:
---------------------------------
Priority: Blocker (was: Major)
Description:
Also, the current Btree implementation isn't completely self balanacing. It
misses a balancing condition, partially for efficiency (it's an expensive
balancing operation), and for expediency. It was easier to not implement it and
gets the general case perormance boost.
The thing about this is, the btree code can remain as is if the indexing
compaction just recopies the map values (and back indexes) and recomputes the
reduction values. That's a very simple design, however, if the btree is
completely self balancing, then the btree can be copied on a node by node basis,
instead of a value by value basis, and the reduction values need not be
recomputed all. This will make the compaction significantly faster overall.
was:
Also, the current Btree implementation isn't completely self balanacing. It
misses a balancing condition, partially for efficiency (it's an expensive
balancing operation), and for expediency. It was easier to not implement it and
gets the general case perormance boost.
The thing about this is, the btree code can remain as is if the indexing
compaction just recopies the map values (and back indexes) and recomputes the
reduction values. That's a very simple design, however, if the btree is
completely self balancing, then the btree can be copied on a node by node basis,
instead of a value by value basis, and the reduction values need not be
recomputed all. This will make the compaction significantly faster overall.
Set blocking for 0.9 because I believe this will break the database file format.
> Improve B-Tree implementation
> -----------------------------
>
> Key: COUCHDB-224
> URL: https://issues.apache.org/jira/browse/COUCHDB-224
> Project: CouchDB
> Issue Type: Improvement
> Components: Database Core
> Affects Versions: 0.8
> Reporter: Jan Lehnardt
> Priority: Blocker
> Fix For: 0.9
>
>
> Also, the current Btree implementation isn't completely self balanacing. It
> misses a balancing condition, partially for efficiency (it's an expensive
> balancing operation), and for expediency. It was easier to not implement it and
> gets the general case perormance boost.
> The thing about this is, the btree code can remain as is if the indexing
> compaction just recopies the map values (and back indexes) and recomputes the
> reduction values. That's a very simple design, however, if the btree is
> completely self balancing, then the btree can be copied on a node by node basis,
> instead of a value by value basis, and the reduction values need not be
> recomputed all. This will make the compaction significantly faster overall.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COUCHDB-224) Improve B-Tree implementation
Posted by "Chris Anderson (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COUCHDB-224?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Chris Anderson updated COUCHDB-224:
-----------------------------------
Fix Version/s: (was: 0.9)
0.10
Assignee: Damien Katz
pushed to 0.10 as it's not necessary for the upcoming release
> Improve B-Tree implementation
> -----------------------------
>
> Key: COUCHDB-224
> URL: https://issues.apache.org/jira/browse/COUCHDB-224
> Project: CouchDB
> Issue Type: Improvement
> Components: Database Core
> Affects Versions: 0.8
> Reporter: Jan Lehnardt
> Assignee: Damien Katz
> Priority: Blocker
> Fix For: 0.10
>
>
> Also, the current Btree implementation isn't completely self balanacing. It
> misses a balancing condition, partially for efficiency (it's an expensive
> balancing operation), and for expediency. It was easier to not implement it and
> gets the general case perormance boost.
> The thing about this is, the btree code can remain as is if the indexing
> compaction just recopies the map values (and back indexes) and recomputes the
> reduction values. That's a very simple design, however, if the btree is
> completely self balancing, then the btree can be copied on a node by node basis,
> instead of a value by value basis, and the reduction values need not be
> recomputed all. This will make the compaction significantly faster overall.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.
[jira] Updated: (COUCHDB-224) Improve B-Tree implementation
Posted by "Noah Slater (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/COUCHDB-224?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Noah Slater updated COUCHDB-224:
--------------------------------
Fix Version/s: 1.0.2
(was: 1.0.1)
> Improve B-Tree implementation
> -----------------------------
>
> Key: COUCHDB-224
> URL: https://issues.apache.org/jira/browse/COUCHDB-224
> Project: CouchDB
> Issue Type: Improvement
> Components: Database Core
> Affects Versions: 0.8
> Reporter: Jan Lehnardt
> Assignee: Damien Katz
> Fix For: 1.0.2
>
>
> Also, the current Btree implementation isn't completely self balanacing. It
> misses a balancing condition, partially for efficiency (it's an expensive
> balancing operation), and for expediency. It was easier to not implement it and
> gets the general case perormance boost.
> The thing about this is, the btree code can remain as is if the indexing
> compaction just recopies the map values (and back indexes) and recomputes the
> reduction values. That's a very simple design, however, if the btree is
> completely self balancing, then the btree can be copied on a node by node basis,
> instead of a value by value basis, and the reduction values need not be
> recomputed all. This will make the compaction significantly faster overall.
--
This message is automatically generated by JIRA.
-
You can reply to this email to add a comment to the issue online.