Improve performance by reducing string copies

[alamb]

@Omega359 mentioned in discord a blog post by the Databend folks about how they wrote a replacement of sqlparser-rs for their system

https://www.databend.com/blog/category-engineering/2025-09-10-query-parser/

One thing they cite is the fact that sqlparser-rs often copies strings, even when this could be avoided

If anyone cares, we can probably avoid copying strings, someone just has to care enough to thread the lifetime information through all the tokens (or maybe use an Arc w/ an offset)

@AdamGS mentioned he might be interested in trying this

This could possibly be related to another ticket here:

• Improve performance by not copying Tokens as much #1558

[alamb]

FYI for your amusement @iffyio and @yoavcloud

[AdamGS]

I'm going to give it a try, mostly to satisfy my own curiosity. My intuition is more the Arc path because lifetimes are painful, but its too early to tell if I'm on the right path there, I might try both.

If it works, it might be a significant breaking change externally, but I guess we'll worry about that if we get there.

[eyalsatori]

Some thoughts on this topic:

I've been thinking about the Arc suggestion from the previous discussion, and I see some potential issues:
The tokenizer currently holds only a reference to the original query. If we use Arc, the library would need to create an owned copy of the query, which seems to miss the point of zero-copy tokenization. Additionally, since each copy would need to handle a different slice of the string, we'd need to implement something similar to the Bytes library.
Alternative approach using lifetimes

Another option is to introduce lifetimes directly into the Token enum:

pub enum Token<'a> {
    /// An end-of-file marker, not a real token
    EOF,
    /// A keyword (like SELECT) or an optionally quoted SQL identifier
    Word(Word<'a>),
    /// An unsigned numeric literal
    Number(&'a str, bool),
    // ...
}

And the tokenize method would become:
pub fn tokenize(&'a mut self) -> Result<Vec<Token<'a>>, TokenizerError>

However, this would bind the Token lifetimes to the original string. While this is the goal of this task, it could cause problems for current users who might not account for this and could be using the tokens after the original string is freed. Such a change could be quite disruptive for existing code.

I'd like to suggest a different approach that I think could work better:

1. Rename the current Token enum to BorrowedToken<'a> and recursively replace all String elements with Cow<'a, str>:

pub enum BorrowedToken<'a> {
    /// An end-of-file marker, not a real token
    EOF,
    /// A keyword (like SELECT) or an optionally quoted SQL identifier
    Word(Word<'a>),
    /// An unsigned numeric literal
    Number(Cow<'a, str>, bool),
    // ...
}

2. Define a type alias:
   type Token = BorrowedToken<'static>;

3. Create a new borrow_tokenize method that contains all the tokenization logic without copying strings:
   pub fn borrow_tokenize(&'a mut self) -> Result<Vec<BorrowedToken<'a>>, TokenizerError>

4. Keep the existing tokenize method signature but change its implementation:

pub fn tokenize(&'a mut self) -> Result<Vec<Token>, TokenizerError> {
    let borrow_tokens = self.borrow_tokenize()?;
    let owned_tokens: Vec<BorrowedToken<'static>> = 
        // some code that calls to_owned() on all Cow variables inside the enum
    Ok(owned_tokens)
}

5. Update the parser to work with BorrowedToken

Benefits of this approach:
This way, I think we can achieve our zero-copy goal without introducing a massive breaking change to the API. Existing users would continue to work as before, while new users could opt into the borrowed version for better performance.

I'm happy to work on a prototype if this direction looks promising. What are your thoughts?

[alamb]

Thank you @eyalsatori -- this sounds like a great incremental way to move this project along

So with this strategy, as I understand it, any existing users of Token (aka who need owned tokens) would get BorrowedToken<'static> which should be almost as easy to work with.

Internally the parser would be able to simply use the Borrowed token that refers to the original input string 👍

If this works out well we can maybe even use the same process in the AST nodes.

FYI @iffyio and @yoavcloud

I would be happy to help test the approach downstream in DataFusion

[eyalleshem]

I started working on this (you can see the first step in #2073), and one of the issues I encountered is that in some places in the Tokenizer, we're modifying the raw string (I can see this happening in the escaping function, and possibly in other places as well).
Since this PR already suggests using Cow, my suggestion is that when we try to Tokenize such elements, we should also use the Cow strategy. When a string is manipulated, we would create a new string and use Cow::Owned, and when it's not manipulated, we would use theCow::Borrowed version. (I'm making an assumption here that in most cases we don't manipulate the string - for example, in the escaping case, I assume that most strings will not be escaped by the Tokenizer.)