This is an automated email from the ASF dual-hosted git repository.
yiguolei pushed a commit to branch branch-4.1
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/branch-4.1 by this push:
new 84fc354a861 branch-4.1: [perf](s3) push down expandable S3 glob
prefixes (#65621)
84fc354a861 is described below
commit 84fc354a861c943e6c8c4654a77731a7c4c80264
Author: hui lai <[email protected]>
AuthorDate: Thu Jul 16 11:05:02 2026 +0800
branch-4.1: [perf](s3) push down expandable S3 glob prefixes (#65621)
pick https://github.com/apache/doris/pull/64684
Backport the expandable S3 glob-prefix pushdown to branch-4.1's legacy
S3 object-storage implementation.
Validation:
- `git diff --check`
- `mvn -pl fe-core -DskipTests validate`
Targeted unit tests require the release branch's generated Thrift
classes and locally built FE SNAPSHOT modules, so CI `buildall` will run
the complete validation.
---
.../java/org/apache/doris/common/util/S3Util.java | 268 +++++++++++++++++++++
.../java/org/apache/doris/fs/obj/S3ObjStorage.java | 156 ++++++------
.../org/apache/doris/common/util/S3UtilTest.java | 31 ++-
.../org/apache/doris/fs/obj/S3ObjStorageTest.java | 53 ++++
4 files changed, 431 insertions(+), 77 deletions(-)
diff --git a/fe/fe-core/src/main/java/org/apache/doris/common/util/S3Util.java
b/fe/fe-core/src/main/java/org/apache/doris/common/util/S3Util.java
index 3e4f4e7a62f..f63f0be3c7a 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/common/util/S3Util.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/common/util/S3Util.java
@@ -54,15 +54,20 @@ import
software.amazon.awssdk.services.sts.auth.StsAssumeRoleCredentialsProvider
import java.net.HttpURLConnection;
import java.net.URI;
import java.net.URL;
+import java.nio.charset.StandardCharsets;
import java.time.Duration;
import java.util.ArrayList;
import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.List;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class S3Util {
private static final Logger LOG = LogManager.getLogger(Util.class);
+ private static final int MAX_EXPANDED_GLOB_LIST_PREFIXES = 256;
+ private static final Comparator<String> UTF8_BINARY_ORDER =
S3Util::compareUtf8Binary;
private static AwsCredentialsProvider
getAwsCredencialsProvider(CloudCredential credential) {
AwsCredentials awsCredential;
@@ -302,6 +307,269 @@ public class S3Util {
return globPattern.substring(0, earliestSpecialCharIndex);
}
+ /**
+ * Returns object-store list prefixes that are safe to push down for a
glob pattern.
+ * Bounded brace alternatives and positive character classes are expanded
before the first
+ * unbounded wildcard. Unsafe or oversized expansions fall back to the
longest static prefix.
+ */
+ public static List<String> getGlobListPrefixes(String globPattern) {
+ List<String> prefixes = expandGlobListPrefixes(globPattern, true);
+ return prefixes == null ?
Collections.singletonList(getLongestPrefix(globPattern)) : prefixes;
+ }
+
+ private static List<String> expandGlobListPrefixes(String globPattern,
boolean allowPartialPrefix) {
+ List<String> prefixes = new ArrayList<>();
+ prefixes.add("");
+ int i = 0;
+ while (i < globPattern.length()) {
+ char c = globPattern.charAt(i);
+ if (c == '*' || c == '?') {
+ return allowPartialPrefix ? compactPrefixes(prefixes) : null;
+ }
+ if (c == '\\') {
+ if (i + 1 < globPattern.length()) {
+ appendLiteral(prefixes, globPattern.charAt(i + 1));
+ i += 2;
+ } else {
+ appendLiteral(prefixes, c);
+ i++;
+ }
+ continue;
+ }
+ if (c == '[') {
+ PrefixExpansion charClass = expandCharacterClass(globPattern,
i);
+ if (charClass == null) {
+ return allowPartialPrefix ? compactPrefixes(prefixes) :
null;
+ }
+ prefixes = appendAlternatives(prefixes, charClass.values);
+ if (prefixes == null) {
+ return null;
+ }
+ i = charClass.nextIndex;
+ continue;
+ }
+ if (c == '{') {
+ PrefixExpansion brace = expandBraceGroup(globPattern, i);
+ if (brace == null) {
+ return allowPartialPrefix ? compactPrefixes(prefixes) :
null;
+ }
+ prefixes = appendAlternatives(prefixes, brace.values);
+ if (prefixes == null) {
+ return null;
+ }
+ i = brace.nextIndex;
+ continue;
+ }
+ appendLiteral(prefixes, c);
+ i++;
+ }
+ return compactPrefixes(prefixes);
+ }
+
+ private static void appendLiteral(List<String> prefixes, char c) {
+ for (int i = 0; i < prefixes.size(); i++) {
+ prefixes.set(i, prefixes.get(i) + c);
+ }
+ }
+
+ private static List<String> appendAlternatives(List<String> prefixes,
List<String> alternatives) {
+ long expandedSize = (long) prefixes.size() * alternatives.size();
+ if (expandedSize > MAX_EXPANDED_GLOB_LIST_PREFIXES) {
+ return null;
+ }
+ List<String> expanded = new ArrayList<>((int) expandedSize);
+ for (String prefix : prefixes) {
+ for (String alternative : alternatives) {
+ expanded.add(prefix + alternative);
+ }
+ }
+ return expanded;
+ }
+
+ private static PrefixExpansion expandCharacterClass(String globPattern,
int openIndex) {
+ int closeIndex = findClosingBracket(globPattern, openIndex);
+ if (closeIndex < 0 || closeIndex == openIndex + 1) {
+ return null;
+ }
+ int i = openIndex + 1;
+ char first = globPattern.charAt(i);
+ if (first == '!' || first == '^') {
+ return null;
+ }
+ if (containsSurrogate(globPattern, i, closeIndex)) {
+ return null;
+ }
+ List<String> values = new ArrayList<>();
+ while (i < closeIndex) {
+ char current = globPattern.charAt(i);
+ if (current == '\\') {
+ if (i + 1 >= closeIndex) {
+ return null;
+ }
+ values.add(String.valueOf(globPattern.charAt(i + 1)));
+ i += 2;
+ continue;
+ }
+ if (i + 2 < closeIndex && globPattern.charAt(i + 1) == '-') {
+ char rangeEnd = globPattern.charAt(i + 2);
+ int step = current <= rangeEnd ? 1 : -1;
+ for (char ch = current; step > 0 ? ch <= rangeEnd : ch >=
rangeEnd; ch += step) {
+ values.add(String.valueOf(ch));
+ if (values.size() > MAX_EXPANDED_GLOB_LIST_PREFIXES) {
+ return null;
+ }
+ }
+ i += 3;
+ continue;
+ }
+ values.add(String.valueOf(current));
+ i++;
+ }
+ return new PrefixExpansion(values, closeIndex + 1);
+ }
+
+ private static int findClosingBracket(String globPattern, int openIndex) {
+ for (int i = openIndex + 1; i < globPattern.length(); i++) {
+ char c = globPattern.charAt(i);
+ if (c == '\\') {
+ i++;
+ continue;
+ }
+ if (c == ']') {
+ return i;
+ }
+ }
+ return -1;
+ }
+
+ private static boolean containsSurrogate(String text, int start, int end) {
+ for (int i = start; i < end; i++) {
+ if (Character.isSurrogate(text.charAt(i))) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private static PrefixExpansion expandBraceGroup(String globPattern, int
openIndex) {
+ int closeIndex = findClosingBrace(globPattern, openIndex);
+ if (closeIndex < 0) {
+ return null;
+ }
+ List<String> alternatives = splitBraceAlternatives(
+ globPattern.substring(openIndex + 1, closeIndex));
+ if (alternatives.isEmpty()) {
+ return null;
+ }
+ List<String> values = new ArrayList<>();
+ for (String alternative : alternatives) {
+ List<String> expandedAlternative =
expandGlobListPrefixes(alternative, false);
+ if (expandedAlternative == null) {
+ return null;
+ }
+ values.addAll(expandedAlternative);
+ if (values.size() > MAX_EXPANDED_GLOB_LIST_PREFIXES) {
+ return null;
+ }
+ }
+ return new PrefixExpansion(values, closeIndex + 1);
+ }
+
+ private static int findClosingBrace(String globPattern, int openIndex) {
+ int depth = 0;
+ for (int i = openIndex; i < globPattern.length(); i++) {
+ char c = globPattern.charAt(i);
+ if (c == '\\') {
+ i++;
+ continue;
+ }
+ if (c == '{') {
+ depth++;
+ } else if (c == '}') {
+ depth--;
+ if (depth == 0) {
+ return i;
+ }
+ }
+ }
+ return -1;
+ }
+
+ private static List<String> splitBraceAlternatives(String content) {
+ List<String> alternatives = new ArrayList<>();
+ int depth = 0;
+ int start = 0;
+ for (int i = 0; i < content.length(); i++) {
+ char c = content.charAt(i);
+ if (c == '\\') {
+ i++;
+ continue;
+ }
+ if (c == '{') {
+ depth++;
+ } else if (c == '}') {
+ if (depth == 0) {
+ return Collections.emptyList();
+ }
+ depth--;
+ } else if (c == ',' && depth == 0) {
+ alternatives.add(content.substring(start, i));
+ start = i + 1;
+ }
+ }
+ if (depth != 0) {
+ return Collections.emptyList();
+ }
+ alternatives.add(content.substring(start));
+ return alternatives;
+ }
+
+ private static List<String> compactPrefixes(List<String> prefixes) {
+ List<String> sorted = new ArrayList<>(prefixes);
+ sorted.sort(UTF8_BINARY_ORDER);
+ List<String> compact = new ArrayList<>();
+ for (String prefix : sorted) {
+ if (prefix.isEmpty()) {
+ return Collections.singletonList("");
+ }
+ boolean covered = false;
+ for (String existing : compact) {
+ if (prefix.startsWith(existing)) {
+ covered = true;
+ break;
+ }
+ }
+ if (!covered) {
+ compact.add(prefix);
+ }
+ }
+ return compact;
+ }
+
+ private static int compareUtf8Binary(String left, String right) {
+ byte[] leftBytes = left.getBytes(StandardCharsets.UTF_8);
+ byte[] rightBytes = right.getBytes(StandardCharsets.UTF_8);
+ int commonLength = Math.min(leftBytes.length, rightBytes.length);
+ for (int i = 0; i < commonLength; i++) {
+ int result = Integer.compare(
+ Byte.toUnsignedInt(leftBytes[i]),
Byte.toUnsignedInt(rightBytes[i]));
+ if (result != 0) {
+ return result;
+ }
+ }
+ return Integer.compare(leftBytes.length, rightBytes.length);
+ }
+
+ private static class PrefixExpansion {
+ private final List<String> values;
+ private final int nextIndex;
+
+ private PrefixExpansion(List<String> values, int nextIndex) {
+ this.values = values;
+ this.nextIndex = nextIndex;
+ }
+ }
+
// Apply some rules to extend the globs parsing behavior
public static String extendGlobs(String pathPattern) {
return extendGlobNumberRange(pathPattern);
diff --git a/fe/fe-core/src/main/java/org/apache/doris/fs/obj/S3ObjStorage.java
b/fe/fe-core/src/main/java/org/apache/doris/fs/obj/S3ObjStorage.java
index a92f5549285..5f14506c4de 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/fs/obj/S3ObjStorage.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/fs/obj/S3ObjStorage.java
@@ -88,6 +88,7 @@ import java.nio.file.FileSystems;
import java.nio.file.PathMatcher;
import java.nio.file.Paths;
import java.util.ArrayList;
+import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
@@ -683,9 +684,11 @@ public class S3ObjStorage implements ObjStorage<S3Client> {
LOG.debug("globList listPrefix: '{}' (from globPath: '{}')",
listPrefix, globPath);
}
- // For Directory Buckets, ensure proper prefix handling using
standardized approach
+ // For Directory Buckets, ensure proper prefix handling using
standardized approach.
+ // Other S3-compatible stores can safely expand bounded glob
fragments into narrower
+ // list prefixes, while still applying the complete glob matcher
to returned keys.
finalPrefix = listPrefix;
-
+ List<String> listPrefixes;
if (!hasLimits && uri.useS3DirectoryBucket()) {
String adjustedPrefix =
S3URI.getDirectoryPrefixForGlob(listPrefix);
if (LOG.isDebugEnabled() &&
!adjustedPrefix.equals(listPrefix)) {
@@ -693,92 +696,93 @@ public class S3ObjStorage implements ObjStorage<S3Client>
{
listPrefix, adjustedPrefix);
}
finalPrefix = adjustedPrefix;
+ listPrefixes = Collections.singletonList(adjustedPrefix);
+ } else {
+ listPrefixes = S3Util.getGlobListPrefixes(globPath);
}
- Builder builder = ListObjectsV2Request.builder()
- .bucket(bucket)
- .prefix(finalPrefix);
-
- if (startFile != null) {
- builder.startAfter(startFile);
- }
-
- ListObjectsV2Request request = builder.build();
-
- boolean isTruncated = false;
boolean reachLimit = false;
String lastMatchedKey = "";
- do {
- roundCnt++;
- ListObjectsV2Response response = listObjectsV2(request);
- for (S3Object obj : response.contents()) {
- elementCnt++;
-
- // Limit already reached: scan remaining objects in this
page to find
- // the next glob-matching key, so hasMoreDataToConsume()
returns true
- // correctly without recording a non-matching raw S3 key
as currentMaxFile.
- if (reachLimit) {
- java.nio.file.Path checkPath = Paths.get(obj.key());
- if (matcher.matches(checkPath)) {
- currentMaxFile = obj.key();
- break;
- }
- continue;
- }
-
- java.nio.file.Path objPath = Paths.get(obj.key());
-
- boolean isPrefix = false;
- while (objPath != null &&
objPath.normalize().toString().startsWith(listPrefix)) {
- if (!matcher.matches(objPath)) {
- isPrefix = true;
- objPath = objPath.getParent();
+ listPrefixesLoop:
+ for (String currentListPrefix : listPrefixes) {
+ Builder builder = ListObjectsV2Request.builder()
+ .bucket(bucket)
+ .prefix(currentListPrefix);
+ if (startFile != null) {
+ builder.startAfter(startFile);
+ }
+ ListObjectsV2Request request = builder.build();
+
+ boolean isTruncated;
+ do {
+ roundCnt++;
+ ListObjectsV2Response response = listObjectsV2(request);
+ for (S3Object obj : response.contents()) {
+ elementCnt++;
+
+ // After reaching the page limit, find the next
matching key across the
+ // remaining page(s) and expanded prefixes so
pagination remains correct.
+ if (reachLimit) {
+ java.nio.file.Path checkPath =
Paths.get(obj.key());
+ if (matcher.matches(checkPath)) {
+ currentMaxFile = obj.key();
+ break listPrefixesLoop;
+ }
continue;
}
- if
(directorySet.contains(objPath.normalize().toString())) {
- break;
- }
- if (isPrefix) {
- directorySet.add(objPath.normalize().toString());
- }
- matchCnt++;
- matchFileSize += obj.size();
- RemoteFile remoteFile = new RemoteFile(
- fileNameOnly ?
objPath.getFileName().toString() :
- "s3://" + bucket + "/" +
objPath.toString(),
- !isPrefix,
- isPrefix ? -1 : obj.size(),
- isPrefix ? -1 : obj.size(),
- isPrefix ? 0 :
obj.lastModified().toEpochMilli()
- );
- result.add(remoteFile);
- lastMatchedKey = obj.key();
+ java.nio.file.Path objPath = Paths.get(obj.key());
+
+ boolean isPrefix = false;
+ while (objPath != null &&
objPath.normalize().toString().startsWith(listPrefix)) {
+ if (!matcher.matches(objPath)) {
+ isPrefix = true;
+ objPath = objPath.getParent();
+ continue;
+ }
+ if
(directorySet.contains(objPath.normalize().toString())) {
+ break;
+ }
+ if (isPrefix) {
+
directorySet.add(objPath.normalize().toString());
+ }
+
+ matchCnt++;
+ matchFileSize += obj.size();
+ RemoteFile remoteFile = new RemoteFile(
+ fileNameOnly ?
objPath.getFileName().toString() :
+ "s3://" + bucket + "/" +
objPath.toString(),
+ !isPrefix,
+ isPrefix ? -1 : obj.size(),
+ isPrefix ? -1 : obj.size(),
+ isPrefix ? 0 :
obj.lastModified().toEpochMilli()
+ );
+ result.add(remoteFile);
+ lastMatchedKey = obj.key();
+
+ if (hasLimits && reachLimit(result.size(),
matchFileSize,
+ fileSizeLimit, fileNumLimit)) {
+ reachLimit = true;
+ break;
+ }
- if (hasLimits && reachLimit(result.size(),
matchFileSize, fileSizeLimit, fileNumLimit)) {
- reachLimit = true;
- break;
+ objPath = objPath.getParent();
+ isPrefix = true;
}
-
- objPath = objPath.getParent();
- isPrefix = true;
}
- }
- // If no next matching file was found after the limit in the
current page,
- // fall back to lastMatchedKey to avoid a non-matching raw S3
key
- // (e.g. a sibling file like .lz4) being recorded as
currentMaxFile.
- if (currentMaxFile.isEmpty()) {
- currentMaxFile = lastMatchedKey;
- }
+ isTruncated = response.isTruncated();
+ if (isTruncated) {
+ request = request.toBuilder()
+
.continuationToken(response.nextContinuationToken())
+ .build();
+ }
+ } while (isTruncated && (!reachLimit ||
currentMaxFile.isEmpty()));
+ }
- isTruncated = response.isTruncated();
- if (isTruncated) {
- request = request.toBuilder()
-
.continuationToken(response.nextContinuationToken())
- .build();
- }
- } while (isTruncated && !reachLimit);
+ if (currentMaxFile.isEmpty()) {
+ currentMaxFile = lastMatchedKey;
+ }
if (LOG.isDebugEnabled()) {
LOG.debug("remotePath:{}, result:{}", remotePath, result);
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/common/util/S3UtilTest.java
b/fe/fe-core/src/test/java/org/apache/doris/common/util/S3UtilTest.java
index 4b976ed86cd..6e61893ed3b 100644
--- a/fe/fe-core/src/test/java/org/apache/doris/common/util/S3UtilTest.java
+++ b/fe/fe-core/src/test/java/org/apache/doris/common/util/S3UtilTest.java
@@ -456,5 +456,34 @@ public class S3UtilTest {
// Malformed bracket (no closing ]) - [ kept as literal
Assert.assertEquals("file[abc.csv",
S3Util.expandBracketPatterns("file[abc.csv"));
}
-}
+ @Test
+ public void testGetGlobListPrefixes_expandsBoundedPatterns() {
+ Assert.assertEquals(Arrays.asList(
+ "data/date=2025-03-01/", "data/date=2025-04-01/",
+ "data/date=2025-10-01/", "data/date=2025-11-01/",
+ "data/date=2025-12-01/"),
+
S3Util.getGlobListPrefixes("data/date=2025-{0[3-4],1[0-2]}-01/*"));
+ }
+
+ @Test
+ public void testGetGlobListPrefixes_fallsBackForWildcardBraceArm() {
+ Assert.assertEquals(Arrays.asList("data/"),
+ S3Util.getGlobListPrefixes("data/{foo*,bar*}/part.parquet"));
+ }
+
+ @Test
+ public void testGetGlobListPrefixes_fallsBackForSurrogateCharacterClass() {
+ String emoji = new String(Character.toChars(0x1F600));
+ Assert.assertEquals(Arrays.asList("data/"),
+ S3Util.getGlobListPrefixes("data/[" + emoji +
"]/part.parquet"));
+ }
+
+ @Test
+ public void testGetGlobListPrefixes_usesUtf8BinaryOrder() {
+ String emoji = new String(Character.toChars(0x1F600));
+ String privateUse = new String(Character.toChars(0xE000));
+ Assert.assertEquals(Arrays.asList("data/" + privateUse + "/", "data/"
+ emoji + "/"),
+ S3Util.getGlobListPrefixes("data/{" + emoji + "," + privateUse
+ "}/*"));
+ }
+}
diff --git
a/fe/fe-core/src/test/java/org/apache/doris/fs/obj/S3ObjStorageTest.java
b/fe/fe-core/src/test/java/org/apache/doris/fs/obj/S3ObjStorageTest.java
index d9ff61500fb..018113841ed 100644
--- a/fe/fe-core/src/test/java/org/apache/doris/fs/obj/S3ObjStorageTest.java
+++ b/fe/fe-core/src/test/java/org/apache/doris/fs/obj/S3ObjStorageTest.java
@@ -22,6 +22,7 @@ import org.apache.doris.common.DdlException;
import org.apache.doris.common.UserException;
import
org.apache.doris.datasource.property.storage.AbstractS3CompatibleProperties;
import org.apache.doris.datasource.property.storage.StorageProperties;
+import org.apache.doris.fs.GlobListResult;
import org.apache.doris.fs.remote.RemoteFile;
import org.apache.commons.lang3.tuple.Triple;
@@ -64,6 +65,7 @@ import java.io.ByteArrayInputStream;
import java.io.InputStream;
import java.time.Instant;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
@@ -600,6 +602,57 @@ public class S3ObjStorageTest {
Assertions.assertThrows(DdlException.class, () ->
storage.getStsToken());
}
+ @Test
+ public void testGlobListPushesDownExpandedPrefixes() {
+ List<String> requestedPrefixes = new ArrayList<>();
+
Mockito.when(mockClient.listObjectsV2(Mockito.any(ListObjectsV2Request.class)))
+ .thenAnswer(invocation -> {
+ ListObjectsV2Request request = invocation.getArgument(0);
+ requestedPrefixes.add(request.prefix());
+ return ListObjectsV2Response.builder()
+ .contents(S3Object.builder()
+ .key(request.prefix() + "part.parquet")
+ .size(1L)
+ .lastModified(Instant.now())
+ .build())
+ .isTruncated(false)
+ .build();
+ });
+
+ List<RemoteFile> result = new ArrayList<>();
+ Status status = storage.globList(
+ "s3://bucket/data/date=2025-0[3-4]-01/*.parquet", result,
false);
+
+ Assertions.assertEquals(Status.OK, status);
+ Assertions.assertEquals(Arrays.asList(
+ "data/date=2025-03-01/", "data/date=2025-04-01/"),
requestedPrefixes);
+ Assertions.assertEquals(2, result.size());
+ }
+
+ @Test
+ public void testGlobListWithLimitFindsNextMatchAcrossExpandedPrefixes() {
+
Mockito.when(mockClient.listObjectsV2(Mockito.any(ListObjectsV2Request.class)))
+ .thenAnswer(invocation -> {
+ ListObjectsV2Request request = invocation.getArgument(0);
+ return ListObjectsV2Response.builder()
+ .contents(S3Object.builder()
+ .key(request.prefix() + "part.parquet")
+ .size(1L)
+ .lastModified(Instant.now())
+ .build())
+ .isTruncated(false)
+ .build();
+ });
+
+ List<RemoteFile> result = new ArrayList<>();
+ GlobListResult globResult = storage.globListWithLimit(
+ "s3://bucket/data/date=2025-0[3-4]-01/*.parquet", result,
null, 0, 1);
+
+ Assertions.assertEquals(Status.OK, globResult.getStatus());
+ Assertions.assertEquals(1, result.size());
+ Assertions.assertEquals("data/date=2025-04-01/part.parquet",
globResult.getMaxFile());
+ }
+
private static class TestableRoleBasedS3ObjStorage extends S3ObjStorage {
private final StsClient stsClient;
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
