From static pruning to dynamic pruning: Accelerating graph databases through a new approach that skips reading unnecessary segments

Two researchers involved in database research since their student days

Nishikawa: During my university years, I studied object-oriented databases—databases that manage data and processing in an integrated manner. During my laboratory studies, I also worked on hypertext research. After completing my master’s program, I searched for a position at a company where I could continue database research. At that time, though, there were very few companies in Japan offering that type of environment. During my search, I learned that Hitachi offered the opportunity to work on databases in its R&D division, so I decided to reach out to Hitachi about a potential career. Although commercial relational databases (RDBs)*2 were already widespread at the time, they were primarily used in large enterprises and core business systems. RDBs that anyone could easily use did not yet exist.

*2 A system that manages data in table format, structuring information through relationships between rows and columns. Using programming languages such as SQL (Structured Query Language), data can be handled, extracted, and retrieved by linking multiple tables. Due to its high consistency and reliability, it is used in core banking systems, enterprise applications, and other systems.

After joining Hitachi, I worked on a range of database-related projects. For the first three years or so, I was involved in developing object-oriented database products; after that, I spent some time researching networking technologies. I was then seconded to a Hitachi Group company in the United States. After returning to Japan, I worked in a business division, where I helped develop a relational database management system (RDBMS). Around 2003, I began collaborating with the University of Tokyo, participating in a government-led R&D project. Through this connection, I also enrolled in a doctoral program at the University of Tokyo and obtained my PhD through research on databases and storage systems. I later had another opportunity to work in the United States on big data R&D at a Group company, after which I returned to the joint government-led R&D project with the University of Tokyo—a project that formed a foundation for the development of the dynamic pruning technology we are discussing today.

Takao: At graduate school, I studied in the informatics course my university had just set up. Although I was in a database research laboratory, I focused on natural language processing throughout my master’s program. I eventually set my sights on a research career and, at the recommendation of my professor, shifted my specialization to databases when I enrolled in the doctoral program. When I began looking at employment opportunities after completing my PhD, I focused my search on database research positions. I noticed that Hitachi was a sponsor of an academic conference that I had attended around that time, which sparked my interest in the company. To me, a role at Hitachi seemed like an opportunity to pursue further database research, and I decided to apply.

Since joining Hitachi, I have worked on database research as a member of Nishikawa’s team. The team had already started research on dynamic pruning when I joined, so my first job was to support evaluation experiments and survey relevant literature. I am currently researching ways to make dynamic pruning easier to use in practical applications.

Slow response to recursive queries in graph databases posed a challenge

Nishikawa: The catalyst for developing dynamic pruning technology goes back to when we were exploring ways to use databases in industrial applications. Graph-structured data consists of nodes and edges, forming connections and networks of complex interconnections. Databases that manage data with those structures are known as graph databases, which were already in use in industrial analytics. However, they had a critical weakness: The retrieval speed would slow down as data volume increased or hierarchical depth grew. To expand the use of graph databases, then, we needed to find a way to overcome this retrieval lag, and decided to focus our research on this challenge.

As our research progressed, we focused our attention on recursive queries, which use the result of one query as the input for the next, repeatedly making queries while traversing relationships. For example, one practical application for graph databases in the manufacturing industry is parts traceability. To trace which parts are used in what order for a specific product, you need to trace the path from the product back to the parts in the reverse order they were assembled during manufacturing. This is where recursive queries come in. As products consist of numerous parts, you can imagine that traversing the graph structure using recursive queries takes quite a bit of time.

During the pre-shipment inspection process for a product, for instance, it may be necessary to verify how parts or subparts were used. However, long retrieval times have often made it impossible to inspect all products, forcing the use of sampling inspections instead. If retrieval response time in graph databases could be reduced to a point where full inspection of all products would be feasible, there would be tangible effects: helping prevent defective products from being shipped, for example. Therefore, there was a need for technology that made it possible to inspect all products in a short time period—to make recursive queries in graph databases viable, in other words.

A paradigm shift in approach: Skip reading unnecessary data

Takao: Let’s consider recursive queries in graph databases using an example in a traceability application where we want to search for all the parts of a product. To do this, we search for the parts that make up final product A.

We start by searching for parts B and C that make up final product A. Then we search for the parts of B, which are D and E, and further find G and H, the subparts of D. Meanwhile, for C, we find part F. When executing recursive queries in each of these processes, the search tends to explore the entire graph database, including unnecessary segments. Even when you search specifically for B or G or H, the system traverses almost all the segments of the sprawling database every time, meaning the search takes time to finish.

A conventional solution was a method known as “static pruning.” This approach involves preparing summary information in advance during query compilation (the process of analyzing source code and converting it into a program that the computer can execute) and narrowing the segments to search using filter-based precomputation. For example, when searching for the parts of a certain product, the system informs the upstream step that the search should be limited to a specific range of values, thereby narrowing the scope of the query. Optimizing the query process in this way reduces retrieval time. However, static pruning also has limitations. Although it is effective during the early stages of queries, the amount of data that must be read grows as the recursion depth increases, leading to longer processing times.

In response to this challenge, Hitachi and the University of Tokyo developed dynamic pruning, a method that allows for the dynamic optimization of queries. Rather than relying on pre-optimized filters, this method narrows the database segments to search during query execution itself. The key is that this adjustment happens during query execution. The concept behind the approach is to dynamically calculate the segments of the database that need to be searched next at each step of a recursive query and to perform pruning—in other words, to skip reading unnecessary data—and thereby speed up the process.

