Isaac @ MSDN

StreamInsight 2012 on Academy Live

2012-03-08T10:30:00Z

Hi Folks,

As part of the SQL Server 2012 launch, I've contributed a presentation on StreamInsight 2.0, which is available either on TechNet or the Microsoft Virtual Academy.

You can get the code associated with the video here code.

Enjoy!
-Isaac

Map Projections

2011-11-14T18:43:25Z

Cute!

Although I’m guessing that people who really are into maps have a slightly higher view of Mercator than he implies.

Cheers,
-Isaac

PASS Wrap-Up

2011-10-17T20:46:24Z

Hi Folks,

I just wrapped up my talk the 2011 PASS Summit. Here are a few quick thoughts:

StreamInsight seems like a technology that could benefit a large number of customers, for a large number of scenarios. But relatively few people even know what SI can do. So although the title of my talks was, “What’s new in Microsoft StreamInsight?”, I turned it into more of a dev-ish, “What the Heck is StreamInsight?” This seemed successful: people seemed attentive; I got a lot of good questions; very few people waked out—all good signs. I’ll see what the session feedback looks like, and if you have any comments, please paste them here or shoot me an email. I’ll be talking again at Connections, and want to use all the feedback I can to refine that talk.

I promised folks at the talk that I’d post my code. I’ve cleaned it up a little—added comments and some copyright info to save myself from our legal department—but it really is the code I used during the talk. Hopefully both of these will show up with the talk on the PASS website, but you can also download my code here.

One final thought: I’ve underestimated how hard it would be to get back in the blogging groove. But I’ll keep trying.

Cheers,
-Isaac

Alastair on Spatiotemporal with StreamInsight

2011-08-05T18:16:00Z

Alastair Aitchison has started a series on doing spatiotemporal analysis using StreamInsight and the SQL Server spatial library over on his blog. I’ll certainly be watching how he makes out.

To answer one question he asks in his post: StreamInsight doesn’t require SQL Server Compact, but if you use it for you use it for your metadata provider, then the server metadata (applications, queries, and the like) will be persisted across restarts. This is required if you want to use resiliency for fairly obvious reasons.

Cheers,
-Isaac

Introducing Checkpointing in StreamInsight 1.2

2011-07-25T07:00:00Z

Hi Folks,

As I mentioned some a few posts ago, I recently made a move to the StreamInsight team. Well, we’ve just released the new version, StreamInsight 1.2, so it’s time to start talking about what we’ve been up to.

One of the big features in the new version is resiliency, which helps you build highly available systems that use StreamInsight. This post gives a high-level, no-code overview of what this functionality does and how it can be used. More detailed posts will follow.

To motivate the feature, consider a few use cases:

You have a query that consumes sensor data—say the temperature of a machine—and computes the average temperature over the last day. It’s not the end of the world if StreamInsight were to miss a few minutes of data: the missed events will likely have little impact on the overall average. But if these missed events were caused by an outage, you do care (a) that your app comes back up quickly, (b) that you don’t lose the substantial state that was built up for the aggregation, and (c) that the results you get when SI comes back up are close to what you would have gotten had SI not gone down.

You have a query that consumes Twitter data and sends you email every time someone mentions Justin Bieber. For this query, you have the same requirement (a) for speedy recovery as above, but (b) and (c) are no longer sufficient: you really don’t want to miss an important alert should StreamInsight go down. On the other hand, you don't mind getting duplicate alerts. I.e., you want the same events you would have gotten without the outage—perhaps with some duplicates.

You have a query that consumes stock price data, and produces trade events based on some secret algorithm. Now you have all of the requirements from the Bieber-bot—fast recovery, equivalent events—but now it could be catastrophic if you got duplicate trades. I.e., you want completely equivalent outputs whether or not there was an outage.

The form of resiliency introduced in StreamInsight 1.2 allows SI to take and restore checkpoints. A checkpoint is a serialized form of all of the internal state SI keeps for a query. When SI restarts, it will automatically restart a previously-running query and restore its state from the checkpoint, effectively putting the query at a known point when the checkpoint was taken.

You can control when checkpoints are taken: take them more frequently and you’ll lose less in a crash; take them less frequently and you’ll keep the impact on the system low. Let’s consider how this would be used in our first use case:

Your query is happily chugging along, and you’re asking the system to take a checkpoint every five minutes. At some time—say 12:59—some doofus trips on the power cord of the machine and brings it down. Realizing what he’s done, he plugs it back in and restarts everything. At 1:05 everything’s ready and he restarts StreamInsight, which reads back the latest checkpoint from 12:55 and is ready to start accepting events again at 1:07.

In this case, SI was down from 12:59 to 1:07, and all events that should have been received during this time were lost. In addition, all events received between 12:55 and 12:59 were effectively lost as well, since they weren’t recorded in the last checkpoint before the system went down. These lost input events may cause missed output events, and can also affect aggregate results that overlap the outage. Still, you’re happy because the system is back up, you’ve only lost 12 minutes of data, and your long-term aggregates are roughly intact.

Perhaps all of this is fine for a silly temperature reading, but what if someone were to tweet a Bieber sighting during the outage? To avoid missing this critical information, StreamInsight needs some help: something needs to keep track of the events that occurred during the outage, as well as those that occurred before the outage but after the last checkpoint, and be ready to send them along when SI comes back up.

That something is the input adapter—or more properly, whatever the input adapter is connected to. In other words, there has to be a component sitting in front of StreamInsight that keeps track of recent events and can replay them for SI. And this component has to be independent and highly available as well.

If we have this in place, we’re ready to tackle our second use case:

