Time complexity of query of MongoDB array vs object

Question

I'm trying to understand how I should best set up a schema in MongoDB.

What I have is a many-to-many relationship, like this:

Playlist Document:

{
  _id: '111',
  title: 'some playlist',
  songs: ['222', '333']
}

Song Document:

{
  _id: '222',
  album: 'some album',
  artist: 'some artist'
}

A playlist can reference many songs and a song can belong to many playlists.

If I were to construct a query that searched the playlist collection for playlists containing a particular song id, wouldn't that be a terribly slow operation? It seems like the DB would need to iterate through the songs array of every single playlist to figure out what playlists to return.

The solution I arrived at is to construct my playlist documents like this:

{
  _id: '111',
  title: 'some playlist',
  songs: {
    222: true,
    333: true
  }
}

It seems like this is how I should do it (to me), and yet just about every example I can find uses arrays. Does Mongo do some magic internally when using arrays that makes them as fast to use as objects?

Bastien Léonard · Accepted Answer · 2015-02-19 21:54:30Z

2

If I were to construct a query that searched the playlist collection for playlists containing a particular song id, wouldn't that be a terribly slow operation? It seems like the DB would need to iterate through the songs array of every single playlist to figure out what playlists to return.

MongoDB supports indexes on fields that are arrays: http://docs.mongodb.org/manual/core/index-multikey/

From the documentation, it seems that MongoDB has no problem avoiding collection scans when searching for a specific value of an array, using the index instead.

answered Feb 19, 2015 at 21:54

Bastien Léonard

62.1k20 gold badges81 silver badges95 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Tom O'Connell Over a year ago

Thanks, I'd seen that kind of query done on arrays before but couldn't find info on how it actually worked.

Collectives™ on Stack Overflow

Time complexity of query of MongoDB array vs object

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related