Going back to our example situation, that means that retrieving the parts of A only involves searching the Step 1 and Step 2 segments. The same goes for retrieving the parts of B: the search scope is only the Step 3 segments connected to B. As the number of steps in the recursive query increases, the search scope is dramatically reduced. We believed this approach could significantly reduce retrieval time.

Nishikawa: We conducted proof-of-concept testing for our dynamic pruning technology using Hitachi Advanced Database (HADB),*3 an enterprise-class commercial database designed for high-reliability big-data analytics in data centers and large enterprises.

While executing recursive queries required at least 80 seconds of response time without dynamic pruning, applying dynamic pruning reduced response time to just 2.7 seconds—a retrieval speed approximately 30 times faster. The results of tracing input and output data volumes also showed that the system processed about 95 gigabytes (GB) of data without pruning but just 1.83 GB with dynamic pruning.

*3 Hitachi Advanced Database (formerly Hitachi Advanced Data Binder) utilizes the results of research entitled “Development of the Fastest Database Engine for the Era of Very Large Database and Experiment and Evaluation of Strategic Social Services Enabled by the Database Engine” (principal investigator: Professor Masaru Kitsuregawa, president of the Research Organization of Information and Systems and professor at the University of Tokyo), which was supported by the Japanese Cabinet Office’s Funding Program for World-Leading Innovative R&D on Science and Technology (FIRST Program).

As the graph shows, a 12-level recursive query that previously took at least 80 seconds to complete can be completed by dynamic pruning in 3 seconds or less by narrowing the segments to search. Although performance varies by database type, we have found that this approach can speed up retrieval time by up to 135 times. We have also obtained a patent for this technology.

Pursuing new technologies to further enhance dynamic pruning

Nishikawa: We worked on this project with researchers from the University of Tokyo’s Institute of Industrial Science, holding regular in-person meetings and online discussions as needed. They provided the basic conceptual framework, we also proposed Hitachi’s ideas, and we discussed them together. Over the roughly one year it took for our paper to be accepted, we received valuable input, such as advice on how to address peer-review feedback and guidance on how to present the results of our experiment in an effective manner. We also received a wide range of advice from the University of Tokyo faculty regarding the final wording of the paper.

Despite these achievements, dynamic pruning technology still has limitations. For example, its effectiveness varies depending on the database structure. Although it works effectively in the manufacturing-industry example, it may not function as well in cases where parameters are defined as ranges and segmenting the data into small and well-defined clusters with similar characteristics is a challenge. In these types of cases, we would need to work with the business divisions to restructure the database design so that dynamic pruning could deliver more effective results across a broad range.

Takao: On that point, I am currently working to develop preprocessing technology that can make dynamic pruning more powerful by enabling use in a wider range of applications. Specifically, I am developing methods for improving segmentation in cases involving multidimensional data. Advances in this area would make dynamic pruning even more effective.

Nishikawa: If we can apply the technology Takao is working on, we would be able to effectively apply dynamic pruning across an even broader scope. New technologies like this will eventually find their way into products and services in line with customer demands, as is the case with HADB, and business divisions will ultimately decide on how to incorporate them. From that standpoint, it would be fair to say that our close collaboration with the business divisions is particularly important.

Expanding the technology’s application through a government-led R&D project

Nishikawa: Our dynamic pruning technology is already in operation in HADB, a commercial database. Ready for immediate use upon installation, the technology is already proving effective for customers in the manufacturing field—and its range is also expanding into the healthcare field. Promising areas for future application include the electricity sector, especially power transmission, and artificial intelligence (AI), where the technology has strong potential to deliver significant value.

In addition to our joint development with the University of Tokyo, we are developing this technology further as part of Phase 3 of the Cross-ministerial Strategic Innovation Promotion Program (SIP), a Cabinet Office-led national project. The Integrated Healthcare System initiative under this program comprises 15 projects, and we are working on the one called “Development of Infrastructure for High-Speed Processing, Efficient Management, and Advanced Analysis of Large-Scale Medical Data,” led by Professor Kazuo Goda of the Institute of Industrial Science, the University of Tokyo. Aiming to eventually build medical digital twins, we are studying the application of dynamic pruning technology as a high-speed analysis technique.

Takao: I have personally shifted my main research focus away from dynamic pruning at this point. With the expansion of generative AI, the use of unstructured data is obviously growing. The problem, however, is that unstructured data is difficult to handle within RDBs. That is why I am working to develop technology that can convert unstructured data into high-dimensional vectors so that they can be managed and handled within an RDB framework. I presented this vector database research at an academic conference in the spring of 2026.

What Hitachi means to researchers

Takao: Being part of Hitachi’s Research & Development Group has given me the opportunity to work with highly skilled senior researchers like Nishikawa and technological experts from the company’s business divisions. I have also learned a lot from the colleagues I have worked with through our partnerships with academic institutions. There is a lot to learn every day, but the work is very rewarding. The Research & Development Group is a large organization, and there are many researchers who joined in the same year as me and who I continue to keep in touch with. I also enjoy catching up with my colleagues outside work—we always have a lot of fun no matter whether we are discussing research or our personal interests!

Nishikawa: I am grateful for the diverse experiences I have had since joining Hitachi. The opportunities I have had to research overseas were particularly valuable, as was working closely with business divisions. Although I am a researcher, I have also had the opportunity to present our technologies at trade shows. Being able to not only develop technology but also dialogue with customers and get a real sense of how our research is contributing to society is extremely rewarding.

(Photo by Kiyono Hattori)