{"action":"created","issue":{"url":"https://api.github.com/repos/astropy/astropy/issues/3915","labels_url":"https://api.github.com/repos/astropy/astropy/issues/3915/labels{/name}","comments_url":"https://api.github.com/repos/astropy/astropy/issues/3915/comments","events_url":"https://api.github.com/repos/astropy/astropy/issues/3915/events","html_url":"https://github.com/astropy/astropy/pull/3915","id":92909057,"number":3915,"title":"Indexing system for Table","user":{"login":"mdmueller","id":6729036,"avatar_url":"https://avatars.githubusercontent.com/u/6729036?v=3","gravatar_id":"","url":"https://api.github.com/users/mdmueller","html_url":"https://github.com/mdmueller","followers_url":"https://api.github.com/users/mdmueller/followers","following_url":"https://api.github.com/users/mdmueller/following{/other_user}","gists_url":"https://api.github.com/users/mdmueller/gists{/gist_id}","starred_url":"https://api.github.com/users/mdmueller/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/mdmueller/subscriptions","organizations_url":"https://api.github.com/users/mdmueller/orgs","repos_url":"https://api.github.com/users/mdmueller/repos","events_url":"https://api.github.com/users/mdmueller/events{/privacy}","received_events_url":"https://api.github.com/users/mdmueller/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/astropy/astropy/labels/Enhancement","name":"Enhancement","color":"fad8c7"},{"url":"https://api.github.com/repos/astropy/astropy/labels/table","name":"table","color":"c7def8"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":29,"created_at":"2015-07-03T16:52:28Z","updated_at":"2015-08-21T18:25:54Z","closed_at":null,"pull_request":{"url":"https://api.github.com/repos/astropy/astropy/pulls/3915","html_url":"https://github.com/astropy/astropy/pull/3915","diff_url":"https://github.com/astropy/astropy/pull/3915.diff","patch_url":"https://github.com/astropy/astropy/pull/3915.patch"},"body":"This is a first pass at a new system allowing the `Table` class to hold indices, both for improved grouping performance and for searching by column values. Indices are stored in columns rather than the full table, and indices in turn store a reference to the column(s) they act on, so that composite indices work correctly. Some parts of this PR are final and some are still unfinished, so any comments/suggestions would be great.\r\n\r\n### Complete\r\n* The `Index` class, which provides a wrapper around the sorting engine\r\n* Modifications to `Column`, which ensure that indices are modified as appropriate when a `Column` is modified\r\n* Modifications to `Table`\r\n\r\n### Unfinished\r\n* ~~The `Table.where()` method, particularly finishing up the searching syntax~~\r\n* ~~The actual sorting engine. I have bintrees (which provides fast binary search tree and red-black tree implementations) as an optional dependency, which is replaced by a pure-Python binary search tree class if bintrees isn't present. I also began work on a pure-Python red-black tree and a sorted array class, both unfinished.~~\r\nExperimental parts of this PR have been removed.\r\n\r\n@mdboom @taldcroft "},"comment":{"url":"https://api.github.com/repos/astropy/astropy/issues/comments/133523559","html_url":"https://github.com/astropy/astropy/pull/3915#issuecomment-133523559","issue_url":"https://api.github.com/repos/astropy/astropy/issues/3915","id":133523559,"user":{"login":"embray","id":676149,"avatar_url":"https://avatars.githubusercontent.com/u/676149?v=3","gravatar_id":"","url":"https://api.github.com/users/embray","html_url":"https://github.com/embray","followers_url":"https://api.github.com/users/embray/followers","following_url":"https://api.github.com/users/embray/following{/other_user}","gists_url":"https://api.github.com/users/embray/gists{/gist_id}","starred_url":"https://api.github.com/users/embray/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/embray/subscriptions","organizations_url":"https://api.github.com/users/embray/orgs","repos_url":"https://api.github.com/users/embray/repos","events_url":"https://api.github.com/users/embray/events{/privacy}","received_events_url":"https://api.github.com/users/embray/received_events","type":"User","site_admin":false},"created_at":"2015-08-21T18:25:54Z","updated_at":"2015-08-21T18:25:54Z","body":"@mdmueller Much of the performance impact of overriding `__getitem__` in a Python class comes merely from the fact that it requires a dict lookup every time you index the column (or any other object that overrides `__getitem__`).  That is, a lot of the slowdown comes from looking up the `__getitem__` implementation itself (independent of how that implementation works, which may or may not be slow).\r\n\r\nBecause Numpy arrays are built-in classes (that is, they're implemented in C), running `array[idx]` involves nothing more than a few pointer dereferences: `Py_TYPE(obj)->tp_as_mapping->mp_subscript`\r\n\r\nSubclasses of `ndarray` will automatically get the `ndarray` class's slots copied, so by default `__getitem__` on subclasses is just as fast.  However, if a subclass *overrides` `__getitem__`, then you get the laborious process of lookup in the class dict, along with all the trappings of normal attribute access like descriptor support.  This alone results in a roughly 8x slowdown even for a trivial `__getitem__` *implementation*.\r\n\r\nOverriding `__getitem__` *could* still end up being a problem even if it's written in C like in #4075, but it depends on what we're doing in the implementation.  If we can pass through to the basic implementation for the simple case of a single scalar lookup with only a few checks then the performance impact is negligible.\r\n\r\nFor something like taking a slice, however, the impact is not completely negligible if we decide to have it copy the indices by default.  I don't know if that matters or not though--I don't think we typically care as much about the performance impact on slice."}}