cockroach: github.com/cockroachdb/cockroach/pkg/geo/geoindex Index | Files

package geoindex

import "github.com/cockroachdb/cockroach/pkg/geo/geoindex"

Index

Package Files

config.pb.go geoindex.go s2_geography_index.go s2_geometry_index.go

Variables

var (
    ErrInvalidLengthConfig = fmt.Errorf("proto: negative length found during unmarshaling")
    ErrIntOverflowConfig   = fmt.Errorf("proto: integer overflow")
)
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.

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.

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.

func IsEmptyConfig Uses

func IsEmptyConfig(cfg *Config) bool

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

func IsGeographyConfig Uses

func IsGeographyConfig(cfg *Config) bool

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

func IsGeometryConfig Uses

func IsGeometryConfig(cfg *Config) bool

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

type Config Uses

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 Uses

func DefaultGeographyIndexConfig() *Config

DefaultGeographyIndexConfig returns a default config for a geography index.

func DefaultGeometryIndexConfig Uses

func DefaultGeometryIndexConfig() *Config

DefaultGeometryIndexConfig returns a default config for a geometry index.

func GeometryIndexConfigForSRID Uses

func GeometryIndexConfigForSRID(srid geopb.SRID) (*Config, error)

GeometryIndexConfigForSRID returns a geometry index config for srid.

func (*Config) Descriptor Uses

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

func (*Config) Equal Uses

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

func (*Config) GetValue Uses

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

func (*Config) Marshal Uses

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

func (*Config) MarshalTo Uses

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

func (*Config) ProtoMessage Uses

func (*Config) ProtoMessage()

func (*Config) Reset Uses

func (m *Config) Reset()

func (*Config) SetValue Uses

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

func (*Config) Size Uses

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

func (*Config) String Uses

func (m *Config) String() string

func (*Config) Unmarshal Uses

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

func (*Config) XXX_DiscardUnknown Uses

func (m *Config) XXX_DiscardUnknown()

func (*Config) XXX_Marshal Uses

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

func (*Config) XXX_Merge Uses

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

func (*Config) XXX_Size Uses

func (m *Config) XXX_Size() int

func (*Config) XXX_Unmarshal Uses

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

type GeographyIndex Uses

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 Uses

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 Uses

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 Uses

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 Uses

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 Uses

func (k Key) String() string

type KeySpan Uses

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

KeySpan represents a range of Keys.

type RPExprElement Uses

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 Uses

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 Uses

func (x RPKeyExpr) String() string

type RPSetOperator Uses

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 Uses

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 Uses

func (gr RelationshipType) String() string

type S2Config Uses

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 Uses

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

func (*S2Config) Equal Uses

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

func (*S2Config) Marshal Uses

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

func (*S2Config) MarshalTo Uses

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

func (*S2Config) ProtoMessage Uses

func (*S2Config) ProtoMessage()

func (*S2Config) Reset Uses

func (m *S2Config) Reset()

func (*S2Config) Size Uses

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

func (*S2Config) String Uses

func (m *S2Config) String() string

func (*S2Config) Unmarshal Uses

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

func (*S2Config) XXX_DiscardUnknown Uses

func (m *S2Config) XXX_DiscardUnknown()

func (*S2Config) XXX_Marshal Uses

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

func (*S2Config) XXX_Merge Uses

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

func (*S2Config) XXX_Size Uses

func (m *S2Config) XXX_Size() int

func (*S2Config) XXX_Unmarshal Uses

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

type S2GeographyConfig Uses

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

func (*S2GeographyConfig) Descriptor Uses

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

func (*S2GeographyConfig) Equal Uses

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

func (*S2GeographyConfig) Marshal Uses

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

func (*S2GeographyConfig) MarshalTo Uses

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

func (*S2GeographyConfig) ProtoMessage Uses

func (*S2GeographyConfig) ProtoMessage()

func (*S2GeographyConfig) Reset Uses

func (m *S2GeographyConfig) Reset()

func (*S2GeographyConfig) Size Uses

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

func (*S2GeographyConfig) String Uses

func (m *S2GeographyConfig) String() string

func (*S2GeographyConfig) Unmarshal Uses

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

func (*S2GeographyConfig) XXX_DiscardUnknown Uses

func (m *S2GeographyConfig) XXX_DiscardUnknown()

func (*S2GeographyConfig) XXX_Marshal Uses

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

func (*S2GeographyConfig) XXX_Merge Uses

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

func (*S2GeographyConfig) XXX_Size Uses

func (m *S2GeographyConfig) XXX_Size() int

func (*S2GeographyConfig) XXX_Unmarshal Uses

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

type S2GeometryConfig Uses

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 Uses

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

func (*S2GeometryConfig) Equal Uses

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

func (*S2GeometryConfig) Marshal Uses

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

func (*S2GeometryConfig) MarshalTo Uses

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

func (*S2GeometryConfig) ProtoMessage Uses

func (*S2GeometryConfig) ProtoMessage()

func (*S2GeometryConfig) Reset Uses

func (m *S2GeometryConfig) Reset()

func (*S2GeometryConfig) Size Uses

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

func (*S2GeometryConfig) String Uses

func (m *S2GeometryConfig) String() string

func (*S2GeometryConfig) Unmarshal Uses

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

func (*S2GeometryConfig) XXX_DiscardUnknown Uses

func (m *S2GeometryConfig) XXX_DiscardUnknown()

func (*S2GeometryConfig) XXX_Marshal Uses

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

func (*S2GeometryConfig) XXX_Merge Uses

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

func (*S2GeometryConfig) XXX_Size Uses

func (m *S2GeometryConfig) XXX_Size() int

func (*S2GeometryConfig) XXX_Unmarshal Uses

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

type UnionKeySpans Uses

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 and sorted in increasing order. 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 Uses

func (s UnionKeySpans) String() string

Package geoindex imports 19 packages (graph) and is imported by 15 packages. Updated 2020-08-12. Refresh now. Tools for package owners.