Your opinion matters! Please fill in the InfoQ Survey!

Indexes for LINQ

| by Jonathan Allen Follow 257 Followers on Apr 30, 2007. Estimated reading time: 1 minute |

A note to our readers: As per your request we have developed a set of features that allow you to reduce the noise, while not losing sight of anything that is important. Get email and web notifications by choosing the topics you are interested in.

When a LINQ expression directly targets a database, the DLINQ provider has full access to the database's indexes. But LINQ is not only about databases, it can also target XML or even simple object collections. For larger queries, the lack of indexing may become an issue.

In order to address the issue, Aaron Erickson has created a product called Index for Objects or i4o. This project, which is open source, is downright trivial to use. One merely has to add an Indexable attribute to properties that should be indexed. When the objects are subsequently placed in an IndexableCollection, the indexes are automatically generated.

The magic occurs at runtime when calls to the Where and Join extension methods are made. i4o evaluates the expression tree and, if appropriate, replaces the for-each loops with an index lookup.

This technique may end up only being applicable when using very large, in memory object collections. In tests against collections of 1 million objects, i4o resulted in speed improvements of roughly two orders of magnitude.

Being a new project, there are still pending issues. Some are trivial and will be done soon, like adding support for removing objects from collections or supporting BindingList. The harder ones include how to handle updates to objects in an indexed collection. The objects do not 'know' they are in a collection, adding support for INotifyPropertyChanged to every indexed class is tedious, and it probably is not possible to use some sort of Aspect Orientated Programming technique to inject the necessary event hooks.

The project in binary and source code format can be downloaded from CodePlex. For more information about i4o, or to make suggestions for future enhancements, you can read Aaron Erickson's blog.

Rate this Article

Adoption Stage

Hello stranger!

You need to Register an InfoQ account or or login to post comments. But there's so much more behind being registered.

Get the most out of the InfoQ experience.

Tell us what you think

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread
Community comments

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread

Allowed html: a,b,br,blockquote,i,li,pre,u,ul,p

Email me replies to any of my messages in this thread


Login to InfoQ to interact with what matters most to you.

Recover your password...


Follow your favorite topics and editors

Quick overview of most important highlights in the industry and on the site.


More signal, less noise

Build your own feed by choosing topics you want to read about and editors you want to hear from.


Stay up-to-date

Set up your notifications and don't miss out on content that matters to you