Database governance built for humans and agents — controlling changes and access across every major database.
Go cicddata-governancedata-maskingdata-securitydatabase-accessdatabase-governancedevopsdevsecopsflywaygitopsliquibasemongodbmysqloraclepostgresqlschema-migrationssecuritysql-clientsqlservertidb
package gonative
import (
"bytes"
"encoding/json"
"slices"
"strings"
"github.com/Azure/azure-sdk-for-go/sdk/data/azcosmos/queryengine"
"github.com/pkg/errors"
)
// groupByItem is one entry in the per-document groupByItems array. For a
// single-key GROUP BY the array has one element; multi-key GROUP BY would
// have more, and needs no special handling here because the engine hashes and
// orders the whole array.
type groupByItem struct {
Item json.RawMessage `json:"item"`
}
// groupDoc is one Documents[i] entry in a GROUP BY per-partition response.
type groupDoc struct {
GroupByItems []groupByItem `json:"groupByItems"`
Payload map[string]json.RawMessage `json:"payload"`
}
// groupPartitionResponse decodes a GROUP BY per-partition body.
type groupPartitionResponse struct {
Documents []groupDoc `json:"Documents"`
}
func parseGroupPartitionResponse(raw []byte) (*groupPartitionResponse, error) {
var r groupPartitionResponse
if err := json.Unmarshal(raw, &r); err != nil {
return nil, errors.Wrap(err, "gonative: parse group partition response")
}
return &r, nil
}
// groupState accumulates one group's worth of aggregate partials across every
// partition that contributed to that group. Group-key columns are captured
// once (they're identical for every partition that reports this key).
type groupState struct {
// keyValues holds the raw payload value for each group-key column, in the
// order those aliases appear in groupByAliases. The first partition to
// report a given group populates these; subsequent partitions overwrite
// with the same value (Cosmos guarantees equality).
keyValues map[string]json.RawMessage
// items is the group's key as the gateway reported it, kept for ordering
// the output rows.
items []groupByItem
// aggregators are ordered per groupByAliases; entries whose alias is a
// group-key column are nil.
aggregators []aggregator
}
// groupPipeline implements queryengine.QueryPipeline for plans with GROUP BY.
// It collects per-partition group contributions into a hash map keyed on the
// canonical JSON of groupByItems, then emits one row per group once every
// partition has delivered.
//
// GROUP BY is non-streaming — all partitions must arrive before any row is
// emitted, and a partition that answers over several pages must be read to its
// last page. Memory is bounded by the cardinality of distinct group keys, not
// by the total row count across partitions.
type groupPipeline struct {
query string
fanout rangeFanout
closed bool
// aliases preserves the order of groupByAliases; kinds[i] is the
// aggregate kind for aliases[i] ("" when the alias is a group-key column).
aliases []string
kinds []string
// groups is the per-group state, keyed on the canonical JSON of
// groupByItems. Grows to the cardinality of distinct group keys.
groups map[string]*groupState
// order holds those keys in the order the groups were first seen, which
// is what the output falls back to when the keys cannot be ordered.
order []string
// sort is how to order the output rows: which group key to compare
// first, which way, and how strictly — see groupSortKeys.
sort []groupSortKey
// pending holds fully finalized rows awaiting the caller's next Run().
pending [][]byte
// finalized is true after the first post-drain Run() has built the pending
// set; subsequent Runs just flush.
finalized bool
}
// newGroupPipeline builds a pipeline for a GROUP BY plan. It extracts the
// alias order and per-alias aggregate kinds from the plan's groupByAliases
// and groupByAliasToAggregateType fields; any alias missing from the map is
// treated as a group-key column.
//
// Composing GROUP BY with TOP, OFFSET/LIMIT or DISTINCT would mean wrapping
// this pipeline in another operator; CreateQueryPipeline rejects those plans
// before they reach here.
func newGroupPipeline(plan *planDoc, pkRangeIDs []string) (*groupPipeline, error) {
qi := plan.QueryInfo
if len(qi.GroupByExpressions) == 0 {
return nil, errors.New("gonative: groupPipeline requires groupByExpressions")
}
if len(qi.GroupByAliases) == 0 {
return nil, errors.New("gonative: groupPipeline requires groupByAliases")
}
aliases := append([]string(nil), qi.GroupByAliases...)
kinds := make([]string, len(aliases))
for i, alias := range aliases {
kind, ok := qi.GroupByAliasToAggregateType[alias]
if !ok {
// Alias exists in the output but has no map entry. Treat as a
// group-key column.
kinds[i] = ""
continue
}
kinds[i] = kind
if kind != "" {
if a := newAggregator(kind); a == nil {
return nil, errors.Errorf("gonative: unsupported aggregate kind %q for alias %q", kind, alias)
}
}
}
sortKeys, err := groupSortKeys(qi)
if err != nil {
return nil, err
}
return &groupPipeline{
// GROUP BY plans always carry a non-empty rewrittenQuery that wraps the
// user's projection into {groupByItems, payload}; running the original
// query instead would return raw rows with no groupByItems field.
query: qi.RewrittenQuery,
fanout: newRangeFanout(pkRangeIDs),
aliases: aliases,
kinds: kinds,
groups: make(map[string]*groupState),
sort: sortKeys,
}, nil
}
// Query implements queryengine.QueryPipeline.
func (p *groupPipeline) Query() string { return p.query }
// IsComplete returns true once every range has delivered its last page and
// every finalized row has been flushed to the caller.
func (p *groupPipeline) IsComplete() bool {
if len(p.pending) > 0 {
return false
}
return p.fanout.allDrained() && p.finalized
}
// Close implements queryengine.QueryPipeline.
func (p *groupPipeline) Close() { p.closed = true }
// Run drives one pipeline turn:
// 1. Ask for the next page of every range that has one — the initial fan-out
// across all ranges on the first call.
// 2. Once every range has drained, build the output rows by finalizing each
// group's aggregators and emitting in alias order.
// 3. Flush pending rows on subsequent calls until drained.
func (p *groupPipeline) Run() (*queryengine.PipelineResult, error) {
if reqs := p.fanout.requests(p.query); len(reqs) > 0 {
return &queryengine.PipelineResult{Requests: reqs}, nil
}
if !p.finalized && p.fanout.allDrained() {
if err := p.finalize(); err != nil {
return nil, err
}
}
if len(p.pending) > 0 {
batch := p.pending
p.pending = nil
return &queryengine.PipelineResult{Items: batch, IsCompleted: p.IsComplete()}, nil
}
return &queryengine.PipelineResult{IsCompleted: p.IsComplete()}, nil
}
// ProvideData consumes each partition's response and folds every row into the
// appropriate group's state.
func (p *groupPipeline) ProvideData(results []queryengine.QueryResult) error {
for _, r := range results {
if err := p.fanout.note(r); err != nil {
return err
}
resp, err := parseGroupPartitionResponse(r.Data)
if err != nil {
return err
}
for docIdx, doc := range resp.Documents {
if len(doc.GroupByItems) == 0 {
return errors.Errorf("gonative: group doc %d missing groupByItems", docIdx)
}
key, err := groupKey(doc.GroupByItems)
if err != nil {
return err
}
state, ok := p.groups[key]
if !ok {
state = p.initGroupState(doc)
p.groups[key] = state
p.order = append(p.order, key)
}
// Merge this partition's aggregate contributions into the group's state.
for i, alias := range p.aliases {
if p.kinds[i] == "" {
// Group-key column: set once; subsequent partitions carry
// the same value so no work needed.
continue
}
rawItem, ok := doc.Payload[alias]
if !ok {
return errors.Errorf("gonative: group doc %d missing payload alias %q", docIdx, alias)
}
// The payload value is shaped {"item": <partial> [, "item2": ...]}.
partial, err := extractAggregatePartial(p.kinds[i], rawItem)
if err != nil {
return err
}
if err := state.aggregators[i].feedPartial(partial); err != nil {
return err
}
}
}
}
return nil
}
// initGroupState creates a fresh state for a newly-seen group key. Captures
// the group-key column values from the first document reporting this key
// (they're identical for every subsequent partition reporting the same key)
// and allocates aggregators for the aggregate columns.
func (p *groupPipeline) initGroupState(doc groupDoc) *groupState {
s := &groupState{
keyValues: make(map[string]json.RawMessage, len(p.aliases)),
items: append([]groupByItem(nil), doc.GroupByItems...),
aggregators: make([]aggregator, len(p.aliases)),
}
for i, alias := range p.aliases {
if p.kinds[i] == "" {
// Group-key column: store raw value.
if v, ok := doc.Payload[alias]; ok {
s.keyValues[alias] = append([]byte(nil), v...)
}
} else {
s.aggregators[i] = newAggregator(p.kinds[i])
}
}
return s
}
// finalize produces one output row per group, in group-key order — see
// sortGroups. Walking p.groups instead would emit them in Go's randomized map
// order, which made the same query answer in a different order every run.
func (p *groupPipeline) finalize() error {
if err := p.sortGroups(); err != nil {
return err
}
for _, key := range p.order {
row, err := p.buildRow(p.groups[key])
if err != nil {
return err
}
p.pending = append(p.pending, row)
}
p.finalized = true
return nil
}
// orderByKeyword is how the gateway spells the clause in a rewritten query.
const orderByKeyword = "ORDER BY"
// orderByKey is one key of an ORDER BY clause.
type orderByKey struct {
expr string
descending bool
}
// groupSortKey names one group key to order the output rows by: its position
// in groupByItems, which way to compare it, and whether the query named it.
//
// A key the query named has to be compared the service's way or not at all. A
// key appended to settle ties the clause says nothing about takes any
// repeatable order, so it is compared with compareItemsTotal and never fails.
type groupSortKey struct {
index int
descending bool
named bool
}
// groupSortKeys works out how to order a GROUP BY's output rows. A GROUP BY
// the user also ordered reaches the engine as a plan with no order fields at
// all — orderBy and orderByExpressions stay empty and the ORDER BY survives
// only inside the rewritten query — so the clause is read from that text.
//
// The engine orders these rows by comparing their group keys, so every key the
// clause names must be one of the GROUP BY expressions. An order it cannot
// produce that way — by an aggregate, or by a column the query does not group
// by — fails the query rather than answering in an order nobody asked for. The
// gateway refuses those queries itself today, so this is the engine holding the
// line rather than a reachable error.
//
// Group keys the clause leaves out are appended ascending. The clause does not
// constrain them, and ordering them too is what makes two runs of one query
// answer alike.
func groupSortKeys(qi planQueryInfo) ([]groupSortKey, error) {
keys, found := trailingOrderBy(qi.RewrittenQuery)
if found && len(keys) == 0 {
return nil, errors.Wrap(ErrUnsupportedPlanFeature, "ORDER BY is not a plain list of keys")
}
sortKeys := make([]groupSortKey, 0, len(qi.GroupByExpressions))
named := make([]bool, len(qi.GroupByExpressions))
for _, key := range keys {
index := slices.Index(qi.GroupByExpressions, key.expr)
if index < 0 {
return nil, errors.Wrapf(ErrUnsupportedPlanFeature,
"ORDER BY key %q is not one of the GROUP BY expressions", key.expr)
}
if named[index] {
continue
}
named[index] = true
sortKeys = append(sortKeys, groupSortKey{index: index, descending: key.descending, named: true})
}
for index, taken := range named {
if !taken {
sortKeys = append(sortKeys, groupSortKey{index: index})
}
}
return sortKeys, nil
}
// trailingOrderBy splits the ORDER BY clause that ends query into its keys.
// found is false when the query has no trailing ORDER BY; keys is nil with
// found true when the clause is not the plain `<expression> [ASC|DESC]` list
// the gateway writes there, which the caller must treat as an order it cannot
// honour rather than as no order at all.
//
// The words are matched outside quoted text, so a property path that needs
// bracket notation — c["order by"] — is a key and not a clause, whichever it
// is spelled as.
//
// The keys are plain property paths because that is all the service allows a
// grouped query to order by: `GROUP BY SUBSTRING(c.x, 0, 1) ORDER BY
// SUBSTRING(c.x, 0, 1)` is refused outright with SC2103, "not contained in
// either an aggregate function or the GROUP BY clause", however exactly the
// two spellings match. So a key here holds no comma and no bracketed
// arithmetic of its own.
func trailingOrderBy(query string) (keys []orderByKey, found bool) {
at := lastUnquotedIndex(query, orderByKeyword)
if at < 0 {
return nil, false
}
tail := query[at+len(orderByKeyword):]
for _, item := range splitUnquoted(tail, ',') {
fields := splitUnquoted(item, ' ', '\t', '\n', '\r')
var key orderByKey
switch len(fields) {
case 1:
key.expr = fields[0]
case 2:
key.expr = fields[0]
switch strings.ToUpper(fields[1]) {
case "ASC":
case "DESC":
key.descending = true
default:
return nil, true
}
default:
return nil, true
}
keys = append(keys, key)
}
if len(keys) == 0 {
return nil, true
}
return keys, true
}
// lastUnquotedIndex returns the last index at which needle occurs in s outside
// quoted text, ignoring case, or -1.
func lastUnquotedIndex(s, needle string) int {
quoted := quotedBytes(s)
for i := len(s) - len(needle); i >= 0; i-- {
if !quoted[i] && strings.EqualFold(s[i:i+len(needle)], needle) {
return i
}
}
return -1
}
// splitUnquoted splits s on any of seps that sits outside quoted text,
// dropping empty pieces so runs of whitespace behave like one separator.
func splitUnquoted(s string, seps ...byte) []string {
quoted := quotedBytes(s)
var out []string
start := -1
for i := range len(s) {
if !quoted[i] && slices.Contains(seps, s[i]) {
if start >= 0 {
out = append(out, s[start:i])
start = -1
}
continue
}
if start < 0 {
start = i
}
}
if start >= 0 {
out = append(out, s[start:])
}
return out
}
// quotedBytes marks the bytes of s that sit inside quoted text. A rewritten
// query quotes a property path spelled in bracket notation and any string
// literal the query compares against, and the words of a clause mean nothing
// inside either.
func quotedBytes(s string) []bool {
quoted := make([]bool, len(s))
var quote byte
for i := 0; i < len(s); i++ {
c := s[i]
if quote == 0 {
if c == '"' || c == '\'' {
quote = c
quoted[i] = true
}
continue
}
quoted[i] = true
if c == '\\' && i+1 < len(s) {
// An escaped quote does not close the span, and the byte it
// escapes is inside it either way.
i++
quoted[i] = true
continue
}
if c == quote {
quote = 0
}
}
return quoted
}
// sortGroups puts p.order in group-key order, in the direction the query asked
// for. Each key carries how strictly it is compared — see groupSortKey — so a
// key the query named fails rather than take an invented order, while one
// appended to settle ties takes any repeatable one.
func (p *groupPipeline) sortGroups() error {
var failed error
slices.SortStableFunc(p.order, func(a, b string) int {
order, err := compareGroupKeys(p.groups[a].items, p.groups[b].items, p.sort)
if err != nil && failed == nil {
failed = err
}
return order
})
return failed
}
// compareGroupKeys orders two group keys under Cosmos item ordering, comparing
// the columns sortKeys names in the order, direction and strictness it gives.
func compareGroupKeys(a, b []groupByItem, sortKeys []groupSortKey) (int, error) {
for _, key := range sortKeys {
if key.index >= len(a) || key.index >= len(b) {
continue
}
cmp := compareItemsTotal
if key.named {
cmp = compareItems
}
order, err := cmp(a[key.index].Item, b[key.index].Item)
if err != nil {
return 0, err
}
if order != 0 {
if key.descending {
return -order, nil
}
return order, nil
}
}
return len(a) - len(b), nil
}
// isUndefinedItem reports whether a groupByItems entry carries no value,
// which is how the gateway spells a key the document does not define.
func isUndefinedItem(raw json.RawMessage) bool {
return len(bytes.TrimLeft(raw, " \t\n\r")) == 0
}
// buildRow assembles the final JSON object for a single group, preserving
// the alias order from groupByAliases. JSON object key order in Go's encoder
// depends on sort for map marshaling, so we write the object manually.
//
// An alias whose aggregate has no value — MIN or MAX over a group where the
// column is undefined in every row — is left out of the object, which is how
// the gateway spells it.
func (p *groupPipeline) buildRow(s *groupState) ([]byte, error) {
var buf []byte
buf = append(buf, '{')
for i, alias := range p.aliases {
var value json.RawMessage
if p.kinds[i] == "" {
v, ok := s.keyValues[alias]
if !ok {
// The group's key is undefined here, and the service answers
// that with the alias left out of the row.
continue
}
value = v
} else {
final, err := s.aggregators[i].finalize()
if err != nil {
return nil, err
}
if final == nil {
continue
}
value = final
}
if len(buf) > 1 {
buf = append(buf, ',')
}
aliasJSON, err := json.Marshal(alias)
if err != nil {
return nil, err
}
buf = append(buf, aliasJSON...)
buf = append(buf, ':')
buf = append(buf, value...)
}
buf = append(buf, '}')
return buf, nil
}
// groupKey returns a canonical hash key for a groupByItems array. The key is
// the canonical JSON of the array — equal keys produce equal bytes.
func groupKey(items []groupByItem) (string, error) {
// Build a slice of the inner "item" values, canonicalize each, then join.
// Using a combined key of canonicalized element JSON keeps equality
// deterministic even for complex multi-key GROUP BY.
//
// A key the documents leave undefined arrives with no "item" at all. It is
// a group of its own — the service counts it apart from an explicit null —
// so each part is wrapped in an array and an undefined one is the empty
// array, which no value's canonical form can collide with.
parts := make([]json.RawMessage, len(items))
for i, it := range items {
if isUndefinedItem(it.Item) {
parts[i] = json.RawMessage(`[]`)
continue
}
c, err := canonicalJSON(it.Item)
if err != nil {
return "", errors.Wrapf(err, "gonative: canonicalize group key part %d", i)
}
parts[i] = append(append(json.RawMessage{'['}, c...), ']')
}
b, err := json.Marshal(parts)
if err != nil {
return "", errors.Wrap(err, "gonative: marshal group key")
}
return string(b), nil
}
// extractAggregatePartial decodes the payload value for an aggregate alias
// into the shape the corresponding aggregator's feedPartial expects.
//
// The wire format is {"item": <direct value> [, "item2": {"min"|"max":...,
// "count":...}]}. For Count/Sum/Avg the aggregator consumes "item" directly.
// For Min/Max: prefer "item2" (the reliable cross-partition partial carrying
// count); fall back to synthesizing a single-count partial from "item" when
// item2 is absent — see aggregatePartial, which both aggregate pipelines and
// this one route through.
func extractAggregatePartial(kind string, raw json.RawMessage) (json.RawMessage, error) {
var wrap aggItem
if err := json.Unmarshal(raw, &wrap); err != nil {
return nil, errors.Wrap(err, "gonative: extract aggregate partial")
}
return aggregatePartial(kind, wrap), nil
}