Repository files navigation

Recently several works proposed new approaches on how advancements in machine learning can be used to improve indexing strategies on sorted data. This led to theSOSD benchmark, which enabled having a baseline for evaluating different competitors in a standardized way. At the same time, with a wider adoption of network programmability through P4, a trend towards outsourcing computationally intensive procedures to programmable switches started. Our goal is to combine these two advancements and evaluate possibilities of further leveraging the performance of learned indexing algorithms by using the power of network programmability.

After careful evaluation, we come to the decision that we continue our work focusing on the learned indexing algorithmRMI, which suits our idea of implementing parts of it over the network best. Indeed, we find that theP4 specification allows an implementation of the lookup part of RMI on the switch and attains perfect accuracy when tested on simulated network hardware. At this point we analyze how far away our theoretical implementation is, from actually running on real world hardware and find that there is a long way to go. From this result we then generalize our solution to any dataset and arbitrary RMI configuration by adapting the code generation part of theRMI reference implementation to output P4 source code files. We finally conclude our work by coming up with a strategy to, even though having a theoretical implementation, estimate how much our idea of outsourcing RMI calculations to the network could benefit a closed system. We find that we could save around 50-100ns per lookup per last-mile search worker, which would result in a constant speed up that scales horizontally with the amount of last-mile search workers available to a single switch. In comparison to a full RMI calculation and depending on configuration, this would provide a speed up of 10% to 50% per last-mile search worker.

The proposedRMI-P4 implementation can be foundhere.

Additionally theRMI reference implementation can be foundhere.

Finally the originalSOSD benchmark can be foundhere.

• Prof. Dr. Philippe Cudré-Mauroux
• Dr. Alberto Lerner

• Lucas Bürgi