Graph database benchmark: Neo4j vs Kùzu

Intro

0:00 Hello and welcome back to episode three, where we're going to find out how smollerGraph holds up against Neo4j and Kùzu, on a graph of a million relationships. Let's begin with a quick look at where we're going to be by the end of the episode.

0:14 By the end, we're going to have seen smollerGraph load a million relationships about twenty times slower than Kùzu, and walk two hops about eleven times quicker than Neo4j, along with why, for now.

0:27 On the website of the series, you can find more information about the project. The code is open source on GitHub, tagged at each step of each episode, so that you can follow along, and each episode has a page here, with its chapters and its code.

Last time

0:42 Now, before we get to today's work, let's quickly go over what we did last time. We set up a Docker build, with GitHub Actions running it on each push. We wrote a pager, which reads and writes a file in pages of four kilobytes, and files of fixed-size records packed into those pages. The graph moved onto node and relationship records, with each node at the head of a chain of its relationships, and the tests from episode one passed without a change. With sg load and sg walk, a graph we load once can be walked by a later run. And we saw what's slow: each relationship we add reads or writes six pages. Today, we're going to find out what that costs, on a graph a lot bigger than ten animals.

Today

1:25 Today, we're going to measure smollerGraph for the first time. We write a small generator, which makes up a social graph of a hundred thousand people and a million friendships. Then sg learns to time its loads and its walks. A script loads the generated graph into Kùzu and into Neo4j, and asks all three databases one question, for those thousand people. We chart what it measured, and go through why smollerGraph is slow where it's slow, and quick where it's quick. All right, let's get started with the graph.

A million relationships

1:57 For a benchmark, ten animals won't do, and we want a graph we can make again on any machine. So we write a generator, a program of its own in the tools folder, make friends dot c c. It includes charconv, for reading its arguments as numbers, as text that from chars turns into an integer. Its comment, at the top, says what it writes: a made-up social graph, where people each know a number of others, picked at random. It writes them as smollerGraph facts, and as CSV files that Neo4j and Kùzu can import, along with the people to start our queries from. Then it includes cstdint, and filesystem, for making the folder it writes to. Fstream is for writing files, iostream for printing, and random for a random number generator, along with string, string view and system error. In an unnamed namespace, Parse count reads an argument as a whole number with from chars, and checks that the whole argument was read, and that the number is more than zero. Main takes three arguments: how many people, how many friends each, and a folder. Both counts are read with Parse count, and with a wrong number of arguments, or a count it can't read, it prints how to use it and returns one. It creates the folder, with an error code, as the style guide doesn't use exceptions, and says why when it can't. The folder's path is a string, and each file's path is the folder with the file's name on the end. Then it opens four files in the folder, as output file streams, each of which creates its file, or empties one that's already there. Each stream gets a name for what it holds. Friends dot txt holds the facts for smollerGraph, people dot csv a name a line for the other two databases, and knows dot csv a pair of names a line, one for each friendship. Starts dot txt is the people our queries are going to start from. The first loop writes each person's name, from Person one up to the number we asked for. Then comes the random number generator, a Mersenne Twister, which the standard library calls m t one nine nine three seven, given a fixed seed, forty-two. Its comment says why we use its raw numbers: the standard defines them to the bit, so each run, on any machine, writes an identical graph. The distributions that turn them into a range differ between standard libraries, so GCC and Clang would make different graphs with those. For each person, and for each of their friends, we pick someone at random, as the remainder of a random number divided by the number of people, plus one. That's very slightly biased towards smaller numbers, which doesn't matter here. The loop around it picks again when it lands on the person themselves. It's a do while loop, which runs its body once before it checks its condition, as there's no pick to check until we've made one. Its comment says why: nobody is their own friend, so no walk uses one relationship twice, which Neo4j's patterns don't allow. Each friendship goes into the facts file as a pattern, and into knows dot csv as a pair. Then we pick a thousand people at random to start from, and print what we wrote. The number of relationships is worked out as a sixty-four bit number, as a big enough graph would overflow thirty-two bits. In CMake, make friends is an executable of its own, built from that one file, as it doesn't need the database at all. And git ignores bench slash data, where the generated files go, as they're tens of megabytes, and anyone can make them again.

5:24 Let's build it, and ask for a hundred thousand people with ten friends each, into bench slash data. That's a million relationships, written in about a second. The four files are there, and the facts file is the biggest, at around forty megabytes, as each fact spells out both names in full. The first lines show Person one's first friends, as facts for smollerGraph, and as pairs of names for the other two.

Timing it

5:49 Now sg learns to time its own loads and walks. In main dot c c, we include algorithm, for sorting, and chrono, the standard library's header for time, where a duration carries its unit in its type. Then cstddef for sizes, iomanip, for printing numbers with a fixed number of decimals, and vector. Inside the unnamed namespace, a using alias names the clock we're going to read, standard chrono steady clock. A steady clock can't go backwards, unlike the time of day, which the system can change under us, so it's the one to time things with. The usage message gains a third command, bench, for timing walks. Parse hops is new, a function of its own in the namespace. It reads the number of hops, and says what's wrong when it can't. It's the from chars code that walk had, which reads the number and checks that it read the whole argument. It returns true when the number is good, and otherwise prints what's wrong and returns false. Its comment says it has to be a whole number that isn't negative. Walk and bench both need it, so it moved out of Walk into a function of its own. Load now notes the time before loading the facts, and after them works out how long it took, as a duration in seconds. It prints that after the counts, with one decimal, using fixed and set precision. Walk reads its hops with Parse hops, and is otherwise as before. Then comes the new command, bench, which does the timing. Its comment says what it does: it times a walk of a number of hops of one type from each node named in a file. It does that after a first pass that warms the system's caches, and prints how long opening the graph and the walks took, as JSON. Bench takes the graph, the starts file's path, the type, the hops as text, and how long the graph took to open. It reads the hops and opens the file. Then it reads the file a line at a time, a name to a line, and turns each name into a node id with Find, and it stops if a name isn't in the graph. The starts are kept as node ids, so the timed loop doesn't spend any of its time looking names up. The loop over the file's lines declares the name inside the for statement, so the name lasts as long as the loop does. With no names at all, there's nothing to time, so it says so. The total is a size t, the type for counting things in memory. The first loop walks from each start once, without timing, and adds up how many nodes each walk reached. That pass brings the files' pages into the operating system's cache, as it would be for a database that's been running for a while. And its total is the answer we're going to check against the other two databases. The second loop times each walk on its own, from just before the walk to just after it, as a duration in microseconds, and keeps it. Standard sort puts the times in order, from the quickest to the slowest. Sorting a thousand numbers takes no time worth measuring, and it happens after the timed loop anyway. Then we print them as JSON: how long the graph took to open, how many walks, the total, the median, which is the middle of the sorted times, and the ninety-fifth percentile. Ninety-five percent of the walks were quicker than that, so it tells us about the slow ones, which the median hides. In main, bench is a third flag next to load and walk, and anything else still prints the usage. Bench takes four arguments, like walk, and main notes how long opening the graph took, which bench prints. Opening reads each node record for its name, so on a big graph, that's a number worth watching too.

9:29 Let's load the million relationships into a folder, friends dot sg. Sg reads the facts file a line at a time, and each relationship it adds reads or writes six pages, so this takes a while. It takes about thirteen seconds, for a hundred thousand nodes and a million relationships. Then sg bench opens the graph and times the walks from the thousand starts. Opening took about sixty-six milliseconds, most of it spent reading each node record for its name. The median walk took about seventy-three microseconds, and the ninety-fifth percentile about seventy-nine. So a walk of two hops, which reads about a hundred and twenty pages, takes well under a millisecond, as the operating system has the files in its cache.

Neo4j and Kùzu

10:14 Now the comparison, which is in Python, as Kùzu and Neo4j both have Python libraries, and it lives in the bench folder, as compare dot py. Its docstring, at the top, says what it does: it loads the generated graph into smollerGraph, Kùzu and Neo4j, and times a two-hop walk of KNOWS from each person in starts dot txt in each of them. It does that three times over, and writes the medians to results dot json. It also says how to run it, after building: generate the graph, then run it with uv, with the Kùzu and Neo4j libraries, which uv installs on the fly. And it says that Neo4j runs in Docker. We import json, shutil for removing folders, statistics, for medians, subprocess for running sg and Docker, time, and Path for paths. Then Kùzu's library, and the Neo4j driver, which talks to a Neo4j server. Root is the repository's root, two folders up from this file, data is bench slash data, and the Neo4j constant is the image we use, five point two six. The runs constant is three, the number of times each database gets measured. Its comment says why: each database is loaded and timed three times, and the median of each measure is kept, so one unlucky run doesn't decide the result, say if something else on the machine wakes up halfway through. Then the question all three answer, written in Cypher: from a person found by name, along KNOWS to anyone, and along KNOWS again, counting the distinct people at the end. Its comment says what it asks, and that smollerGraph's walk answers it with the size of its list. Timed takes a function that asks for one start, and the list of starts. In Python, a function is a value like any other, so each database can hand timed its own way of asking, as a lambda. Its docstring says what it does: it asks for each start once, to warm the caches, and adds up the answers. Then it asks again, timing each one with perf counter, Python's clock for short times, in microseconds. It sorts the times, and returns the total, the median and the ninety-fifth percentile, like sg bench does. Remove deletes a folder or a file, whichever is there, as Kùzu keeps its database in a single file. SmollerGraph's function removes the graph folder an earlier run left, and uses sg from the build folder, the one we just built. It times sg load, as a process of its own, from start to exit. Then it runs sg bench, with the graph, the starts file, the type and the hops, and captures what sg prints, as text. It reads that as JSON, drops the two fields the other databases don't have, and returns the load time with the walks. Kùzu's function removes its database and its write-ahead log from an earlier run, and opens a database in process, with a connection. The database's path is a string, as that's what Kùzu's library takes. The schema comes first: a node table of people, with the name as its primary key, and a relationship table of KNOWS, from a person to a person. Then we time the two COPY statements, which bring the CSV files into those tables in bulk. The first copies the people from people dot csv, and the second the friendships, from knows dot csv, both of them with no header line. Each COPY is a single statement, and Kùzu works through the file on several cores. We note the time after both of them, and the difference is Kùzu's load time, the bulk load and nothing else. And the walks are timed by running the Cypher query with the person's name as a parameter, and reading the count out of its first row. Neo4j's function needs Docker, as the server runs in a container. A small helper runs a docker command, and stops the script if it fails. It removes any container and volume that an earlier run left behind. The volumes mount our data and the header files into the container, and a named volume holds Neo4j's database between the two containers we're going to run. Then we time neo4j admin's import, Neo4j's bulk loader, which writes a database from CSV files before the server starts. The import gets the two kinds of file with dash dash nodes and dash dash relationships, each with the label or the type its rows get. Each list of files starts with its header file, which names the columns: the person's name as their ID, and the start and end of each relationship. Then we start the server in the background, with authentication off and the Bolt port published, on the volume the import wrote. Inside a try, we connect with the driver, and wait for up to two minutes for Bolt to answer, as the server takes a few seconds to start. In a session, we create an index on the name. Like the comment says, it plays the part Kùzu's primary key plays, so the query finds its start without a scan. We wait for the index to be built, and time the walks, reading the count from the single row each query returns. Finally, whatever happened in the try, the server's container is removed. Main reads the starts, a name a line, and runs the three in turn. The list pairs a short key for the results file, the name to print, and the function to run. For each one, it runs the benchmark three times, and stops if the runs don't agree with each other on the answer. Then it keeps the median of each measure across the three runs, with a dictionary comprehension, a dictionary built from a loop in a single expression. And it prints a line, with an f-string that pads the name to thirteen characters, so the numbers line up in columns. The load time gets two decimals and the walks one, and flush makes Python print each line as soon as it's ready, as the run takes minutes. Each line has the load time, the median, the ninety-fifth percentile, and how many people the walks reached. The two times in microseconds get eight places and one decimal, as the slowest of them run to tens of thousands. Then it checks that all three answers are equal, and stops if they aren't, as timing three different questions would tell us nothing. Last, it writes the results as JSON, indented by two spaces, so the file reads a field to a line, and a change shows up clearly in a diff. The last two lines run main when the file is run as a script. The two header files for Neo4j are a line each. People dot csv says its column is the person's ID, and knows dot csv says its two columns are where each relationship starts and where it ends. The README gets a section on running the benchmark, and git ignores the results, along with Python's cache folder.

16:44 Let's run it, with uv and the two libraries. SmollerGraph goes first, with its slow load, and then Kùzu and Neo4j load the graph and answer their a thousand queries, twice each, and all three do that three times over. Neo4j's part starts a container for the import and another for the server each time, so the whole run takes several minutes, and the recording skips ahead. At the end, the three lines agree on how many people the walks reached, so all three answered one question, and the charts are going to show the rest.

The numbers

17:16 Loading first, where smollerGraph was meant to lose. Kùzu copies a million relationships into its tables in about six hundred and thirty milliseconds. Neo4j's bulk importer takes about eight seconds, and as far as I can tell, most of that is starting Java and the container, as a tiny graph takes nearly as long. SmollerGraph takes about thirteen seconds, which is about twenty times as long as Kùzu, and about one point six times as long as Neo4j.

17:45 The walk goes the other way round, though. SmollerGraph's median two-hop walk takes about seventy microseconds. Neo4j's takes about seven hundred and fifty microseconds, about eleven times as long, and Kùzu's about fifteen hundred. Kùzu's slowest walks are slower still, with its ninety-fifth percentile at about seventeen hundred microseconds, while smollerGraph's is about seventy-three.

Why, for now

18:11 So why is smollerGraph slow at one and quick at the other? When it loads, it reads a line, adds a relationship, and reads or writes six pages through a system call each, one relationship at a time, on one core. That's about six million system calls for a million relationships. Kùzu and Neo4j load the graph in bulk instead. They read the CSV files on several cores, sort what they read, and write their files in large sequential pieces, not a page at a time. When it walks, smollerGraph is a function call inside our own program, written for one question, walking two hops of one type. Kùzu and Neo4j are answering a Cypher query, which they parse, plan and run, through their Python libraries, and in Neo4j's case over Bolt, to a server in a container. So the walk isn't a fair fight yet, as smollerGraph has no query language to pay for, and no transactions to keep. And all three were measured warm, with their files in the operating system's cache, which is what makes our page reads cheap. These numbers are where we start from, and the plan is to measure again as the buffer pool, the index and the Cypher subset come in.

Wrap-up

19:21 So, today we wrote a generator for a social graph of a million relationships, which writes an identical graph on any machine. Sg learned to time its loads, and to time its walks with sg bench. And a script asked smollerGraph, Kùzu and Neo4j one question, for a thousand people, and checked that all three answered it alike. SmollerGraph was about twenty times slower than Kùzu to load, and about eleven times quicker than Neo4j to walk, for reasons that have more to do with what it doesn't do yet than with anything clever. And from here on, each change comes with these charts, before and after.

20:00 This is going to be an evolving project, so I'd love to hear from you. Let me know in the comments what you'd like smollerGraph measured against next, and if you'd like to follow along, subscribe to the channel. I hope you find this useful, and thanks for watching.