geoindex

package
v0.0.0-...-1b6ad0c Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 11, 2020 License: Apache-2.0 Imports: 20 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source
var (
	ErrInvalidLengthConfig = fmt.Errorf("proto: negative length found during unmarshaling")
	ErrIntOverflowConfig   = fmt.Errorf("proto: integer overflow")
)
View Source
var CommuteRelationshipMap = map[RelationshipType]RelationshipType{
	Covers:       CoveredBy,
	CoveredBy:    Covers,
	DWithin:      DWithin,
	DFullyWithin: DFullyWithin,
	Intersects:   Intersects,
}

CommuteRelationshipMap is used to determine how the geospatial relationship changes if the arguments to the index-accelerated function are commuted.

The relationships in the RelationshipMap map above only apply when the second argument to the function is the indexed column. If the arguments are commuted so that the first argument is the indexed column, the relationship may change.

View Source
var RelationshipMap = map[string]RelationshipType{
	"st_covers":           Covers,
	"st_coveredby":        CoveredBy,
	"st_contains":         Covers,
	"st_containsproperly": Covers,
	"st_crosses":          Intersects,
	"st_dwithin":          DWithin,
	"st_dfullywithin":     DFullyWithin,
	"st_equals":           Intersects,
	"st_intersects":       Intersects,
	"st_overlaps":         Intersects,
	"st_touches":          Intersects,
	"st_within":           CoveredBy,
}

RelationshipMap contains all the geospatial functions that can be index- accelerated. Each function implies a certain type of geospatial relationship, which affects how the index is queried as part of a constrained scan or geospatial lookup join. RelationshipMap maps the function name to its corresponding relationship (Covers, CoveredBy, DFullyWithin, DWithin or Intersects).

Note that for all of these functions, a geospatial lookup join or constrained index scan may produce false positives. Therefore, the original function must be called on the output of the index operation to filter the results.

View Source
var RelationshipReverseMap = map[RelationshipType]string{
	Covers:       "st_covers",
	CoveredBy:    "st_coveredby",
	DWithin:      "st_dwithin",
	DFullyWithin: "st_dfullywithin",
	Intersects:   "st_intersects",
}

RelationshipReverseMap contains a default function for each of the possible geospatial relationships.

Functions

func IsEmptyConfig

func IsEmptyConfig(cfg *Config) bool

IsEmptyConfig returns whether the given config contains a geospatial index configuration.

func IsGeographyConfig

func IsGeographyConfig(cfg *Config) bool

IsGeographyConfig returns whether the config is a geography geospatial index configuration.

func IsGeometryConfig

func IsGeometryConfig(cfg *Config) bool

IsGeometryConfig returns whether the config is a geometry geospatial index configuration.

Types

type Config

type Config struct {
	S2Geography *S2GeographyConfig `protobuf:"bytes,1,opt,name=s2_geography,json=s2Geography,proto3" json:"s2_geography,omitempty"`
	S2Geometry  *S2GeometryConfig  `protobuf:"bytes,2,opt,name=s2_geometry,json=s2Geometry,proto3" json:"s2_geometry,omitempty"`
}

Config is the information used to tune one instance of a geospatial index. Each SQL index will have its own config.

At the moment, only one major indexing strategy is implemented (S2 cells).

func DefaultGeographyIndexConfig

func DefaultGeographyIndexConfig() *Config

DefaultGeographyIndexConfig returns a default config for a geography index.

func DefaultGeometryIndexConfig

func DefaultGeometryIndexConfig() *Config

DefaultGeometryIndexConfig returns a default config for a geometry index.

func GeometryIndexConfigForSRID

func GeometryIndexConfigForSRID(srid geopb.SRID) *Config

GeometryIndexConfigForSRID returns a geometry index config for srid.

func (*Config) Descriptor

func (*Config) Descriptor() ([]byte, []int)

func (*Config) Equal

func (this *Config) Equal(that interface{}) bool

func (*Config) GetValue

func (this *Config) GetValue() interface{}

func (*Config) Marshal

func (m *Config) Marshal() (dAtA []byte, err error)

func (*Config) MarshalTo

func (m *Config) MarshalTo(dAtA []byte) (int, error)

func (*Config) ProtoMessage

func (*Config) ProtoMessage()

func (*Config) Reset

func (m *Config) Reset()

func (*Config) SetValue

func (this *Config) SetValue(value interface{}) bool

func (*Config) Size

func (m *Config) Size() (n int)

func (*Config) String

func (m *Config) String() string

func (*Config) Unmarshal

func (m *Config) Unmarshal(dAtA []byte) error

