Database Reference
In-Depth Information
Ace
Acme
Acme
Acme
Acme
Biz
Ox12
OxFF
OxA1
Ox0B
Ox1C
OxEE
7999
7500
7500
7500
7499
7499
OxFF
Ox12
OxEE
OxA1
Ox0B
Ox1C
Traversal
Figure 7.2 Single-key
index traversal
Manufacturers and disk locations
Sale prices and disk locations
used. The query optimizer will pick the more efficient of the two, but neither will give
you an ideal result. To satisfy the query using these indexes, you'd have to traverse
each structure separately and then grab the list of disk locations that match and calcu-
late their union. MongoDB doesn't support this right now, in part because using a
compound index for this case is so much more efficient.
A compound index is a single index where each entry is composed of more than
one key. If you were to build a compound-key index on manufacturer and price, the
ordered representation would look like what you see in figure 7.3.
In order to fulfill your query, the query optimizer only need find the first entry in
the index where manufacturer is Acme and price is $75.00. From there, the results
can be retrieved with a simple scan of the successive index entries, stopping when the
value of manufacturer no longer equals Acme .
There are two things you should notice about the way this index and query work
together. The first is that the order of the index's keys matters. If you had declared a
compound index where price was the first key and manufacturer the second, then
your query would've been far less efficient. Hard to see why? Take a look at the struc-
ture of the entries in such an index in figure 7.4.
Keys must be compared in the order in which they appear. Unfortunately, this
index doesn't provide an easy way to jump to all the Acme products. So the only way to
fulfill your query would be to look at every product whose price is less than $75.00 and
then select only those products made by Acme. To put this in perspective, imagine
that your collection had a million products, all priced under $100.00 and evenly dis-
tributed by price. Under these circumstances, fulfilling your query would require that
you scan 750,000 index entries. By contrast, using the original compound index,
Ace - 8000
Acme - 7999
Acme - 7500
Acme - 7499
Acme - 7499
Biz - 8999
Ox12
OxFF
OxA1
Ox0B
Ox1C
OxEE
7999 - Acme
OxFF
7500 - Ace
OxEE
Traversal
7500 - Acme
Ox12
Traversal
7500 - Biz
7499 - Acme
7499 - Acme
OxA1
Ox0B
Ox1C
Manufacturers and prices, with disk locations
Prices and manufacturers, with disk locations
Figure 7.4 A compound-key index with the
keys reversed
Figure 7.3
Compound-key index traversal
 
Search WWH ::




Custom Search