Your query is happily Biebering along, taking checkpoints every minute, but you have a historian sitting in front of your query. This historian is pulling tweets from Twitter and persisting them before sending them on to StreamInsight. As before, our doofus trips over the cable at 12:59 and restarts StreamInsight at 1:05. But now as part of its recovery routine, SI will ask its input adapter to replay the event it’s missed and the historian will guarantee that SI will see all that it has missed since 12:55 when it took its last checkpoint.

And this is great: StreamInsight came back, and you haven’t missed a thing. But you notice something funny: the report of Justin’s new coif that issued at 12:57 came through twice. Once before the outage, and once after. Why? Because SI forgot that it issued that event before the outage, and when the events replayed, it got issued again.

And that’s not bad. Unless events have consequences—which is certainly the case with stock trades. To eliminate these duplicates, StreamInsight needs a little more help, this time on the output. As SI produces events, the output adapter—again, more properly, whatever the output adapter is connected to—has to remember them.

When StreamInsight comes back up after an outage, it will essentially tell its output adapters the last time it remembers. It also guarantees that every event that it produced after that time will be produced again. Since the output adapter knows what these events were, it can remove the duplicates when it sees them instead of acting on them. And this is what we need in our third use case:

Your query is happily trading away, taking checkpoints every minute. You also have a historian in front of the query recoding stock prices, and a historian on the end recording trades. As before our doofus—who we have somehow failed to fire—trips over the cable at 12:59 and restarts things at 1:05. During recovery, StreamInsight gets the input to replay all stock info since 12:55, so no input is missed. It also notifies its output that all trades that happened between 12:55 and the outage will be sent again, so when the duplicate trades are issued, the output adapter just drops them on the floor.

And now we have full stream equivalence. You don’t miss a trade, and you don’t get any duplicates.

Hopefully this gives a feel of what’s possible with checkpointing. I’ll have more to say on specifics over the next few weeks. In the meantime, be sure to pick up the release and take a look at the documentation. And there’s a full end-to-end demo available on CodePlex as well.

Cheers,
-Isaac

Collation Hell

2011-05-05T16:00:00Z

Hi Folks,

I’m going to pick up from last time and discuss another major problem with moving databases from one place to another: collations. Some people will have never run into collation issues because they have a consistent collation across all of their environments: they have the same collation on all of their instances, and all databases share that same collation as well.

Others are not so lucky.

Let me illustrate the problem with a few concrete examples. The most common example people encounter involves mismatches between their database collation and the collation used by tempdb. For the purposes of this post, we’ll assume that the tempdb collation is the same as the instance collation. This is not strictly true, but is almost always the case.

Here’s the typical way this rears its ugly head. A developer creates a table and a temp table, and joins the two:

CREATE TABLE foo (x varchar(100))
GO
CREATE TABLE #bar (y varchar(100))
GO

-- ...

SELECT foo.x, #bar.y
FROM foo JOIN #bar ON foo.x = #bar.y

When the developer created this, the instance and database had the same collation, say SQL_Latin1_General_CP1_CI_AS. But at some later point, an administrator moved the database to a new instance with a different collation. It doesn’t matter what collation this is, but for purposes of this example, let’s say it was Turkish_100_CI_AI. Now when we create the temp table and perform the join, things don’t go so well:

CREATE TABLE #bar (y varchar(100))
GO

-- ...

SELECT foo.x, #bar.y
FROM foo JOIN #bar ON foo.x = #bar.y

This results in:

Msg 468, Level 16, State 9, Line 5
Cannot resolve the collation conflict between "Turkish_100_CI_AI" and 
   "SQL_Latin1_General_CP1_CI_AS" in the equal to operation.

To get around this, the developer has to rewrite things slightly:

CREATE TABLE #bar (y varchar(100) COLLATE DATABASE_DEFAULT)
GO

 -- ...

SELECT foo.x, #bar.y
FROM foo JOIN #bar ON foo.x = #bar.y

Now things work as we’d like: the COLLATE DATABASE_DEFAULT statement ensures that the collation used for the data in the temp table will match the database, regardless of the instance collation. But it’s unlikely that the developer would have proactively done this, and it’s a pain to do in any case.

This example is fairly common. I want to emphasize that the next example is not: I have never seen or heard of this happening in the wild; the example was invented by one of our developers to illustrate what could go wrong. I would be very interested to hear if this has ever occurred for real.

Alright: let’s blow something up!

I am going to generate some collation-dependent behavior that manifests in a very bad way. To do this, I first need to identify some collation-dependent behavior, and for this example, I’m going to exploit a difference between Latin1_General and Turkish collations. I’ve chosen this because it’s kind of fun, but you can engineer similar behavior just case sensitivity. Also, to understand what’s going on, remember that variable binding is done using the instance collation. I.e., unlike most languages where there is only one way for variables to bind, in T-SQL you can change this by changing the instance collation.

So let’s play with the Turkish “I”. Imagine I have variables named @I and @İ. (Note that the first one is a usual “I”, but the second one has a dot.) These are different variables in both Latin1_General and Turkish collations. But what happens if I refer to @i (a little “i” with a dot) and my instance collation is case insensitive? It depends:

In Latin1_General, @i binds to @I.
In Turkish, @i binds to @İ.

My next step is to amplify this difference a bit:

CREATE FUNCTION snafu (@x int) RETURNS int
WITH SCHEMABINDING
AS
BEGIN
    DECLARE @I int = 1
    DECLARE @İ int = 2
    RETURN @i * @x
END

This function exhibits behavior that is sensitive to the instance collation. On an instance with a case-insensitive Latin1_General collation, it’s the identity function on integers: for each input @x, it just returns @x times one. But on an instance with a case-insensitive Turkish collation, it doubles its input.