func (*Config) XXX_DiscardUnknown

func (m *Config) XXX_DiscardUnknown()

func (*Config) XXX_Marshal

func (m *Config) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*Config) XXX_Merge

func (m *Config) XXX_Merge(src proto.Message)

func (*Config) XXX_Size

func (m *Config) XXX_Size() int

func (*Config) XXX_Unmarshal

func (m *Config) XXX_Unmarshal(b []byte) error

type GeographyIndex

type GeographyIndex interface {
	// InvertedIndexKeys returns the keys to store this object under when adding
	// it to the index.
	InvertedIndexKeys(c context.Context, g *geo.Geography) ([]Key, error)

	// Covers returns the index spans to read and union for the relationship
	// ST_Covers(g, x), where x are the indexed geometries.
	Covers(c context.Context, g *geo.Geography) (UnionKeySpans, error)

	// CoveredBy returns the index entries to read and the expression to compute
	// for ST_CoveredBy(g, x), where x are the indexed geometries.
	CoveredBy(c context.Context, g *geo.Geography) (RPKeyExpr, error)

	// Intersects returns the index spans to read and union for the relationship
	// ST_Intersects(g, x), where x are the indexed geometries.
	Intersects(c context.Context, g *geo.Geography) (UnionKeySpans, error)

	// DWithin returns the index spans to read and union for the relationship
	// ST_DWithin(g, x, distanceMeters). That is, there exists a part of
	// geometry g that is within distanceMeters of x, where x is an indexed
	// geometry. This function assumes a sphere.
	DWithin(
		c context.Context, g *geo.Geography, distanceMeters float64,
		useSphereOrSpheroid geogfn.UseSphereOrSpheroid,
	) (UnionKeySpans, error)

	// TestingInnerCovering returns an inner covering of g.
	TestingInnerCovering(g *geo.Geography) s2.CellUnion
}

GeographyIndex is an index over the unit sphere.

func NewS2GeographyIndex

func NewS2GeographyIndex(cfg S2GeographyConfig) GeographyIndex

NewS2GeographyIndex returns an index with the given configuration. The configuration of an index cannot be changed without rewriting the index since deletes could miss some index entries. Currently, reads could use a different configuration, but that is subject to change if we manage to strengthen the covering invariants (see the todo in covers() in index.go).

type GeometryIndex

type GeometryIndex interface {
	// InvertedIndexKeys returns the keys to store this object under when adding
	// it to the index.
	InvertedIndexKeys(c context.Context, g *geo.Geometry) ([]Key, error)

	// Covers returns the index spans to read and union for the relationship
	// ST_Covers(g, x), where x are the indexed geometries.
	Covers(c context.Context, g *geo.Geometry) (UnionKeySpans, error)

	// CoveredBy returns the index entries to read and the expression to compute
	// for ST_CoveredBy(g, x), where x are the indexed geometries.
	CoveredBy(c context.Context, g *geo.Geometry) (RPKeyExpr, error)

	// Intersects returns the index spans to read and union for the relationship
	// ST_Intersects(g, x), where x are the indexed geometries.
	Intersects(c context.Context, g *geo.Geometry) (UnionKeySpans, error)

	// DWithin returns the index spans to read and union for the relationship
	// ST_DWithin(g, x, distance). That is, there exists a part of geometry g
	// that is within distance units of x, where x is an indexed geometry.
	DWithin(c context.Context, g *geo.Geometry, distance float64) (UnionKeySpans, error)

	// DFullyWithin returns the index spans to read and union for the
	// relationship ST_DFullyWithin(g, x, distance). That is, the maximum distance
	// across every pair of points comprising geometries g and x is within distance
	// units, where x is an indexed geometry.
	DFullyWithin(c context.Context, g *geo.Geometry, distance float64) (UnionKeySpans, error)

	// TestingInnerCovering returns an inner covering of g.
	TestingInnerCovering(g *geo.Geometry) s2.CellUnion
}

GeometryIndex is an index over 2D cartesian coordinates.

func NewS2GeometryIndex

func NewS2GeometryIndex(cfg S2GeometryConfig) GeometryIndex

NewS2GeometryIndex returns an index with the given configuration. All reads and writes on this index must use the same config. Writes must use the same config to correctly process deletions. Reads must use the same config since the bounds affect when a read needs to look at the exceedsBoundsCellID.

type Key

type Key uint64

Key is one entry under which a geospatial shape is stored on behalf of an Index. The index is of the form (Key, Primary Key).

func (Key) String

func (k Key) String() string

type KeySpan

type KeySpan struct {
	// Both Start and End are inclusive, i.e., [Start, End].
	Start, End Key
}

