in Microsoft.Azure.Cosmos/src/Query/Core/Pipeline/CrossPartition/OrderBy/OrderByCrossPartitionQueryPipelineStage.cs [1172:1410]
private static (string leftFilter, string targetFilter, string rightFilter) GetFormattedFilters(
ReadOnlyMemory<(OrderByColumn orderByColumn, CosmosElement orderByItem)> columnAndItems)
{
// When we run cross partition queries,
// we only serialize the continuation token for the partition that we left off on.
// The only problem is that when we resume the order by query,
// we don't have continuation tokens for all other partition.
// The saving grace is that the data has a composite sort order(query sort order, partition key range id)
// so we can generate range filters which in turn the backend will turn into rid based continuation tokens,
// which is enough to get the streams of data flowing from all partitions.
// The details of how this is done is described below:
int numOrderByItems = columnAndItems.Length;
bool isSingleOrderBy = numOrderByItems == 1;
StringBuilder left = new StringBuilder();
StringBuilder target = new StringBuilder();
StringBuilder right = new StringBuilder();
(StringBuilder, StringBuilder, StringBuilder) builders = (left, target, right);
if (isSingleOrderBy)
{
//For a single order by query we resume the continuations in this manner
// Suppose the query is SELECT* FROM c ORDER BY c.string ASC
// And we left off on partition N with the value "B"
// Then
// All the partitions to the left will have finished reading "B"
// Partition N is still reading "B"
// All the partitions to the right have let to read a "B
// Therefore the filters should be
// > "B" , >= "B", and >= "B" respectively
// Repeat the same logic for DESC and you will get
// < "B", <= "B", and <= "B" respectively
// The general rule becomes
// For ASC
// > for partitions to the left
// >= for the partition we left off on
// >= for the partitions to the right
// For DESC
// < for partitions to the left
// <= for the partition we left off on
// <= for the partitions to the right
(OrderByColumn orderByColumn, CosmosElement orderByItem) = columnAndItems.Span[0];
(string expression, SortOrder sortOrder) = (orderByColumn.Expression, orderByColumn.SortOrder);
AppendToBuilders(builders, "( ");
// We need to add the filter for within the same type.
if (orderByItem is not CosmosUndefined)
{
StringBuilder sb = new StringBuilder();
CosmosElementToQueryLiteral cosmosElementToQueryLiteral = new CosmosElementToQueryLiteral(sb);
orderByItem.Accept(cosmosElementToQueryLiteral);
string orderByItemToString = sb.ToString();
left.Append($"{expression} {(sortOrder == SortOrder.Descending ? Expressions.LessThan : Expressions.GreaterThan)} {orderByItemToString}");
target.Append($"{expression} {(sortOrder == SortOrder.Descending ? Expressions.LessThanOrEqualTo : Expressions.GreaterThanOrEqualTo)} {orderByItemToString}");
right.Append($"{expression} {(sortOrder == SortOrder.Descending ? Expressions.LessThanOrEqualTo : Expressions.GreaterThanOrEqualTo)} {orderByItemToString}");
}
else
{
// User is ordering by undefined, so we need to avoid a null reference exception.
// What we really want is to support expression > undefined,
// but the engine evaluates to undefined instead of true or false,
// so we work around this by using the IS_DEFINED() system function.
ComparisionWithUndefinedFilters filters = new ComparisionWithUndefinedFilters(expression);
left.Append($"{(sortOrder == SortOrder.Descending ? filters.LessThan : filters.GreaterThan)}");
target.Append($"{(sortOrder == SortOrder.Descending ? filters.LessThanOrEqualTo : filters.GreaterThanOrEqualTo)}");
right.Append($"{(sortOrder == SortOrder.Descending ? filters.LessThanOrEqualTo : filters.GreaterThanOrEqualTo)}");
}
// Now we need to include all the types that match the sort order.
ReadOnlyMemory<string> isDefinedFunctions = orderByItem.Accept(CosmosElementToIsSystemFunctionsVisitor.Singleton, sortOrder == SortOrder.Ascending);
foreach (string isDefinedFunction in isDefinedFunctions.Span)
{
AppendToBuilders(builders, " OR ");
AppendToBuilders(builders, $"{isDefinedFunction}({expression})");
}
AppendToBuilders(builders, " )");
}
else
{
//For a multi order by query
// Suppose the query is SELECT* FROM c ORDER BY c.string ASC, c.number ASC
// And we left off on partition N with the value("A", 1)
// Then
// All the partitions to the left will have finished reading("A", 1)
// Partition N is still reading("A", 1)
// All the partitions to the right have let to read a "(A", 1)
// The filters are harder to derive since their are multiple columns
// But the problem reduces to "How do you know one document comes after another in a multi order by query"
// The answer is to just look at it one column at a time.
// For this particular scenario:
// If a first column is greater ex. ("B", blah), then the document comes later in the sort order
// Therefore we want all documents where the first column is greater than "A" which means > "A"
// Or if the first column is a tie, then you look at the second column ex. ("A", blah).
// Therefore we also want all documents where the first column was a tie but the second column is greater which means = "A" AND > 1
// Therefore the filters should be
// (> "A") OR (= "A" AND > 1), (> "A") OR (= "A" AND >= 1), (> "A") OR (= "A" AND >= 1)
// Notice that if we repeated the same logic we for single order by we would have gotten
// > "A" AND > 1, >= "A" AND >= 1, >= "A" AND >= 1
// which is wrong since we missed some documents
// Repeat the same logic for ASC, DESC
// (> "A") OR (= "A" AND < 1), (> "A") OR (= "A" AND <= 1), (> "A") OR (= "A" AND <= 1)
// Again for DESC, ASC
// (< "A") OR (= "A" AND > 1), (< "A") OR (= "A" AND >= 1), (< "A") OR (= "A" AND >= 1)
// And again for DESC DESC
// (< "A") OR (= "A" AND < 1), (< "A") OR (= "A" AND <= 1), (< "A") OR (= "A" AND <= 1)
// The general we look at all prefixes of the order by columns to look for tie breakers.
// Except for the full prefix whose last column follows the rules for single item order by
// And then you just OR all the possibilities together
for (int prefixLength = 1; prefixLength <= numOrderByItems; prefixLength++)
{
ReadOnlySpan<(OrderByColumn orderByColumn, CosmosElement orderByItem)> columnAndItemPrefix = columnAndItems.Span.Slice(start: 0, length: prefixLength);
bool lastPrefix = prefixLength == numOrderByItems;
AppendToBuilders(builders, "(");
for (int index = 0; index < prefixLength; index++)
{
string expression = columnAndItemPrefix[index].orderByColumn.Expression;
SortOrder sortOrder = columnAndItemPrefix[index].orderByColumn.SortOrder;
CosmosElement orderByItem = columnAndItemPrefix[index].orderByItem;
bool lastItem = index == prefixLength - 1;
AppendToBuilders(builders, "(");
bool wasInequality;
// We need to add the filter for within the same type.
if (orderByItem is CosmosUndefined)
{
ComparisionWithUndefinedFilters filters = new ComparisionWithUndefinedFilters(expression);
// Refer to the logic from single order by for how we are handling order by undefined
if (lastItem)
{
if (lastPrefix)
{
if (sortOrder == SortOrder.Descending)
{
// <, <=, <=
AppendToBuilders(builders, filters.LessThan, filters.LessThanOrEqualTo, filters.LessThanOrEqualTo);
}
else
{
// >, >=, >=
AppendToBuilders(builders, filters.GreaterThan, filters.GreaterThanOrEqualTo, filters.GreaterThanOrEqualTo);
}
}
else
{
if (sortOrder == SortOrder.Descending)
{
// <, <, <
AppendToBuilders(builders, filters.LessThan, filters.LessThan, filters.LessThan);
}
else
{
// >, >, >
StreamingOrderByCrossPartitionQueryPipelineStage.AppendToBuilders(builders, filters.GreaterThan, filters.GreaterThan, filters.GreaterThan);
}
}
wasInequality = true;
}
else
{
// =, =, =
AppendToBuilders(builders, filters.EqualTo);
wasInequality = false;
}
}
else
{
// Append Expression
AppendToBuilders(builders, expression);
AppendToBuilders(builders, " ");
// Append Binary Operator
if (lastItem)
{
string inequality = sortOrder == SortOrder.Descending ? Expressions.LessThan : Expressions.GreaterThan;
AppendToBuilders(builders, inequality);
if (lastPrefix)
{
AppendToBuilders(builders, string.Empty, Expressions.EqualTo, Expressions.EqualTo);
}
wasInequality = true;
}
else
{
AppendToBuilders(builders, Expressions.EqualTo);
wasInequality = false;
}
// Append OrderBy Item
StringBuilder sb = new StringBuilder();
CosmosElementToQueryLiteral cosmosElementToQueryLiteral = new CosmosElementToQueryLiteral(sb);
orderByItem.Accept(cosmosElementToQueryLiteral);
string orderByItemToString = sb.ToString();
AppendToBuilders(builders, " ");
AppendToBuilders(builders, orderByItemToString);
AppendToBuilders(builders, " ");
}
if (wasInequality)
{
// Now we need to include all the types that match the sort order.
ReadOnlyMemory<string> isDefinedFunctions = orderByItem.Accept(CosmosElementToIsSystemFunctionsVisitor.Singleton, sortOrder == SortOrder.Ascending);
foreach (string isDefinedFunction in isDefinedFunctions.Span)
{
AppendToBuilders(builders, " OR ");
AppendToBuilders(builders, $"{isDefinedFunction}({expression}) ");
}
}
AppendToBuilders(builders, ")");
if (!lastItem)
{
AppendToBuilders(builders, " AND ");
}
}
AppendToBuilders(builders, ")");
if (!lastPrefix)
{
AppendToBuilders(builders, " OR ");
}
}
}
return (left.ToString(), target.ToString(), right.ToString());
}