Now we can do something truly horrible. Imagine that we have our database on an instance with a Latin1_General collation, and we create:

CREATE TABLE baz (a int, b as dbo.snafu(a) PERSISTED)
GO

If we insert a few values and try a couple simple commands:

INSERT INTO baz VALUES (1), (2), (3)
GO

SELECT a, b
FROM baz
GO

DBCC CHECKTABLE (baz)
GO

We get back:

a           b
----------- -----------
1           1
2           2
3           3

(3 row(s) affected)

DBCC results for 'baz'.
There are 3 rows in 1 pages for object "baz".
DBCC execution completed. If DBCC printed error messages, 
   contact your system administrator.

Everything looks fine. But now if we move the database to our Turkish instance and rerun the DBCC we get:

Msg 2537, Level 16, State 106, Line 1
Table error: object ID 885578193, index ID 0, partition ID 72057594039173120, 
   alloc unit ID 72057594043498496 (type In-row data), page (1:223), row 0. 
   The record check (valid computed column) failed. The values are 2 and 0.
Msg 2537, Level 16, State 106, Line 1
Table error: object ID 885578193, index ID 0, partition ID 72057594039173120,
   alloc unit ID 72057594043498496 (type In-row data), page (1:223), row 1.
   The record check (valid computed column) failed. The values are 2 and 0.
Msg 2537, Level 16, State 106, Line 1
Table error: object ID 885578193, index ID 0, partition ID 72057594039173120, 
   alloc unit ID 72057594043498496 (type In-row data), page (1:223), row 2. 
   The record check (valid computed column) failed. The values are 2 and 0.
DBCC results for 'baz'.
There are 3 rows in 1 pages for object "baz".
CHECKTABLE found 0 allocation errors and 3 consistency errors in table 'baz' 
   (object ID 885578193).
repair_allow_data_loss is the minimum repair level for the errors found by 
   DBCC CHECKTABLE (foo.dbo.baz).
DBCC execution completed. If DBCC printed error messages, contact your system 
   administrator.

Ack! Our table is corrupted! What’s going on? We’ve persisted values of a function that exhibits a dependency on the instance collation, and these values are no longer valid on the new instance. We can illustrate this another way by inserting the same values again and looking at the result:

INSERT INTO baz VALUES (1), (2), (3)
GO

SELECT a, b
FROM baz
GO

a           b
----------- -----------
1           1
2           2
3           3
1           2
2           4
3           6

(6 row(s) affected)

The values in column b should be dependent solely on those in column a. They aren’t.

The takeaway from this nightmare is that databases in SQL Server exhibit a strong dependency on the instance collation. There are other instance-level settings that have similar bindings, but collations are probably the most pervasive.

As with authentication, we’ve addressed this with contained databases. But before moving on to solutions, I want to step back and frame this problem a bit more generally. And that will be my next post.

Cheers,
-Isaac

The Database Shuffle

2011-04-20T16:56:00Z

Hi Folks,

As I mentioned in my previous post, I recently moved from my old home in the SQL Server engine to the StreamInsight team. As I continue to ramp up here, I want to take a few posts to talk about what I was working on back in the engine: the contained database.

To illustrate the problem contained databases are intended to solve, let’s consider a simple scenario: I take a database D that lives on server S, detach it, and attach it to server T:

This is one example of database movement, but there are many movement scenarios—recovery, upgrade, load balancing, consolidation, moves to production—and many movement techniques—backup/restore, detach/attach, mirroring. But how well do these techniques satisfy the scenarios?

In a word: poorly. As an illustrative example, let’s take a look at what happens with authentication.

SQL Server security is a little complex, but for our purposes it’s enough to consider two core artifacts: logins and users. Logins are instance-level objects (stored in master) and users are database-level objects (stored in the user database). Each of these are responsible for authorization in their respective domains, i.e., used to grant permissions at the instance and at the database respectively. But only logins are used for authentication. So in order to even log on to the server you have to have a login.

Users and logins are associated with each other through a matching identifier called a SID, and in order for a person to connect to and use a database, he must have a user in the target database and matching login on the instance. And here’s where our problem comes from: while users are stored in and move with the database, logins are not and do not. They’re left behind:

The result of this is that someone who could connect to D when it lived on S may no longer be able to do so when it moves to T because their login is missing. This is reparable, of course: you just need to manually add the required logins to the new instance. It’s also not easily automatable, since the target instance may already have a different login with the same name, which would cause a collision.

Were this only a problem for logins, we’d have one nit to work around. But of course it isn’t. The same applies to any other server-scoped object on which the database depends: agent jobs, error messages, linked servers, etc.

I’m going to blow my punch line here: we solved this the authentication problem with contained databases. But before moving on to the details, I’m going to touch on some more subtle problems. In particular, collations. Stay tuned.

Cheers,
-Isaac

It’s Alive!

2011-03-30T23:46:13Z

Hi Folks,

Many years ago I kicked up this blog. It started with a trickle of general posts on SQL Server programmability topics. As our spatial support took off, it was quickly consumed by spatial-related posts.

And then it languished…

…and now its back. Let me quickly explain via a quick Q&A with myself:

Where did you go?

Through the 2008 release, I was the program manager for spatial. I led spatial projects, thought spatial thoughts, and dreamt spatial… well only occasionally. In any case, as we ramped up the next release, I started working on what we now call “contained databases”. Since these weren’t public yet, I couldn’t say too much to say about them. And since I wasn’t involved so much in spatial, I didn’t have so much to say there, either.

Why are you back?

After spending six years in the SQL Server engine, I’ve taken a new job. I am now a program manager with StreamInsight. And with this new adventure comes a renewed vigor on the blogging front.

What is this blog about now?