KeySpan represents a range of Keys.

type RPExprElement

type RPExprElement interface {
	// contains filtered or unexported methods
}

RPExprElement is an element in the Reverse Polish notation expression. It is implemented by Key and RPSetOperator.

type RPKeyExpr

type RPKeyExpr []RPExprElement

RPKeyExpr is an expression to evaluate over primary keys retrieved for index keys. If we view each index key as a posting list of primary keys, the expression involves union and intersection over the sets represented by each posting list. For S2, this expression represents an intersection of ancestors of different keys (cell ids) and is likely to contain many common keys. This special structure allows us to efficiently and easily eliminate common sub-expressions, hence the interface presents the factored expression. The expression is represented in Reverse Polish notation.

func (RPKeyExpr) String

func (x RPKeyExpr) String() string

type RPSetOperator

type RPSetOperator int

RPSetOperator is a set operator in the Reverse Polish notation expression.

const (
	// RPSetUnion is the union operator.
	RPSetUnion RPSetOperator = iota + 1

	// RPSetIntersection is the intersection operator.
	RPSetIntersection
)

type RelationshipType

type RelationshipType uint8

RelationshipType stores a type of geospatial relationship query that can be accelerated using an index.

const (
	// Covers corresponds to the relationship in which one geospatial object
	// covers another geospatial object.
	Covers RelationshipType = (1 << iota)

	// CoveredBy corresponds to the relationship in which one geospatial object
	// is covered by another geospatial object.
	CoveredBy

	// Intersects corresponds to the relationship in which one geospatial object
	// intersects another geospatial object.
	Intersects

	// DWithin corresponds to a relationship where there exists a part of one
	// geometry within d distance units of the other geometry.
	DWithin

	// DFullyWithin corresponds to a relationship where every pair of points in
	// two geometries are within d distance units.
	DFullyWithin
)

func (RelationshipType) String

func (gr RelationshipType) String() string

type S2Config

type S2Config struct {
	// MinLevel is the minimum cell level stored in the index. If left unset, it
	// defaults to 0.
	MinLevel int32 `protobuf:"varint,1,opt,name=min_level,json=minLevel,proto3" json:"min_level,omitempty"`
	// MaxLevel is the maximum cell level stored in the index. If left unset, it
	// defaults to 30.
	MaxLevel int32 `protobuf:"varint,2,opt,name=max_level,json=maxLevel,proto3" json:"max_level,omitempty"`
	// `MaxLevel-MinLevel` must be an exact multiple of LevelMod. If left unset,
	// it defaults to 1.
	LevelMod int32 `protobuf:"varint,3,opt,name=level_mod,json=levelMod,proto3" json:"level_mod,omitempty"`
	// MaxCells is a soft hint for the maximum number of entries used to store a
	// single geospatial object. If left unset, it defaults to 4.
	MaxCells int32 `protobuf:"varint,4,opt,name=max_cells,json=maxCells,proto3" json:"max_cells,omitempty"`
}

S2Config is the required information to tune one instance of an S2 cell backed geospatial index. For advanced users only -- the defaults should be good enough.

TODO(sumeer): Based on experiments, reduce the knobs below by making the covering self-tuning.

func (*S2Config) Descriptor

func (*S2Config) Descriptor() ([]byte, []int)

func (*S2Config) Equal

func (this *S2Config) Equal(that interface{}) bool

func (*S2Config) Marshal

func (m *S2Config) Marshal() (dAtA []byte, err error)

func (*S2Config) MarshalTo

func (m *S2Config) MarshalTo(dAtA []byte) (int, error)

func (*S2Config) ProtoMessage

func (*S2Config) ProtoMessage()

func (*S2Config) Reset

func (m *S2Config) Reset()

func (*S2Config) Size

func (m *S2Config) Size() (n int)

func (*S2Config) String

func (m *S2Config) String() string

func (*S2Config) Unmarshal

func (m *S2Config) Unmarshal(dAtA []byte) error

func (*S2Config) XXX_DiscardUnknown

func (m *S2Config) XXX_DiscardUnknown()

func (*S2Config) XXX_Marshal

func (m *S2Config) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*S2Config) XXX_Merge

func (m *S2Config) XXX_Merge(src proto.Message)

func (*S2Config) XXX_Size

func (m *S2Config) XXX_Size() int

func (*S2Config) XXX_Unmarshal

func (m *S2Config) XXX_Unmarshal(b []byte) error

type S2GeographyConfig

