Teaching Python to skip a hundred thousand tuples, in C

Squeezing performance out of a hotspot: database diffing

I recently released DumpTales , which compares two database snapshots offline.

But before it can compare anything, it has to read. And conventional mysqldump output is not kind to readers: one INSERT statement typically carries hundreds or thousands of rows, and a single statement can legally be 128 MiB of comma-separated tuples:

INSERT INTO `accounts` VALUES (1,'Acme','basic'),(2,'Harbour','basic'),(3,'Old Co','trial');

Splitting that into rows and values sounds trivial, until you remember that ,, ), ' and " are all perfectly legal inside a quoted value. You need a little state machine that tracks whether you are inside quotes, handles backslash escapes and doubled quotes, counts nested parentheses, and slices out values only at top-level commas. Do it wrong, and a value containing the string `'),(`` will quietly corrupt the comparison.

Dumptales is, like most of my tools, a Python app, and so I first wrote that state machine in Python, as two functions called parens and split_top.

Then I profiled, and almost all of the MySQL parsing time was sitting in those two loops. Not because the algorithm was clever or expensive - but because it is a per-character loop, and a per-character loop in an interpreter pays rent on every character.

In the end, with that same algorithm converted into a CPython extension module, the results were pretty dramatic. Nothing cleverer, just the same logic compiled to machine code.

If you're like me, you very rarely delve into C these days, but it can be kind of interesting.

And it's only 82 lines! Let's go through it.

Chunk 1: who's calling, and where are we?

#define PY_SSIZE_T_CLEAN
#include <Python.h>

static PyObject *next_row(PyObject *self, PyObject *args) {
    PyObject *sql;
    Py_ssize_t at;
    if (!PyArg_ParseTuple(args, "On", &sql, &at)) return NULL;
    if (!PyUnicode_Check(sql)) {
        PyErr_SetString(PyExc_TypeError, "SQL statement must be Unicode");
        return NULL;
    }
    if (PyUnicode_READY(sql) < 0) return NULL;
    Py_ssize_t length = PyUnicode_GET_LENGTH(sql);
    int kind = PyUnicode_KIND(sql);
    void *data = PyUnicode_DATA(sql);
    if (at < 0 || at >= length || PyUnicode_READ(kind, data, at) != '(') {
        PyErr_SetString(PyExc_ValueError, "expected opening parenthesis");
        return NULL;
    }

The first two lines are housekeeping: Python.h is just the header that lets a C function participate in Python's world of objects and reference counting.

next_row is the one function Python will call. It receives its arguments as a tuple, and PyArg_ParseTuple(args, "On", &sql, &at) unpacks them: O means "a Python object" (the SQL statement string) and n means "a Python integer, stored as a native Py_ssize_t" (the position to start at). If the caller passes nonsense, we return NULL - in the CPython C API, returning NULL from a function is how you say "an exception has been raised".

Two sanity checks follow: the object really is a string, and PyUnicode_READY normalises the string's internal storage so we can read it safely.

The KIND/DATA/READ trio is the interesting bit. Python does not always store strings the same way internally: a string of plain ASCII may use one byte per character, while a string with an emoji in it uses four. Rather than caring, we ask the string for its kind (1, 2 or 4 bytes) and a pointer to its data buffer, and PyUnicode_READ(kind, data, i) fetches character i correctly for whichever shape it is. This is a direct array lookup into memory the string already owns - we never copy the statement.

Finally, we check the caller has actually aimed us at an opening parenthesis.

Chunk 2: four bits of state

    PyObject *values = PyList_New(0);
    if (!values) return NULL;
    Py_ssize_t start = at + 1;
    Py_UCS4 quote = 0;
    int depth = 1;
    for (Py_ssize_t i = start; i < length; i++) {
        Py_UCS4 ch = PyUnicode_READ(kind, data, i);

The whole scanner needs surprisingly little state:

• values - an empty Python list to collect the row's values into;
• start - where the value we are currently inside begins (just after the opening ();
• quote - which quote character opened the current quoted string, or 0 for "not inside a string";
• depth - how many nested parentheses we are inside. It starts at 1, because we are already inside the tuple's own (.

Then the loop: walk every character from start to the end of the statement. Everything below happens inside this loop.

Chunk 3: inside quotes

        if (quote) {
            if (ch == '\\') {
                if (i + 1 < length) i++;
                continue;
            }
            if (ch == quote) {
                if (i + 1 < length && PyUnicode_READ(kind, data, i + 1) == quote) {
                    i++;
                    continue;
                }
                quote = 0;
            }
            continue;
        }

If we are inside a quoted string, the only characters that matter are:

• a backslash, which escapes the next character - so \' inside a single-quoted value does not end the string. We skip the next character by bumping the loop counter manually;
• a quote character matching the one that opened the string. If it is immediately followed by another identical quote, that is the SQL doubling convention ('' meaning one literal quote), so we skip both. Otherwise the string has ended, and quote goes back to 0.

Everything else inside a string is ignored. That is the entire escaping story: get this right and a value like `'),(`` is just data.

Chunk 4: structure, boundaries, and finding a way out

        if (ch == '\'' || ch == '"' || ch == '`') {
            quote = ch;
        } else if (ch == '(') {
            depth++;
        } else if (ch == ')') {
            depth--;
            if (depth == 0) {
                Py_ssize_t left = start, right = i;
                while (left < right && Py_UNICODE_ISSPACE(PyUnicode_READ(kind, data, left))) left++;
                while (right > left && Py_UNICODE_ISSPACE(PyUnicode_READ(kind, data, right - 1))) right--;
                PyObject *token = PyUnicode_Substring(sql, left, right);
                if (!token || PyList_Append(values, token) < 0) { Py_XDECREF(token); Py_DECREF(values); return NULL; }
                Py_DECREF(token);
                PyObject *result = PyTuple_New(2);
                if (!result) { Py_DECREF(values); return NULL; }
                PyObject *position = PyLong_FromSsize_t(i + 1);
                if (!position) { Py_DECREF(result); Py_DECREF(values); return NULL; }
                PyTuple_SET_ITEM(result, 0, values);
                PyTuple_SET_ITEM(result, 1, position);
                return result;
            }
        } else if (ch == ',' && depth == 1) {
            Py_ssize_t left = start, right = i;
            while (left < right && Py_UNICODE_ISSPACE(PyUnicode_READ(kind, data, left))) left++;
            while (right > left && Py_UNICODE_ISSPACE(PyUnicode_READ(kind, data, right - 1))) right--;
            PyObject *token = PyUnicode_Substring(sql, left, right);
            if (!token || PyList_Append(values, token) < 0) { Py_XDECREF(token); Py_DECREF(values); return NULL; }
            Py_DECREF(token);
            start = i + 1;
        }
    }
    Py_DECREF(values);
    PyErr_SetString(PyExc_ValueError, "unbalanced parentheses");
    return NULL;
}

Outside quotes, only four characters matter:

• ', " or ` open a quoted string, and we remember which one;
• ( deepens the nesting (values can contain parenthesised expressions);
• ) closes one level. If that brings depth back to 0, the tuple is finished: we trim surrounding whitespace off the final value, cut it out of the statement with PyUnicode_Substring, append it to the list, and return a two-item tuple of (list_of_values, position_just_after_the_closing_paren). That position is how the caller finds the next row without being handed (or copying) the rest of the statement;
• , at depth == 1 - a comma inside this tuple but not inside a nested one - is a value boundary. Same ritual: trim, slice, append, and remember that the next value starts after the comma.

The Py_DECREF calls sprinkled through the error paths are reference-counting bookkeeping - the C-side equivalent of Python's garbage collector, telling CPython "I am done with this object", so nothing leaks.

If the loop reaches the end of the statement without ever closing the tuple, we tidy up, raise a Python ValueError("unbalanced parentheses") and return NULL. DumpTales' Python caller catches that ValueError and re-raises it as its own DumpError.

Chunk 5: the glue that makes it importable

static PyMethodDef methods[] = {
    {"next_row", next_row, METH_VARARGS, "Parse the next SQL VALUES tuple without copying the remaining statement."},
    {NULL, NULL, 0, NULL}
};
static struct PyModuleDef module = {PyModuleDef_HEAD_INIT, "_dumptales_native", NULL, -1, methods};
PyMODINIT_FUNC PyInit__dumptales_native(void) { return PyModule_Create(&module); }

The last five lines are pure ceremony, but they are what make the whole thing work: a table registering next_row under its Python name, a module definition calling the module _dumptales_native, and the initialisation function CPython runs when you import _dumptales_native. After that, from Python's point of view, it is an ordinary module.

Why the C wins

The Python functions parens and split_top in dumptales.py implement exactly this state machine (I've kept them there in case, for whatever reason, the user doesn't or can't use the C parser).

But three things make the C version faster:

1. No interpreter tax. In the Python loop, each character costs bytecode dispatch, object handling and reference counting before the actual comparison happens. The compiled loop is a handful of machine instructions per character.
2. No intermediate copies. The Python path slices the entire tuple text out of the statement first (raw, pos = parens(s, pos)), then slices that again per value with split_top. The C version reads characters in place and creates exactly one new string per value - the minimum work needed to return Python objects at all.
3. No copying of the remaining statement. The function hands back an integer offset and the caller resumes there. The Python approach re-slices the still-unparsed tail of a statement that can be megabytes long, once per row.

Let's do some measurements!

Consider this code (you'll need to have a copy of the dumptales codebase handy and relative to the script):

import sys, time
sys.path.insert(0, '/path/to/dumptales/source')
from dumptales import parens, split_top
import _dumptales_native as native

row = "(1,'Acme & Co',45.5,'2026-09-30',`some_long_text`,NULL,'plain')"
s = "INSERT INTO `t` VALUES " + ",".join([row] * 50000)
start = s.index('(')

def python_loop():
    pos = start
    n = 0
    while pos < len(s):
        raw, pos = parens(s, pos)
        n += len(split_top(raw))
        while pos < len(s) and s[pos].isspace():
            pos += 1
        if pos == len(s):
            break
        pos += 1
        while pos < len(s) and s[pos].isspace():
            pos += 1
    return n

def native_loop():
    pos = start
    n = 0
    while pos < len(s):
        raw_values, pos = native.next_row(s, pos)
        n += len(raw_values)
        while pos < len(s) and s[pos].isspace():
            pos += 1
        if pos == len(s):
            break
        pos += 1
        while pos < len(s) and s[pos].isspace():
            pos += 1
    return n

assert python_loop() == native_loop()

for name, fn in (('python', python_loop), ('native', native_loop)):
    t = time.perf_counter()
    fn()
    print(f'{name}: {time.perf_counter() - t:.3f}s')

One INSERT statement, 50,000 rows, both parsers walking it to completion:

About eighteen times faster, consistently across runs. Multiply by a dump with hundreds of statements, and the saving is far from subtle!

In fact, real database dumps would likely stress-test the Python interpreter version even more, because wider rows, with more real string content, would increase the tax on the interpreter.

For example, if we test with wider rows:

import sys, time
sys.path.insert(0, '/path/to/dumptales/source')
from dumptales import parens, split_top
import _dumptales_native as native

def make(nrows, ncols, textlen):
    vals = ','.join(["'x%d_%s'" % (j, 'y'*(textlen//6)) if j % 3 == 1 else str(j) for j in range(ncols)])
    row = '(' + vals + ')'
    return "INSERT INTO `t` VALUES " + ','.join([row]*nrows)

def loop(s, start, native_mode):
    pos = start; n = 0
    while pos < len(s):
        if native_mode:                                                                                                                                                                            raw_values, pos = native.next_row(s, pos); n += len(raw_values)
        else:
            raw, pos = parens(s, pos); n += len(split_top(raw))
        while pos < len(s) and s[pos].isspace(): pos += 1
            if pos == len(s): break
            pos += 1
            while pos < len(s) and s[pos].isspace(): pos += 1
    return n

for label, ncols, textlen in (('narrow (7 cols, ~30 ch)', 7, 30), ('wide (20 cols, ~240 ch)', 20, 240)):
    s = make(50000, ncols, textlen)
    start = s.index('(')
    assert loop(s, start, False) == loop(s, start, True)
    out = []
    for mode in (False, True):
        t = time.perf_counter(); loop(s, start, mode)
        out.append(time.perf_counter() - t)
    print(f'{label}: statement {len(s)/1e6:.1f} MB | python {out[0]:.2f}s | native {out[1]:.3f}s | ratio {out[0]/out[1]:.0f}x')

python3 /tmp/bench_wide.py && python3 /tmp/bench_wide.py

narrow (7 cols, ~30 ch): statement 1.7 MB | python 0.38s | native 0.028s | ratio 14x
wide (20 cols, ~240 ch): statement 18.0 MB | python 3.83s | native 0.177s | ratio 22x
narrow (7 cols, ~30 ch): statement 1.7 MB | python 0.62s | native 0.038s | ratio 16x
wide (20 cols, ~240 ch): statement 18.0 MB | python 4.47s | native 0.059s | ratio 75x

So there you go. I'm pretty happy with the performance - still maybe could be better. Maybe Python and C is the wrong solution here - will I end up using Rust for the first time? We'll see :)