[Bug] FileIndexPredicate getRequiredNames() redundant child.visit() causing Exponential algorithmic complexity

[fafacao86]

Search before asking

• I searched in the issues and found nothing similar.

Paimon version

Paimon built from source, master branch, commit e1cbeed 2025/12/31.

Compute Engine

Flink 1.20

Minimal reproduce step

Flink-SQL batch mode + Paimon.
Create a Primary key tableA and enable any file index, I was using BitmapFileIndex, on a column col1, then select filter with a large IN clause,which translates to a tree of OR expression by calcite.
select * from table tableA where col1 IN (1, 2, 3, ... 100)
Then the query takes a lot of time but not producing any result,CPU is running 100%.
Use jstack to get the stacktrace:

	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:131)
	at org.apache.paimon.fileindex.FileIndexPredicate$1.visit(FileIndexPredicate.java:120)
	at org.apache.paimon.predicate.CompoundPredicate.visit(CompoundPredicate.java:69)
	at org.apache.paimon.fileindex.FileIndexPredicate.getRequiredNames(FileIndexPredicate.java:119)
	at org.apache.paimon.fileindex.FileIndexPredicate.evaluate(FileIndexPredicate.java:80)
	at org.apache.paimon.io.FileIndexEvaluator.evaluate(FileIndexEvaluator.java:74)
	at org.apache.paimon.operation.RawFileSplitRead.createFileReader(RawFileSplitRead.java:249)
	at org.apache.paimon.operation.RawFileSplitRead.lambda$createFileReader$3(RawFileSplitRead.java:234)
	at org.apache.paimon.operation.RawFileSplitRead$$Lambda$1900/0x000073f47b848ba8.get(Unknown Source)
	at org.apache.paimon.mergetree.compact.ConcatRecordReader.readBatch(ConcatRecordReader.java:73)
	at org.apache.paimon.flink.source.FileStoreSourceSplitReader.fetch(FileStoreSourceSplitReader.java:122)
	at org.apache.flink.connector.base.source.reader.fetcher.FetchTask.run(FetchTask.java:58)
	at org.apache.flink.connector.base.source.reader.fetcher.SplitFetcher.runOnce(SplitFetcher.java:165)
	at org.apache.flink.connector.base.source.reader.fetcher.SplitFetcher.run(SplitFetcher.java:117)
	at java.util.concurrent.Executors$RunnableAdapter.call(java.base@17.0.18/Executors.java:539)
	at java.util.concurrent.FutureTask.run(java.base@17.0.18/FutureTask.java:264)
	at java.util.concurrent.ThreadPoolExecutor.runWorker(java.base@17.0.18/ThreadPoolExecutor.java:1136)
	at java.util.concurrent.ThreadPoolExecutor$Worker.run(java.base@17.0.18/ThreadPoolExecutor.java:635)
	at java.lang.Thread.run(java.base@17.0.18/Thread.java:840)

What doesn't meet your expectations?

Query should return result in a relatively short time.

Anything else?

Looked at the code, the first child.visit() might be redundant? And it doubles the execution path visitng each node.

private Set<String> getRequiredNames(Predicate filePredicate) {
        return filePredicate.visit(
                new PredicateVisitor<Set<String>>() {

                    @Override
                    public Set<String> visit(LeafPredicate predicate) {
                        return Collections.singleton(predicate.fieldName());
                    }

                    @Override
                    public Set<String> visit(CompoundPredicate predicate) {
                        Set<String> result = new HashSet<>();
                        for (Predicate child : predicate.children()) {
                            // This might be redundant? And it doubles the execution path visitng each node.
                            child.visit(this);
                            result.addAll(child.visit(this));
                        }
                        return result;
                    }
}

I removed the child.visit() and recompile, the query returned result very quickly.

Are you willing to submit a PR?

• I'm willing to submit a PR!

[fafacao86]

Not sure if the first child.visit() has some side-effect, and is neccessary. If this is indeed a bug, and I can submit a PR regarding this.