How does compound index help speed up query?

Question

Say we have a bunch of column in mysql table.

Latitude Longitude

Say we make an index (Latitude and Longitude)

Well, the index will sort by Latitude first and IF the Latitude is the same it'll sort by Longitude.

Something fishy should show up. Latitude is rarely, if ever, exactly the same.

Say we want to find all points whose Lat,Long is "in a box" How in the earth those indexes can be useful at all.

Note: I am trying to understand how indexing work. I am not trying to snobbishly say that compound index is stupid. Doesn't have to be full answer. Any pointing is fine.

More importantly, I am suspicious that a query will only use 1 index and the only way for a query to use multilpe index is to make compound index.

Answer 1

Indexes are in most cases a B-Tree structure (or some sort of). There are DBMS that supported different indexing types.

As you are talking about longitude/latitude PostgreSQL with it's GIST indexes come to mind. Oracle has Bitmap indexes in addition to the B-Tree indexes. I'm sure SQL Server and DB2 also have some special index types. And then there are full text indexes which make searching text very efficient.

A B-Tree index is very efficient in finding a specific value - think of a primary key index where all values are different. If the index only contains the PK column(s) (i.e. it is not a clustered index) then typically looking up a row by a specific PK values takes not more than (roughly) 3-4 IO operations (at least with Oracle). 2-3 to find the index block and an additional one to read the whole row. This gets more efficient if the index contains additional columns so that the lookup of the actual table row is not needed. The term for that is "covering index" or "index only retrieval".

Now for doing "range lookups" (e.g. where foo > 42) an index is very helpful as well as in most DBMS the index can also be scanned according to a predicate. Usually (again this highly depends on the DBMS) this is slightly less efficient than a direct lookup (again this also depends on the ability to do an "index only retrieval").

I don't know of any BMS which can not use more than one index in a query. Think a join on a PK and a FK column - depending on the data distribution the DBMS might use the index to find the parent rows (PK lookup) and the child rows (FK lookup).

But not all DBMS can use more than one index for the same table in a single query.

After all whether or not an index is being used or not depends on a lot of things.

I can highly recommend http://use-the-index-luke.com/ which is a very good introduction on indexing across all major DBMS.

DBMS specific information:

Oracle: http://docs.oracle.com/cd/E11882_01/server.112/e25789/indexiot.htm
PostgreSQL: http://www.postgresql.org/docs/current/static/indexes.html

Answer 2

Values don't need to be exact in order to use an index. In your particular example, a Range scan will limit the amount of data examined. An index on both bounds allows the data to be range limited on both axis.

A range scan operates conceptually similar to how you would look at a map. If you wanted to find the Washington Monument at Latitude: 38.889449 Longitude: -77.035232, you might begin your search by focusing on 30 to 40 Latitude and -70 to -80 Longitude. If you just looked at the Latitude you would have a lot more map to look at than when you look at both.

Here is a demonstration in Oracle.

> drop table t1
table T1 dropped.
> create table t1 as 
   (select dbms_random.value()*90 lat, dbms_random.value()*180 lon, level x 
      from dual connect by level<=5000)
table T1 created.
> create index x1 on t1 (lat)
index X1 created.
> set autotrace on explain
Autotrace Enabled
Displays the execution plan only.
> select * from t1 WHERE lat between 30 AND 40 AND lon BETWEEN 100 and 110
LAT LON X
--- --- -
30.3767657321169330960894098832402216675 104.010180757903737597756516124940719947 815 
30.5867860257718358281746146497630607937 105.59648614423201691420471610631375134 3308 
31.4193624839183326648532951557713565746 
...    
 25 rows selected 

Plan hash value: 3070918941

------------------------------------------------------------------------------------
| Id  | Operation                   | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |      |    25 |   975 |    12   (0)| 00:00:01 |
|*  1 |  TABLE ACCESS BY INDEX ROWID| T1   |    25 |   975 |    12   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | X1   |    23 |       |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   1 - filter("LON">=100 AND "LON"<=110)
   2 - access("LAT">=30 AND "LAT"<=40)

Note
-----
   - dynamic sampling used for this statement (level=2)

> set autotrace off
Autotrace Disabled
> create index x2 on t1 (lat,lon)
index X2 created.
> set autotrace on explain
Autotrace Enabled
Displays the execution plan only.
> select * from t1 WHERE lat between 30 AND 40 AND lon BETWEEN 100 and 110
LAT LON X
--- --- -
30.3767657321169330960894098832402216675 104.010180757903737597756516124940719947 815 
30.5867860257718358281746146497630607937 105.59648614423201691420471610631375134 3308 
31.4193624839183326648532951557713565746 
...    
 25 rows selected 

Plan hash value: 1153438080

------------------------------------------------------------------------------------
| Id  | Operation                   | Name | Rows  | Bytes | Cost (%CPU)| Time     |
------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |      |    25 |   975 |     3   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| T1   |    25 |   975 |     3   (0)| 00:00:01 |
|*  2 |   INDEX RANGE SCAN          | X2   |     1 |       |     2   (0)| 00:00:01 |
------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("LAT">=30 AND "LON">=100 AND "LAT"<=40 AND "LON"<=110)
       filter("LON">=100 AND "LON"<=110)

Note
-----
   - dynamic sampling used for this statement (level=2)

> set autotrace off
Autotrace Disabled