Since most of what I’m working on is centered around StreamInsight, StreamInsight would be a good guess. I’ll probably have a thing or two to say about contained databases as well. And heck, I may even do some spatial.

Stick around and we’ll find out.

Cheers,
-Isaac

Filter: One Odd Duck

2010-03-04T15:57:00Z

Hi Folks,

Over at his blog, Nicklas Avéns questions the behavior of Filter. He's right: Filter is a little odd. It is also very much by design.

Before we look at filter, let's review the data flow for a typical spatial query. A spatial selection generally has two internal components: a primary filter, which is designed to be fast, but which may produce extra results; and a secondary filter, which is slower, but only works to remove the false positives passed by the primary filter.

The primary filter is accomplished by using the spatial index. The secondary filter requires calls to actual geometry routines, and will be much more expensive. But the secondary filter also guarantees index-independent—and geometrically correct—results.

Without an index, most operations will just skip the primary filter. The result is slow, but returns the same results as the full primary–secondary pathway.

Filter is designed for a pretty common, but somewhat odd use case. Imagine that you want to display a portion of a map: you want to retrieve from the database those objects that would show on the map, but if you happen to retrieve a few extras you don't care—they'll just fall off the display.

In other words, false positives are okay. In fact, they're often preferred, because the overall performance is can be much better if you can skip the expensive geometry operations and instead render some additional objects.

So we added Filter, which simply skips the secondary filter and gives you the quick index-only results.

But what if you don't have an index? We had two choices, either (a) return an error, or (b) revert to STIntersects. Note that both of these options have index-dependent behavior: that ship sailed when we decided to skip the secondary filter.

We chose to allow the operation, but revert to STIntersects in the non-indexed case. This gives us clear semantics: the correct results are always a subset of what we return. It's true that for SQL Server, these are somewhat odd semantics, since they are index-dependent.

But this is the only place in spatial where we have such behavior. If you want consistent results regardless of index, use STIntersects or any of the other methods we provide. If your use case fits the one I described above, you may very well want Filter.

Call it useful, call it odd. Call it Filter.

Cheers,
-Isaac

Spatial Data Type Structure

2009-08-10T19:38:25Z

Hi Folks,

As part of a larger effort to document our protocols, SQL Server has just released documentation on the structure of our spatial types. The document is also available in PDF. Note that all of this is preliminary, and while I doubt it will change much, it could. I had very little to do with this effort; you have Ed to thank.

It turns out that this structure is pretty simple, and there are folks out there who have fairly easily reverse-engineered it. Now that we’re publishing the structure, let me make one very specific warning: if you are going to play around with the binary format, do not set the valid bit (v) unless you’re absolutely sure the object is valid.

Setting this should not cause SQL Server itself any problems: you won’t crash anything. We just can’t guarantee that you’ll get the most predictable results. And things get very difficult to fix.

Let’s work an example. Consider the following linestring: LINESTRING (0 0, 10 0, 5 0, 10 0). This is clearly invalid according to the OGC, since it overlaps itself. We can put this into a geometry element and play with it:

declare @g geometry = 'LINESTRING (0 0, 10 0, 5 0, 10 0)'

select @g.STIsValid()            -- 0

select @g.MakeValid().STLength() -- 10

We can’t run the STLength() without first making the object valid or we’ll get an error. We can now pull out the binary version of this to play with:

select @g

And we get:

0x000000000100040000000000000000000000000000000000000000000000000024400000000000000000000000000000144000000000000000000000000000002440000000000000000001000000010000000001000000FFFFFFFF0000000002

We’re particularly interested in the highlighted byte, which contains a number of flags, all currently false. Most of these aren’t particularly dangerous to play with. For example, the lowest-order bit tells SQL Server that the item contains Z values. If you flip it, you’ll just end up with an error, since the data that follows doesn’t actually contain any Z values:

declare @g geometry = 0x000000000101040000000000000000000000000000000000000000000000000024400000000000000000000000000000144000000000000000000000000000002440000000000000000001000000010000000001000000FFFFFFFF0000000002

Msg 6522, Level 16, State 1, Line 1

A .NET Framework error occurred during execution of user-defined routine or aggregate "geometry":

System.IO.EndOfStreamException: Unable to read beyond the end of the stream.

The valid bit, the third-least significant, is a little touchy, though. Let’s see what happens if we flip that on our instance and run a few operations:

declare @g geometry = 0x000000000104040000000000000000000000000000000000000000000000000024400000000000000000000000000000144000000000000000000000000000002440000000000000000001000000010000000001000000FFFFFFFF0000000002

select @g.STIsValid()  -- 1

select @g.STLength()   -- 20

What’s happening? First, the system is trusting the bit and telling us that the instance is valid. This shouldn’t be too surprising: the bit was added so that we wouldn’t have to perform an expensive check every time we check the validity, and we’re using the optimization.

Second, the result of the STLength() operation is a bit odd. It’s calculating the length used to draw the invalid object, not the length of the object itself.

Okay, you say: let’s make this instance valid and see if we can fix things:

declare @h geometry = @g.MakeValid()

select @h.STLength()  -- 20

select @h.ToString()  -- LINESTRING (0 0, 10 0, 5 0, 10 0)

Ack! We’re trapped. MakeValid() tries to preserve the input geometry whenever possible, and therefore refuses to touch a valid instance. Our instance isn’t actually valid, but we said it was.

So if you’re creating a geometry from scratch, how are you to know how to set this bit? That is, how on Earth do you figure out if an instance is valid? Unless you’re absolutely sure, let the system do it for you: tell SQL that it isn’t valid and then run MakeValid(). Unlike setting the value true, there’s absolutely no harm in doing this—other than perf. In fact, when MakeValid() sees an object that isn’t marked as valid, it will first check to see if the instance is valid. If it is, MakeValid() won’t muck with the data, but will just flip the bit to true.

And keep in mind that although you can play with these structures, most of the time you shouldn’t need to. Use the built-in methods, and use the builder/sink API if you need to do something fancy. As always, there are plenty of examples on the SQL Server Spatial Tools CodePlex project.

Cheers,
-Isaac

The Sphere is Finite

2009-07-09T20:18:20Z

Hi Folks,

The title of this post states the obvious: the area of a sphere is finite. We even have a nice formula for it, 4πr². The same is true for an ellipsoid, which is just a sat-upon sphere, although computing the area gets more complicated.

But the plane is infinite. If we combine this with the fact that the OGC (implicitly) assumes that all geometry objects have a finite area, then any OGC-valid geometry has exactly one reasonable interpretation. If I ask you to fill in this polygon:

You have only one reasonable choice:

Not:

You can’t reasonably give me the latter one, since it would have an infinite area.

But since the sphere already has a finite area, a ring like this on the sphere just cuts it into two finite areas. So if I ask you to fill in this box:

You have a problem, since you don’t know for sure what I mean: do I want you to fill the portion containing the United States, or the part containing the rest of the world? The request is underspecified.

We fix this by using orientation, which I’ll discuss next time.

Cheers,
-Isaac

New Stuff in SQL Spatial Tools

2009-06-02T23:40:19Z

Hi Folks,

Marko Tintor from our Serbia team just dropped some new functionality into the SQL Server Spatial Tools project on CodePlex:

A method for testing whether a geography instance is valid.
Better: a method for creating a valid geography from invalid input. How this works deserves a post on of its own, but it basically uses the technique I suggested in this forum thread.
Methods for creating convex hulls in geography.

Enjoy!
-Isaac

The Plane, the Sphere, and the Ellipsoid

2009-06-02T00:00:00Z

Hi Folks,

We all know that the sphere isn’t the plane, and that an ellipsoid is different as well, but I don’t know if everyone has given so much thought to the practical effects of these differences.

And so I thought it might be a nice idea to catalog some of the interesting things that change when we move from a flat to round model—and it also makes a nice new series for the blog. My planned agenda is:

Edges on the Ellipsoid aren’t Obvious
The Sphere is Finite…
… So Orientation Matters on the Sphere…
…And yet, Maybe not so Much
Some Sensible Concepts Are Nonsense on the Sphere
Bounding Boxes on the Sphere are Strange
Funny Things Happen to Convex Polygons

I’ll keep this list up to date with links as they bake.

As you can see, I get off easy on the first post: I wrote it some time ago. I’ve also started to touch on the next few topics, but I think there’s more to say. I’ll be scrounging some material from my PDC talk last year, but there should be some new goodies as well.

Cheers,
-Isaac

SQL Server Spatial Indexing

2009-05-28T17:58:49Z

Hi Folks,

This post contains no new information; it’s just a rollup of links to spatial indexing posts I’ve made. If you want to know more about spatial indexing, these are the ones to read.

In order:

Hmm… it looks like I never got around to the specific of the geography index. It’s in the queue now.

Cheers,
-Isaac

London Spatial Event

2009-04-09T19:09:28Z

Simon Sabin asked me to pass along information about a free spatial event that he and Johannes Kebeck are holding in London on the 16th. It looks like they’ll be covering a bunch of hot SQL Server Spatial topics: how to get your data in to SQL, how to get your data out and visualize it, and how to make best use of spatial indexes.

Actually, they’re holding it twice: once in the afternoon, and again in the evening. Follow those links to sign up.

It looks like it should be a good meeting.

Cheers,
-Isaac

The Spatial Library without the Server: Bug and Workaround

2009-02-24T04:40:20Z

Hi Folks,

Jason Follas recently ran across a lingering issue when using our spatial library without the server. I mistakenly thought the fix had been shipped, but for now it remains.

The background is that the spatial library consists of a managed part and a native part. Roughly, the core geometry library resides in the native code, and everything else is in the managed layer. The native code requires the C++ runtime libraries. This is installed with SQL Server, so everything works fine if you install SQL.

The redistributable version we ship as part of the feature pack should redistribute the runtime as well, but it doesn’t. That’s the bug. So, if you install the library on a machine without the runtime, then it will fail.

The workaround is simple: install the runtime manually. Annoying, but effective. You’ll also be fine if you install another package—like the SQL Native Client—that includes the runtime, but unless you also want that component, I’d stick with the stand-alone install.

SP1 for SQL Server 2008 is coming up, but unfortunately, we’ve missed the cutoff to get this in. We’ll try to get this into the next service pack, but that will take some time. In the meantime, you’ll have to use this workaround. I’ll try to get an official KB article published on this as well.

So, apologies for the inconvenience. And thanks to Jason for raising the issue.

Cheers,
-Isaac

The Geography Hemisphere Limitation

2009-02-06T22:08:46Z

Hi Folks,

It occurs to me that I haven’t posted anything about the hemisphere limitation for the SQL Server geography type. This limitation is a little confusing, and could probably use some clarification.

It also occurs to me that I haven’t posted anything in a while—let’s rectify both of these.

We usually express SQL Server’s limitation by saying that no object can exceed a hemisphere. But which hemisphere? Does this mean that objects cannot cross the equator? The international date line? The truth: neither. We can, in fact, generate objects that cross the equator:

POLYGON ((-145 -45, -55 -45, -55 45, -145 45, -145 -45))

Or the date line:

POLYGON ((135 0, -135 0, -135 90, 135 90, 135 0))

Or the poles:

POLYGON ((0 45, 90 45, 180 45, 270 45, 0 45))

This illustrates that it is not objects in certain positions that are disallowed. Rather, large objects are disallowed: if an object spans more than half the globe, SQL Server will complain. So while a polygon that sits slightly inside of a hemisphere is fine:

POLYGON ((0 1, 90 1, 180 1, 270 1, 0 1))

One that is slightly larger causes problems:

POLYGON ((0 -1, 90 -1, 180 -1, 270 -1, 0 -1))

Msg 6522, Level 16, State 1, Line 1
A .NET Framework error occurred during execution of user-defined routine or aggregate "geography":
Microsoft.SqlServer.Types.GLArgumentException: 24205: The specified input does not represent a valid geography instance because it exceeds a single hemisphere. Each geography instance must fit inside a single hemisphere. A common reason for this error is that a polygon has the wrong ring orientation.
Microsoft.SqlServer.Types.GLArgumentException:
   at Microsoft.SqlServer.Types.GLNativeMethods.ThrowExceptionForHr(GL_HResult errorCode)
   at Microsoft.SqlServer.Types.GLNativeMethods.GeodeticIsValid(GeoData g)
   at Microsoft.SqlServer.Types.SqlGeography.IsValidExpensive()
   at Microsoft.SqlServer.Types.SqlGeography.ConstructGeographyFromUserInput(GeoData g, Int32 srid)
   at Microsoft.SqlServer.Types.SqlGeography.GeographyFromText(OpenGisType type, SqlChars taggedText, Int32 srid)
   at Microsoft.SqlServer.Types.SqlGeography.STGeomFromText(SqlChars geometryTaggedText, Int32 srid)
   at Microsoft.SqlServer.Types.SqlGeography.Parse(SqlString s)
.

We can dig a little deeper. When SQL Server sees a geography instance, it computes a bounding cap for it. This is very much like a bounding box on the plane, but is defined by a center point and an angle. We can actually find the bounding cap for an object using the EnvelopeCenter() and EnvelopeAngle() methods on geography. Using these, we can plot the cap. For example:

POLYGON ((-50 -10, 50 -10, 50 10, -50 10, -50 -10))

If the cap angle exceeds 90 degrees, then the object exceeds a hemisphere. The cap computed above has an angle of 50.7 degrees.

But there is some subtlety in how SQL Server determines this cap. The angle is relatively simple: it is the maximum angle from the center to any of the points in the figure, yielding a minimal cap with that center. The center, however, is determined by summing the vectors from the center of the globe to each vertex in the figure, essentially averaging the vertices. This means that if the points in our figure are lopsided—e.g., if add more points on the eastern edge—we will compute a cap that no longer looks very minimal:

POLYGON ((-50 -10, 50 -10, 50 -5, 50 0, 50 5, 50 10, -50 10, -50 -10))

Now the cap center is skewed, so the angle has to increase—to 77.4 degrees—to contain the object. If we add more points on the eastern edge we get into trouble:

POLYGON ((-50 -10, 50 -10, 50 -8, 50 -6, 50 -5 50 -4, 50 -2, 50 0, 50 2, 50 4, 50 5, 50 6, 50 8, 50 10, -50 10, -50 -10))

Msg 6522, Level 16, State 1, Line 1
A .NET Framework error occurred during execution of user-defined routine or aggregate "geography":
Microsoft.SqlServer.Types.GLArgumentException: 24205: The specified input does not represent a valid geography instance because it exceeds a single hemisphere. Each geography instance must fit inside a single hemisphere. A common reason for this error is that a polygon has the wrong ring orientation.
Microsoft.SqlServer.Types.GLArgumentException:
   at Microsoft.SqlServer.Types.GLNativeMethods.ThrowExceptionForHr(GL_HResult errorCode)
   at Microsoft.SqlServer.Types.GLNativeMethods.GeodeticIsValid(GeoData g)
   at Microsoft.SqlServer.Types.SqlGeography.IsValidExpensive()
   at Microsoft.SqlServer.Types.SqlGeography.ConstructGeographyFromUserInput(GeoData g, Int32 srid)
   at Microsoft.SqlServer.Types.SqlGeography.GeographyFromText(OpenGisType type, SqlChars taggedText, Int32 srid)
   at Microsoft.SqlServer.Types.SqlGeography.STGeomFromText(SqlChars geometryTaggedText, Int32 srid)
   at Microsoft.SqlServer.Types.SqlGeography.Parse(SqlString s)
.

So although our object hasn’t changed—the extra vertices we added were chosen so they don’t change the shape—SQL Server now thinks we’ve exceeded a hemisphere.

Let me answer two more obvious questions. First: why do we compute caps this way instead of computing a true minimal bounding cap? It turns out that finding a minimal cap is difficult computationally, and because this operation happens a lot, we need something cheap.

Second: why does SQL Server have the hemisphere limitation at all? A complete answer will require another post. Suffice to say, it’s an implementation artifact that the SQL Server team absolutely abhors. That SQL Server isn’t the only system with such a limitation doesn’t make it any less annoying, and removing the limit is high on everyone’s priorities.

Cheers,
-Isaac

Good Spatial Blog Resources

2008-12-11T13:20:00Z

Hi Folks,

While I continue to procrastinate, here are some excellent spatial resources to peruse.

First, David Lean, a Microsoft evangelist, has very comprehensive list of spatial posts over on his Dave does Data blog. He covers a wide range of spatial methods, the builder/sink API, as well as some pointers on creating spatial applications.

Second, John O’Brien, a Microsoft MVP, has a couple articles (here and here) showing how to do some cool data visualization right in Management Studio.

Finally, Johannes Kebeck continues with a couple recent posts on creating maps in Virtual Earth based on data coming from SQL Server.

Enjoy!
-Isaac

Puzzle Solution

2008-12-08T21:33:21Z

Last time, I posted a question sent to me by Rob Mount. So what solutions exist other than the north pole?

You did well: jnelso99 got part of the way there; tanoshimi finished it off. We can find a set of circles around the south pole with lengths of 1/N miles: 1 mile, 1/2 mile, 1/3 mile, etc. Any point one mile north of any of these circles will work: you travel south one mile to one of the circles, circle the earth N times, and then head back north to where you started.

Where exactly are these circles? Well, let’s be a bit mathematical about it. Let R be the radius of the earth, and let x be the distance of each leg of our path. Working in radians, let p0 = (lat, long) be our starting point. (Radians just make the math so much nicer.)

First we walk south x units. This only changes the latitude, and so we find ourselves at a new point:

p1 = (lat – x/R, long)

Next we walk x units east, which only impacts the longitude. How much this affects the longitude depends, however, on our current latitude:

p2 = (lat – x/R, long + x/cos(lat – x/R))

Finally we walk x units north. This brings the latitude back to where we started:

pf = (lat, long + x/(R * cos(lat – x/R)))

Okay, so what do we make of this? We want p0 to equal pf. The latitude is easy, since the latitudes of p0 and pf are the same. Further, we note that if lat is positive or negative pi/2 then we’re at a pole and the value of long is irrelevant. Positive pi/2 gives us the north pole solution; –pi/2 ends up being nonsense, since you can’t go south from the south pole.

But if lat is not pi/2, then long matters. In particular, our starting longitude has to equal our ending, but it can wrap around, so:

long + 2 * pi * N = long + x / (R * cos(lat – x/R))

2 * pi * N = x / (R * cos(lat – x/R))

Here N is any integer; the 2 * pi * N factor accounts for the fact that we can circle the globe. Solving for lat we find:

cos(lat – x/R) = x / ( 2 * pi * N * R )

lat – x/R = acos( x / ( 2 * pi * N * R) )

lat = acos( x / ( 2 * pi * N * R) ) + x/R

The acos term is undefined if N = 0, and if N < 1 then the value lies outside of the range [–pi/2, pi/2]. When N is greater than 0, then the results of the acos term are in our range, but they could be positive or negative; it turns out that the values we want are negative.

So what does this mean? We have derived a set of latitude values that look like solutions, and the longitudes associated with these solutions are unconstrained. In other words, we have a set of circles around the south pole corresponding to each N in {1, 2, …}. These are exactly the circles we’ve already described, but now we can compute exactly where they are. For R = 3963 miles and x = 1:

N=1: lat = -acos( 1 / (24900.263) ) + 0.000252 = -1.5705041 = -89.983260 degrees

N=2: lat = -acos( 1 / (49800.527) ) + 0.000252 = -1.5705242 = -89.984410 degrees

N=3: lat = -acos( 1 / (74700.790) ) + 0.000252 = -1.5705309 = -89.984794 degrees

…

And when N=1, this circle is indeed about 1.16 miles north of the south pole, just as jnelso99 noted.

Cheers,
-Isaac

PDC and a Nice Geographic Puzzle

2008-12-05T22:03:09Z

Hi Folks,

At PDC I gave a talk largely inspired by topics raised here and in the spatial forums. But “inspired by” doesn’t equate to “a duplicate of”, and to turn things around, I’ve been meaning to write a few posts here inspired by my PDC talk. Stay tuned.

In the meantime, Rob Mount from Intergraph sent me a note that started:

As I review your PDC presentation I’m reminded of a puzzle I think you’ll enjoy.

I did indeed, and I hope a lot of you will enjoy it as well. Rob started out with a puzzle I expect most of us have heard before:

When I was growing up one of my uncles was fond of challenging the children in the family with puzzles. One of my favorites, as a very young child, was this one: A hunter walks a mile south, a mile east and a mile north and finds himself back at the starting point. A bear walks by. What color is the bear?

This is well-known enough that I don’t think the answer will be much of a spoiler:

He, of course, thought the hunter started at the North Pole. The bear was a polar bear and hence white.

A perfectly valid answer, of course. But Rob continues:

Years later I finally got my revenge by stumping him with this problem: I reminded him of the hunter and the polar bear and pointed out that there are actually several other points on the earth that meet the geographic constraint he stated – if you walk a mile south, a mile east and a mile north you find yourself back where you started.

Assuming a spherical earth, how many such points exist and where are they?

I won’t spoil this one so quickly. Go ahead and post your answers in the comments; I’ll post the solution in a few days.

Cheers,
-Isaac

Frequently Asked Question: How do I load shapefiles?

2008-11-05T00:29:34Z

This has come up a few times now. Multiple questions deserve at least one answer, right?

First, Microsoft has not produced a shapefile loader (or exporter). If this is important to you, here’s the Connect item to hit. (And yes: we do listen to Connect!)

So, what are you to do? There are a few options:

If you are a user of one of our partner GIS vendors---Autodesk, ESRI, Intergraph, Manifold, or Pitney Bowes (MapInfo)---they probably have support for loading shapefiles already. You’ll have to ask them, though: I’m not an expert in their products.
If not, and if you aren’t interested in a real GIS, then you should check out Safe Software: they build spatial ETL software that will take shapefiles (as well as about ~200 other formats) perform transformations on the data, and load into SQL Server.
If you’re looking for a free solution, then there are a few popping up in the wild. Morten Nielsen has had his tool available for some time now, which has both a command line and GUI interfaces. Scott Ellington has created a command line tool as well, but I haven’t had a chance to play with it yet.
You could build your own. I suggest using the sink/builder API---you can find plenty of examples in our Codeplex project.

Hopefully one of these solutions will work for you.

Cheers,
-Isaac

Off to PDC

2008-10-24T23:51:00Z

Despite my relative youth, I can be a bit of a fuddy-duddy. Fighting my natural impulses, I’ve decided to give Twitter a try---at least while I’m at PDC. So, if you’re interested in tracking me down, surf the tubes over to my very own Truman Show.

Or drop me an old-fashioned email.

See you at the show!
-Isaac

Nearest Neighbors

2008-10-23T02:38:00Z

Hi Folks,

Spatial users often want to find the object nearest a given point. This operation, usually referred to as nearest neighbor search, is remarkably common in many areas of computer science. In general, we may wish to find not only the nearest, but the k-nearest neighbors.

How can we accomplish this with SQL Server? Here we’ll look at finding the single nearest neighbor; the extension to k-nearest neighbors is relatively straight forward.

First, let's examine the naive method for accomplishing this: simply order the table by distance and restrict the results. For all of these examples, we’ll assume a table T with a spatial column g, as well as a parameter @x containing the search point:

SELECT TOP(1) *

FROM T

ORDER BY g.STDistance(@x) ASC

This solution certainly has simplicity on its side, but consider the work that needs to be done. The entire table must be scanned, and the distance of each to the search point must be calculated. Ouch.

We could conceivably improve on this by restricting our search space to to the immediate region around the target point:

DECLARE @region geography = @x.STBuffer(10000)

SELECT TOP(1) *

FROM T

WHERE g.Filter(@region) = 1

ORDER BY g.STDistance(@x) ASC

But this solution requires that we know our data very well: if there are no rows in the region, then we will fail to find the nearest neighbor; if there are too many, then we will again be left with a rather inefficient query.

How do we escape this morass? We can do so by starting with a very small region---so small that we can be certain not to encounter too many results---and then keep enlarging it until we find something. Doing this with a loop is not hard, but Steven Hemingray showed me how to do this with entirely declarative syntax:

DECLARE @start FLOAT = 1000;

WITH NearestPoints AS

   SELECT TOP(1) WITH TIES *,  T.g.STDistance(@x) AS dist

   FROM Numbers JOIN T WITH(INDEX(spatial_index))

   ON T.g.STDistance(@x) < @start*POWER(2,Numbers.n)

   ORDER BY n

SELECT TOP(1) * FROM NearestPoints

ORDER BY n, dist

This requires some explanation. First, the @start parameter gives the initial region to search. I’ve chosen one kilometer, but this can be adjusted downward if your data is very dense. Second, you’ll notice that we make use of a Numbers table, which just contains the numbers 1 through n. This just contains a long list of integers, which is is useful in many situations.

The inner query examines a set of exponentially-expanding regions. The ORDER BY clause along with the TOP(1) allows the query to stop as soon as it finds the smallest non-empty region. The WITH TIES statement makes sure that all of the objects in that region will be in the result set.

Once the inner query returns a list of potential results, the outer query examines them to find which is actually nearest. With this approach, we can select a start area small enough to keep the cost low in dense data, but also be guaranteed to find a distant nearest neighbor.

Incidentally, if you don’t already have a numbers table, you can create one quite quickly with some mildly-black magic like this:

SELECT TOP 100000 IDENTITY(int,1,1) AS n

INTO numbers

FROM MASTER..spt_values a, MASTER..spt_values b

CREATE UNIQUE CLUSTERED INDEX idx_1 ON numbers(n)

This isn’t a particularly pretty solution, but to proactively answer a question, we didn’t add a method for this primarily because we ran out of time. Look for something more built-in the next go around.

Cheers,
-Isaac

A Few Strange Functions

2008-10-16T20:13:45Z

Hi Folks,

A post on the spatial forum last week caught my attention for entirely non-spatial reasons: it made use of two functions---RADIANS() and DEGREES()---that I never knew existed.

It seems rather strange that out of the innumerable (well, technically enumerable) list of functions that we could implement, someone felt these were worth the effort. For example, we save exactly 0 characters by using these functions:

RADIANS(@x)

DEGREES(@y)

Becomes:

@x*PI()/180

@y*180/PI()

Granted, using the functions is clearer and less error prone; but I’m not arguing that they are bad functions, just surprising.

What is surprising and bad, if you ask me, is that both RADIANS() and DEGREES() have int—>int overloads. In other words, if you call these functions with an integer, you get an integer result:

SELECT RADIANS(180) -- 3, not 3.141592653589793100

SELECT DEGREES(3)   -- 171, not 171.887338539246970000

This behavior is very strange. I cannot think of a case in which it is useful, yet plenty where it could cause harm. The behavior is noted in BOL:

Arithmetic functions, such as ABS, CEILING, DEGREES, FLOOR, POWER, RADIANS, and SIGN, return a value having the same data type as the input value.

Of these, only RADIANS() and DEGREES() have natural floating-point return values: all others are naturally integers, and while promoting them to floats may not be necessary, it doesn’t seem problematic.

Let me know if you can see a benefit of this behavior; I’d love to see these overloads on our deprecation list.

Cheers,
-Isaac

Conference Correction

2008-10-09T18:49:27Z

Hi Folks,

Unfortunately, I need to correct an earlier post of mine. I will not be speaking at PASS this year---it looks like there were some mixed signals. If you’re looking for your spatial fix, Michael Rys will be talking about types and indexing.

Still, PASS is on my home turf, so I’ll be around: come see me at the Ask the Experts session, or drop me a line and we can meet up.

PDC and Autodesk University are still on until they tell me otherwise.

Cheers,
-Isaac