type S2GeographyConfig struct {
	S2Config *S2Config `protobuf:"bytes,1,opt,name=s2_config,json=s2Config,proto3" json:"s2_config,omitempty"`
}

func (*S2GeographyConfig) Descriptor

func (*S2GeographyConfig) Descriptor() ([]byte, []int)

func (*S2GeographyConfig) Equal

func (this *S2GeographyConfig) Equal(that interface{}) bool

func (*S2GeographyConfig) Marshal

func (m *S2GeographyConfig) Marshal() (dAtA []byte, err error)

func (*S2GeographyConfig) MarshalTo

func (m *S2GeographyConfig) MarshalTo(dAtA []byte) (int, error)

func (*S2GeographyConfig) ProtoMessage

func (*S2GeographyConfig) ProtoMessage()

func (*S2GeographyConfig) Reset

func (m *S2GeographyConfig) Reset()

func (*S2GeographyConfig) Size

func (m *S2GeographyConfig) Size() (n int)

func (*S2GeographyConfig) String

func (m *S2GeographyConfig) String() string

func (*S2GeographyConfig) Unmarshal

func (m *S2GeographyConfig) Unmarshal(dAtA []byte) error

func (*S2GeographyConfig) XXX_DiscardUnknown

func (m *S2GeographyConfig) XXX_DiscardUnknown()

func (*S2GeographyConfig) XXX_Marshal

func (m *S2GeographyConfig) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*S2GeographyConfig) XXX_Merge

func (m *S2GeographyConfig) XXX_Merge(src proto.Message)

func (*S2GeographyConfig) XXX_Size

func (m *S2GeographyConfig) XXX_Size() int

func (*S2GeographyConfig) XXX_Unmarshal

func (m *S2GeographyConfig) XXX_Unmarshal(b []byte) error

type S2GeometryConfig

type S2GeometryConfig struct {
	// The rectangle bounds of the plane that will be efficiently indexed. Shapes
	// should rarely exceed these bounds.
	MinX     float64   `protobuf:"fixed64,1,opt,name=min_x,json=minX,proto3" json:"min_x,omitempty"`
	MaxX     float64   `protobuf:"fixed64,2,opt,name=max_x,json=maxX,proto3" json:"max_x,omitempty"`
	MinY     float64   `protobuf:"fixed64,3,opt,name=min_y,json=minY,proto3" json:"min_y,omitempty"`
	MaxY     float64   `protobuf:"fixed64,4,opt,name=max_y,json=maxY,proto3" json:"max_y,omitempty"`
	S2Config *S2Config `protobuf:"bytes,5,opt,name=s2_config,json=s2Config,proto3" json:"s2_config,omitempty"`
}

func (*S2GeometryConfig) Descriptor

func (*S2GeometryConfig) Descriptor() ([]byte, []int)

func (*S2GeometryConfig) Equal

func (this *S2GeometryConfig) Equal(that interface{}) bool

func (*S2GeometryConfig) Marshal

func (m *S2GeometryConfig) Marshal() (dAtA []byte, err error)

func (*S2GeometryConfig) MarshalTo

func (m *S2GeometryConfig) MarshalTo(dAtA []byte) (int, error)

func (*S2GeometryConfig) ProtoMessage

func (*S2GeometryConfig) ProtoMessage()

func (*S2GeometryConfig) Reset

func (m *S2GeometryConfig) Reset()

func (*S2GeometryConfig) Size

func (m *S2GeometryConfig) Size() (n int)

func (*S2GeometryConfig) String

func (m *S2GeometryConfig) String() string

func (*S2GeometryConfig) Unmarshal

func (m *S2GeometryConfig) Unmarshal(dAtA []byte) error

func (*S2GeometryConfig) XXX_DiscardUnknown

func (m *S2GeometryConfig) XXX_DiscardUnknown()

func (*S2GeometryConfig) XXX_Marshal

func (m *S2GeometryConfig) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*S2GeometryConfig) XXX_Merge

func (m *S2GeometryConfig) XXX_Merge(src proto.Message)

func (*S2GeometryConfig) XXX_Size

func (m *S2GeometryConfig) XXX_Size() int

func (*S2GeometryConfig) XXX_Unmarshal

func (m *S2GeometryConfig) XXX_Unmarshal(b []byte) error

type UnionKeySpans

type UnionKeySpans []KeySpan

UnionKeySpans is the set of indexed spans to retrieve and combine via set union. The spans are guaranteed to be non-overlapping. Duplicate primary keys will not be retrieved by any individual key, but they may be present if more than one key is retrieved (including duplicates in a single span where End - Start > 1).

func (UnionKeySpans) String

func (s UnionKeySpans) String() string

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL