Comments (11)
Here is one proposed solution:
NaturalKeyTable
doesn't use row ID andAutoUInt64Table
under the hoodIndex
stores keys asconcat(indexKeyBytes, primaryKeyBytes, len(primaryKeyBytes)[0])
primaryKeyBytes
are limited to 255 bytes so that length can into a single byte at the end of the key- this should allow prefix scans to happen efficiently whether or not primary key is actually
uint64
or[]byte
because the single byte length at the end allows for splitting the indexKeyBytes and primaryKeyBytes
UInt64Index
stores keys asconcat(indexKeyUInt64, primaryKeyBytes)
so that we know that the index key is always a fixed 8 bytes
What do you think of this solution @alpe and @ethanfrey?
from cosmos-modules.
I think this is a good step, but there are other gas inefficiencies in the design as well.
Such as storing secondary indexes as many (key, primary key) -> nil
entries, rather than one key -> []primary key
from cosmos-modules.
Such as storing secondary indexes as many (key, primary key) -> nil entries, rather than one key -> []primary key
IMHO we get away cheaper in terms of gas with @aaronc index design. We pay only the "flat" fees on Read, Write, Delete an not the byte size fees of the payload.
For example.
-
Add new secondary index "foo"
A) Storing a new index key "foo00000001" costs = 2000 (WriteCostFlat)
B) For a new entry in "[]primary key" "foo" it is "2000 + 8*30 (WriteCostPerByte)" = 2240 -
Add another to secondary index "foo" for different rowID
A) Storing as new index key "foo00000002" costs = 2000 (WriteCostFlat)
B) For an additional entry in "[]primary key" "foo" it is "1000 (ReadCostFlat) +8 * 3(ReadCostPerByte) +2000 + 16 * 30 (WriteCostPerByte)" = 3504 -
Delete operations
A) 1000 DeleteCost
B) 1000 (ReadCostFlat) +8 * 3(ReadCostPerByte) + 1000 DeleteCost when last element otherwise + 2000 +x *30 (WriteCostPerByte) -
Has operations
A) 1000 HasCost
B) 1000 (ReadCostFlat) +x * 3(ReadCostPerByte) -
Iterations over prefix
A) 30 IterNextCostFlat * x (entries)
B) 30 IterNextCostFlat + x *8 * 3(ReadCostPerByte)
Here variant B is slightly more efficient. If we would consider pagination with a limited result set then option B is only more efficient with small sets.
from cosmos-modules.
Thanks for the detailed analysis @alpe! So it sounds like from what you're saying that the concat(indexKeyBytes, primaryKeyBytes, len(primaryKeyBytes)[0])
is a reasonable approach generally? I would have expected key -> []primary key
to be more efficient generally for small sets but it seems like because of gas, that's only the case for prefix iteration which is a bit surprising.
Anyway, if you think it makes sense, then let's move forward with this design.
I do want to note that we could get past the limitation of 255 bytes for primary keys by encoding a uvarint in reverse starting from the back of the index key, basically concat(indexKeyBytes, primaryKeyBytes, reverse(uvarint(len(primaryKeyBytes))))
. This would be a bit more complex to implement but would prevent surprises in edge cases.
from cosmos-modules.
I think concat(indexKeyBytes, primaryKeyBytes, len(primaryKeyBytes)[0])
could be used to optimize natural key table indexes.
I am not sure if saving 33 gas (1123 vs 1090 for a GroupMember
index entry) on Read on a secondary index is worth the effort and complexity. It is of course more with Create, Delete.
After the analysis above I did a small optimization for Read so that we have (153 vs 120 for a GroupMember
index entry)
from cosmos-modules.
I am not sure if saving 33 gas (1123 vs 1090 for a
GroupMember
index entry) on Read on a secondary index is worth the effort and complexity. It is of course more with Create, Delete.
I'm sorry, what is the context for 1123 vs 1090?
from cosmos-modules.
sorry, context is access via natural key index or by rowID on table:
_, err = k.groupMemberTable.GetOne(gCtx, m.NaturalKey(), &loaded)
= 1123 gas_, err = k.groupMemberTable.autoTable.GetOne(gCtx, 1, &loaded)
= 1090 gas
To be fair, this only about READ. Create (+2000) and Delete(+1000) come with extra costs that we could avoid by storing the natural key in the table and not the index.
See "price list" KVGasConfig
from cosmos-modules.
@alpe how does this impact the proposed redesign of Index
keys?
from cosmos-modules.
how does this impact the proposed redesign of
Index
keys?
It does not impact the redesign. It was an example that there are potential improvements on gas consumption that can have impact with the current design. Just about priorities.
from cosmos-modules.
@alpe is this still being worked on, or can we consider this closed?
from cosmos-modules.
The concerns were addressed by the redesign PR. We can close this
from cosmos-modules.
Related Issues (20)
- Implement ability to withdraw a proposal
- Implement queries for group module
- Implement sdk events for all messages
- Drop amino support
- Implement ThresholdDecisionPolicy
- Implement Genesis IO for sdk Module spec
- Implement MsgVote
- Support custom decision policies HOT 1
- Master branch - project cleanup
- Execute proposal on submission already
- Follow up on orm.Persistence validation
- Add CLI client support HOT 2
- Add REST support
- Group comment or admin changes should not affect a running proposals
- Document proposal execution and edge cases
- Update groups module to use Any in proto encoding
- Upgrade groups module to Stargate HOT 1
- Group decision policy interface
- Group weights may be token balances HOT 3
- group membership defined by fungible token HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cosmos-modules.