You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@cassandra.apache.org by "Evgeny Ryabitskiy (Created) (JIRA)" <ji...@apache.org> on 2011/11/30 23:41:40 UTC
[jira] [Created] (CASSANDRA-3545) Fix very low Index Search
performance
Fix very low Index Search performance
-------------------------------------
Key: CASSANDRA-3545
URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
Project: Cassandra
Issue Type: Improvement
Components: Core
Affects Versions: 1.0.5, 1.0.4
Reporter: Evgeny Ryabitskiy
Priority: Critical
Fix For: 1.0.6
While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
After profiling I got this picture:
60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
I see several performance improvements:
1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
Also need local code changes.
3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
Need research and maybe this research was done.
4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
This solution requires huge code changes.
I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Evgeny Ryabitskiy (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Evgeny Ryabitskiy updated CASSANDRA-3545:
-----------------------------------------
Attachment: CASSANDRA-3545_v2.patch
New version of patch with fix of bugs and clear code.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: CASSANDRA-3545.patch, CASSANDRA-3545_v2.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Sylvain Lebresne (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sylvain Lebresne updated CASSANDRA-3545:
----------------------------------------
Attachment: 0002-cleanup.patch
0001-3545.patch
I agree with Jonathan than interning this inside the column family feels cleaner (and is more efficient). Attaching patch to do that (actually 2 patch, the second one does some cleaning of the comparator being given to lots of methods that don't care about it or can get it by other means). The patches are against trunk since I don't think we should push that into a stable release (independently of the actual implementation).
Note that this only applies to memtable, so this has probably much more impact on small benchmarks (where you insert and get immediately) than it will have in real life (it's still an improvement, don't get me wrong).
For the rest:
bq. 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
Unfortunately I don't see much way to do this any cleanly, without breaking badly the comparator abstraction.
bq. 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
It could be worth checking, though a quick search doesn't seem to return much interesting things. Finding a faster MD5 implementation would be convenient too, but the only thing I've found so far is http://twmacinta.com/myjava/fast_md5.php, which is unfortunately incompatible with our licence.
bq. 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator
Imo, that's the most promising option. I don't think that would be very complicated to do (I actually think it would be pretty easy but I may be forgetting a difficulty), but the annoying part will likely be how to deal with the upgrade/backward compatibility. I may give it a shot at some point though.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch, CASSANDRA-3545.patch, CASSANDRA-3545_v2.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (CASSANDRA-3545) Fix very low
Secondary Index performance
Posted by "Evgeny Ryabitskiy (Issue Comment Edited) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165308#comment-13165308 ]
Evgeny Ryabitskiy edited comment on CASSANDRA-3545 at 12/8/11 4:34 PM:
-----------------------------------------------------------------------
Sorry, I have to remove my patches to prevent claims from my employer.
I really doubt about legality of this claims, but still...
Glad to see that fixing is going.
was (Author: apparition):
Sorry, I have to remove my patches to prevent any claims from my employer.
I really doubt about legality of this claims, but still...
Glad to see that fixing is going.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Jonathan Ellis (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165306#comment-13165306 ]
Jonathan Ellis commented on CASSANDRA-3545:
-------------------------------------------
bq. Think about something faster that MD5 for hashing
I've suggested a MRP (MurmurRandomPartitioner) in the past... Murmur is substantially faster than MD5, especially v3 (CASSANDRA-2975), and with CASSANDRA-1034 done we don't need to rely on tokens being unique. Murmur gives quite good hash distribution, which is the main thing we care about for partitioning.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Evgeny Ryabitskiy (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165308#comment-13165308 ]
Evgeny Ryabitskiy commented on CASSANDRA-3545:
----------------------------------------------
Sorry, I have to remove my patches to prevent any claims from my employee.
I really doubt about legality of this claims, but still...
Glad to see that fixing is going.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Index Search
performance
Posted by "Evgeny Ryabitskiy (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Evgeny Ryabitskiy updated CASSANDRA-3545:
-----------------------------------------
Attachment: IndexSearchPerformance.png
Screen from profiler
> Fix very low Index Search performance
> -------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 1.0.4, 1.0.5
> Reporter: Evgeny Ryabitskiy
> Priority: Critical
> Fix For: 1.0.6
>
> Attachments: IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Evgeny Ryabitskiy (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Evgeny Ryabitskiy updated CASSANDRA-3545:
-----------------------------------------
Comment: was deleted
(was: Sorry, I have to remove my patches to prevent claims from my employer.
I really doubt about legality of this claims, but still...
Glad to see that fixing is going.)
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Assignee: Sylvain Lebresne
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Sylvain Lebresne (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165322#comment-13165322 ]
Sylvain Lebresne commented on CASSANDRA-3545:
---------------------------------------------
That has to do with the ListIterator used. When you do a reverse iteration (using previous), the first returned is the previous of the index taken by the iterator constructor. The +1 correct that. There is a unit test to check this is correct :)
I can add a comment (and fix the whitespace) during commit if there is no other remark/problem.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Evgeny Ryabitskiy (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Evgeny Ryabitskiy updated CASSANDRA-3545:
-----------------------------------------
Attachment: (was: IndexSearchPerformance.png)
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Evgeny Ryabitskiy (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Evgeny Ryabitskiy updated CASSANDRA-3545:
-----------------------------------------
Summary: Fix very low Secondary Index performance (was: Fix very low Index Search performance)
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 1.0.4, 1.0.5
> Reporter: Evgeny Ryabitskiy
> Priority: Critical
> Fix For: 1.0.6
>
> Attachments: CASSANDRA-3545.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Jonathan Ellis (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13161023#comment-13161023 ]
Jonathan Ellis commented on CASSANDRA-3545:
-------------------------------------------
Wow. That's a really clever workaround to working on a generic Collection iterator, that we happen to know is sorted. But it's also kind of complicated, and does a bunch of copying to a temporary collection that I'd prefer to avoid.
What if we added a getSortedColumns(byte[] startWith) overload to AbstractColumnContainer + ISortedColumns? Then each ISortedColumns implementation could implement that the straightforward way (for ArrayBacked, with Collections.binarySearch + subList; for the NavigableMap based ones, with tailMap).
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: CASSANDRA-3545.patch, CASSANDRA-3545_v2.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Jonathan Ellis (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165333#comment-13165333 ]
Jonathan Ellis commented on CASSANDRA-3545:
-------------------------------------------
bq. I can add a comment (and fix the whitespace) during commit if there is no other remark/problem.
SGTM.
(For the record, I think that's awful behavior on the part of ListIterator. :)
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Jonathan Ellis (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13161263#comment-13161263 ]
Jonathan Ellis commented on CASSANDRA-3545:
-------------------------------------------
bq. As a compromise I can suggest to apply this patch and add ticket for feature to cleanup code, move to binary search and new API in ISortedColumns.
I'm afraid that's typically not how we work. If we see a clearly better approach during review, which this qualifies as, then we'll wait for that before committing. Especially when the goal is to get into a stable branch.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: CASSANDRA-3545.patch, CASSANDRA-3545_v2.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Sylvain Lebresne (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165328#comment-13165328 ]
Sylvain Lebresne commented on CASSANDRA-3545:
---------------------------------------------
bq. I've suggested a MRP (MurmurRandomPartitioner) in the past...
That's a good idea. I've create CASSANDRA-3594 for that and CASSANDRA-3595 to explore the idea of use byte comparison for secondary indexes. So we can close this once once the 'better search' is committed.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Sylvain Lebresne (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Sylvain Lebresne updated CASSANDRA-3545:
----------------------------------------
Fix Version/s: (was: 1.0.6)
1.1
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Assignee: Sylvain Lebresne
> Fix For: 1.1
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Evgeny Ryabitskiy (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Evgeny Ryabitskiy updated CASSANDRA-3545:
-----------------------------------------
Attachment: (was: CASSANDRA-3545.patch)
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Jonathan Ellis (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Jonathan Ellis updated CASSANDRA-3545:
--------------------------------------
Priority: Major (was: Critical)
Affects Version/s: (was: 1.0.5)
(was: 1.0.4)
0.7.0
That sounds like a good place to start. Thanks for the analysis!
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: CASSANDRA-3545.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Hudson (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165407#comment-13165407 ]
Hudson commented on CASSANDRA-3545:
-----------------------------------
Integrated in Cassandra #1248 (See [https://builds.apache.org/job/Cassandra/1248/])
Improve memtable slice iteration performance
patch by slebresne; reviewed by jbellis for CASSANDRA-3545
slebresne : http://svn.apache.org/viewcvs.cgi/?root=Apache-SVN&view=rev&rev=1211999
Files :
* /cassandra/trunk/CHANGES.txt
* /cassandra/trunk/src/java/org/apache/cassandra/db/AbstractColumnContainer.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/ArrayBackedSortedColumns.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/CollationController.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/ColumnFamilyStore.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/ISortedColumns.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/Memtable.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/RowIteratorFactory.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/ThreadSafeSortedColumns.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/TreeMapBackedSortedColumns.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/filter/IFilter.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/filter/NamesQueryFilter.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/filter/QueryFilter.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/filter/SliceQueryFilter.java
* /cassandra/trunk/src/java/org/apache/cassandra/db/index/keys/KeysSearcher.java
* /cassandra/trunk/src/java/org/apache/cassandra/service/RowRepairResolver.java
* /cassandra/trunk/test/unit/org/apache/cassandra/db/ArrayBackedSortedColumnsTest.java
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Assignee: Sylvain Lebresne
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Evgeny Ryabitskiy (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13161161#comment-13161161 ]
Evgeny Ryabitskiy commented on CASSANDRA-3545:
----------------------------------------------
Yep, a little bit complicated. That is why it is fully covered by JUnits and comments.
Cobertura reports:
Classes in this File Line Coverage Branch Coverage Complexity
CollectionSearchUtil 91% 51/56 81% 36/44 6,5
There is NO bunch of copying to a temporary collection. There only one array of size sqrt(2*N), allocated once and coping is linear (same as iterating).
Let's analyze resources required for this search on N size collection:
Memory usage: == sqrt(2*N)
Array copping: <= N
Iteration ( next() execution): <= N
Compare (with MD5/Column comparator): <= sqrt(2*N)
I have solution (see patch 1) that perform iterating instead of allocation array, but it will require O(N^2) iterating in worst case.
In second patch memory usage is trade of for only one passage with iterator. Iteration can be slow, so array is much better.
You can check that for million columns search (pretty big row) it will be array with length: ~1440. Not too much for such huge search I think .
In case of 10k columns row it will be only 144 length array, with is pretty few.
About getSortedColumns(byte[] startWith):
Yes, it is another good solution. binarySearch is little bit faster in case you have indexed access to underling Columns (like List or Array).
But there is still one disadvantage: My patch is solving this problem and changes only few code lines
and this solution requires much more code changes. Lot's of code changes - low release stability. Sorry for sharing pain in JIRA tickets but 1.0.3 seems to be last stable release :(
As a compromise I can suggest to apply this patch and add ticket for feature to cleanup code, move to binary search and new API in ISortedColumns.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: CASSANDRA-3545.patch, CASSANDRA-3545_v2.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Issue Comment Edited] (CASSANDRA-3545) Fix very low
Secondary Index performance
Posted by "Evgeny Ryabitskiy (Issue Comment Edited) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165308#comment-13165308 ]
Evgeny Ryabitskiy edited comment on CASSANDRA-3545 at 12/8/11 4:33 PM:
-----------------------------------------------------------------------
Sorry, I have to remove my patches to prevent any claims from my employer.
I really doubt about legality of this claims, but still...
Glad to see that fixing is going.
was (Author: apparition):
Sorry, I have to remove my patches to prevent any claims from my employee.
I really doubt about legality of this claims, but still...
Glad to see that fixing is going.
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Evgeny Ryabitskiy (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Evgeny Ryabitskiy updated CASSANDRA-3545:
-----------------------------------------
Attachment: (was: CASSANDRA-3545_v2.patch)
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Updated] (CASSANDRA-3545) Fix very low Index Search
performance
Posted by "Evgeny Ryabitskiy (Updated) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Evgeny Ryabitskiy updated CASSANDRA-3545:
-----------------------------------------
Attachment: CASSANDRA-3545.patch
Patch for 1) solution, that is using fast algorithm for search element in sorted collection with much less compare usage.
Actually this solution can improve any ColumnSlice resolving.
> Fix very low Index Search performance
> -------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 1.0.4, 1.0.5
> Reporter: Evgeny Ryabitskiy
> Priority: Critical
> Fix For: 1.0.6
>
> Attachments: CASSANDRA-3545.patch, IndexSearchPerformance.png
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira
[jira] [Commented] (CASSANDRA-3545) Fix very low Secondary Index
performance
Posted by "Jonathan Ellis (Commented) (JIRA)" <ji...@apache.org>.
[ https://issues.apache.org/jira/browse/CASSANDRA-3545?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13165310#comment-13165310 ]
Jonathan Ellis commented on CASSANDRA-3545:
-------------------------------------------
{code}
. public Iterator<IColumn> iterator(ByteBuffer start)
{
final ListIterator<IColumn> iter = listIterator(size());
int idx = binarySearch(start);
if (idx < 0)
idx = -idx-1;
else if (reversed)
idx++;
return reversed ? reverseInternalIterator(idx) : listIterator(idx);
}
{code}
This doesn't look quite right to me, shouldn't an exact match (idx >= 0) be left alone for the reversed case too?
(Nit: whitespace around the - 1.)
> Fix very low Secondary Index performance
> ----------------------------------------
>
> Key: CASSANDRA-3545
> URL: https://issues.apache.org/jira/browse/CASSANDRA-3545
> Project: Cassandra
> Issue Type: Improvement
> Components: Core
> Affects Versions: 0.7.0
> Reporter: Evgeny Ryabitskiy
> Fix For: 1.0.6
>
> Attachments: 0001-3545.patch, 0002-cleanup.patch
>
>
> While performing index search + value filtering over large Index Row ( ~100k keys per index value) with chunks (size of 512-1024 keys) search time is about 8-12 seconds, which is very very low.
> After profiling I got this picture:
> 60% of search time is calculating MD5 hash with MessageDigester (Of cause it is because of RundomPartitioner).
> 33% of search time (half of all MD5 hash calculating time) is double calculating of MD5 for comparing two row keys while rotating Index row to startKey (when performing search query for next chunk).
> I see several performance improvements:
> 1) Use good algorithm to search startKey in sorted collection, that is faster then iteration over all keys. This solution is on first place because it simple, need only local code changes and should solve problem (increase search in multiple times).
> 2) Don't calculate MD5 hash for startKey every time. It's optimal to compute it once (so search will be twice faster).
> Also need local code changes.
> 3) Think about something faster that MD5 for hashing (like TigerRandomPartitioner with Tiger/128 hash).
> Need research and maybe this research was done.
> 4) Don't use Tokens (with MD5 hash for RandomPartitioner) for comparing and sorting keys in index rows. In index rows, keys can be stored and compared with simple Byte Comparator.
> This solution requires huge code changes.
> I'm going to start from first solution. Next improvements can be done with next tickets.
--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira