# Taming Deep Recursion

DevFeed: [Taming Deep Recursion](<https://devfeed.tech/articles/taming-deep-recursion-25071.md>)

Original publisher: [Read original article](<https://databasearchitects.blogspot.com/2020/11/taming-deep-recursion.html>)

Author: Thomas Neumann (noreply@blogger.com)

Published: 2020-11-22T16:50:00Z

Content type: tutorial

Language: en

Sources: [Database Architects](<https://devfeed.tech/sources/database-architects.md>)

Topics: [Data structures](<https://devfeed.tech/topics/data-structures.md>), [SQL](<https://devfeed.tech/topics/sql.md>), [Parser](<https://devfeed.tech/topics/parser.md>), [Code](<https://devfeed.tech/topics/code.md>), [Exception](<https://devfeed.tech/topics/exception.md>), [Compiler](<https://devfeed.tech/topics/compiler.md>)

Tags: [code](<https://devfeed.tech/tags/code.md>), [compiler](<https://devfeed.tech/tags/compiler.md>), [crash](<https://devfeed.tech/tags/crash.md>), [data-structures](<https://devfeed.tech/tags/data-structures.md>), [exception](<https://devfeed.tech/tags/exception.md>), [recursion](<https://devfeed.tech/tags/recursion.md>), [snippet](<https://devfeed.tech/tags/snippet.md>), [sql](<https://devfeed.tech/tags/sql.md>)

## AI overview

The article examines stack overflows caused by recursive traversal of very deep SQL expression and algebra trees. It discusses stack-usage checks, explicit-stack iteration, and compiler-supported split stacks as ways to handle unusually deep inputs while preserving simpler recursive code.

## Source excerpt

When operating on hierarchical data structures, it is often convenient to formulate that using pairwise recursive functions. For example, our semantic analysis walks that parse tree recursively and transforms it into an expression tree. This corresponding code looks roughly like this: unique_ptr<Expression> analyzeExpression(AST* astNode) { switch (astNode->getType()) { case AST::BinaryExpression: return analyzeBinaryExpression(astNode->as<BinaryExpAST>()); case AST::CaseExpression: return analyzeCaseExpression(astNode->as<CaseExpAST>()); ... } } unique_ptr<Expression> analyzeBinaryExpression(BinaryExpAST* astNode) { auto left = analyzeExpression(astNode->left); auto right = analyzeExpression(astNode->right); auto type = inferBinaryType(astNode->getOp(), left, right); return make_unique<BinaryExpression>(astNode->getOp(), move(left), move(right), type); } It recursively walks the tree, collects input expressions, infers types, and constructs new expressions. This works beautifully until you encounter a (generated) query with 300,000 expressions, which we did. At that point our program crashed due to stack overflow. Oops. Our first mitigation was using __builtin_frame_address(0) at the beginning of analyzeExpression to detect excessive stack usage, and to throw an exception if that happens. This prevented the crash, but is not very satisfying. First, it means we refuse a perfectly valid SQL query "just" because it uses 300,000 terms in one expression. And second, we cannot be sure that this is enough. There are several places in the code that recursively walk the algebra tree, and it is hard to predict their stack usage. Even worse, the depth of the tree can change due to optimizations. For example, when a query has 100,000 entries in the from clause, the initial tree is extremely wide but flat. Later, after we have stopped checking for stack overflows, the optimizer might transform that into a tree with 100,000 levels, again leading to stack overflow. Basically, all