How to speed up my spatial search in SQL Server?

I have a database with about 1 million places (coordinates) placed out on the Earth. My web site has a map (Google Maps) that lets users find those places by zooming in on the map.

The database is a SQL Server 2008 R2 and I have created a spatial column for the location of each marker.

Problem is I need to cut down query time drastically. An example is a map area covering a few square kilometers which returns maybe 20000 points - that query takes about 6 seconds of CPU time on a very fast quad core processor.

I contruct a shape out of the visible area of the map, like this:

DECLARE @shape GEOGRAPHY = geography::STGeomFromText('POLYGON((' +
CONVERT(varchar, @ne_lng) + ' ' + CONVERT(varchar, @sw_lat) + ', ' +
CONVERT(varchar, @ne_lng) + ' ' + CONVERT(varchar, @ne_lat) + ', ' + 
CONVERT(varchar, @sw_lng) + ' ' + CONVERT(varchar, @ne_lat) + ', ' +
CONVERT(varchar, @sw_lng) + ' ' + CONVERT(varchar, @sw_lat) + ', ' +
CONVERT(varchar, @ne_lng) + ' ' + CONVERT(varchar, @sw_lat) + '))', 4326)

And the query then makes the selection based on this:

@shape.STIntersects(MyTable.StartPoint) = 1

a) I have made sure the index is really used (checked the actual execution plan). Also tried with index hints. b) I have also tried querying by pick开发者_开发问答ing everything in a specific distance from the center of the map. It's a little bit better, but it still takes many seconds.

The spatial index looks like this:

CREATE SPATIAL INDEX [IX_MyTable_Spatial] ON [dbo].[MyTable] 
(
    [MyPoint]
)USING  GEOGRAPHY_GRID 
WITH (
GRIDS =(LEVEL_1 = MEDIUM,LEVEL_2 = MEDIUM,LEVEL_3 = MEDIUM,LEVEL_4 = MEDIUM), 
CELLS_PER_OBJECT = 16, PAD_INDEX  = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ALLOW_ROW_LOCKS  = ON, ALLOW_PAGE_LOCKS  = ON) ON [PRIMARY]
GO

What can be done to dramatically improve this search? Should I have a geometry-based index instead? Or are there other settings for the index that are badly chosen (they are the default ones)?

EDIT------------------

I ended up not using SQL Server Spatial indexes at all. Since I only need to do simple searches within a square of a map, using decimal data type and normal <= and >= search is so much faster, and totally enough for the purpose. Thanks everyone for helping me!

SQL server 2008 (and later) supports SPATIAL indexes.

See: http://technet.microsoft.com/en-us/library/bb895373.aspx
for a list of functions that can be used whilst still being able to use an index.
If you use any other function TSQL will not be able to use an index, killing performance.

See: http://technet.microsoft.com/en-us/library/bb964712.aspx
For general info on spatial indexes.

Have you tried using an "Index hint"? For Example:

SELECT * FROM [dbo].[TABLENAME] WITH(INDEX( [INDEX_NAME] ))
WHERE 
[TABLENAME].StartPoint.STIntersects(@shape) = 1