Skip to main content

4 posts tagged with "incremental computation"

View All Tags

Mihai Budiu

Introduction

In previous blog posts we have described at a high level how the Feldera incremental query engine works. An incremental query engine continuously evaluates a set of queries (in our system these queries are described as database views). The queries depend on some data sources that continuously change.

The Feldera query engine (named DBSP) receives as inputs the changes applied to the data sources, and produces as outputs the changes of the results of the queries. The query engine uses the same data structure to represent all changes; this representation is used for inputs, outputs, and the internal data structures. This representation is the Z-set, and its close relative, the Indexed Z-set.

Analyst

Introduction

In today’s Apparel and Footwear markets, customers desire personalized experiences, trends shift overnight, and supply chains need constant optimization. In addition, traditional analytics infrastructure can no longer provide the necessary decision support as it did in the past. Integration of near real-time data synchronization, correct and timely analysis, and reduced inventory costs have become indispensable. Efficient data-driven decisions require efficient processing of data.

Mihai Budiu

Introduction

In previous blog posts we have:

In this blog post we explain how an incremental query engine like Feldera actually operates as seen by a user. We start by motivating the need for incremental computation in databases. Future blog posts will describe the internal operations in detail.

Mihai Budiu

Incremental computation is a computation that reuses results that were previously computed.

Let us assume you have a program PP that is given an input II and produces an output OO:

eyJ2ZXJzaW9uIjoiMSIsImVuY29kaW5nIjoiYnN0cmluZyIsImNvbXByZXNzZWQiOnRydWUsImVuY29kZWQiOiJ4nOVYW1PbOlx1MDAxMH7nV2TSV3B1l8xbuU1zKFBcdTAwMDZOL+dMh1x1MDAxMbGSmDh2jq2QhFx1MDAwZf+9klx0llx1MDAxZCchXHUwMDFkmp7M1Fx1MDAwZmCvVtrV7n7St/m+02g09XSomvuNppq0ZVx1MDAxNFx1MDAwNqlcdTAwMWM3d638XqVZmMRmXGLl31kyStu5Zk/rYbb/9q2b4bWTwdMsXHUwMDE1qYGKdWb0/jXfjcb3/G/JTqraWsbdSOVcdTAwMTPyoZIpIeal50mcm4XcR1xiXGJcImChXHUwMDExZkfGnlaBXHUwMDE57sgoU27Eipo302v05cGPT9FlXHUwMDAw5GRcdTAwMDInZ6jlzHbCKLrS0+hpU7LdXHUwMDFipSWnMp0mffU5XGZ0z1qfk1x1MDAxN/OyxITAzUqTUbdcdTAwMTerLKvMSYayXHUwMDFk6qmVXHUwMDAxUEiforDfcJKJ+aJcdTAwMTh5XHUwMDAwXHRMIcbYp8QvRvP5kHp0zpfDJEpS68tcdTAwMWJcIkin03He3Mp2v2tcXIqDQkenMs6GMjVJcnrj2S65c7mnwm5PW3+ce5nKQ1xyXHUwMDE5JIxcdTAwMTPkPLM2hq0gz/o3XHUwMDE331RcdTAwMGVUy86IR1FUXHUwMDBlUVx1MDAxY8xC9FxcXHUwMDFkrj7wTPLoNmH1j+frqlxcW5X60mridlYqXHUwMDA2eH4pw+N/bo4wXHUwMDE4XHUwMDA3f08uM3BcdTAwMDajZqH3uLt42afJ/Vx1MDAxM3Xz34fzm4dPw+nghpx+2ju/PapaebYv0zRcdTAwMTmvu27rWutcdTAwMDP61+nX4OEs+/qBf7lcdTAwMWVEn9dbd/bmwj1cdTAwMWFcdTAwMDZSz1x1MDAxMuQj4XNCmc9wMVx1MDAxZYVxfz5cdTAwMTdR0u47+OyUXHUwMDFjruG2XHUwMDEy1zJkXHReXHUwMDA2WVxmmUCM8fVcdTAwMTG7OEnbjlhcdTAwMDY8XHUwMDFmmr1cdTAwMTJKXHUwMDAwxJBXXHUwMDExi8TG8FxusYewfajgjDCzXFxcdTAwMWS/iNbwKyhmgjLMX1x1MDAwZuDKQFxyqb+yOJ1XSayvwlx1MDAwN5tcdTAwMDdcdTAwMDQq0lx1MDAxMzlcYqNpJY951ZowfmxWRO+isGuLt9k2rqq0Utc6NNdaoTBcYoOgfFe1jVx1MDAxZFx1MDAxOcYqba1zxSRp2FxyY1x1MDAxOV3X3TA7Vu+fk1x1MDAwNL1Smm5lpuxonqqVmHw6XHUwMDEzXHUwMDE2gFx1MDAxMlx1MDAwMlx1MDAwNubFxUUqKFx1MDAxNIJB6KL/XHUwMDEyLFdcdTAwMWZ/W1xuS1x1MDAwNnzP91x1MDAwNeRcZlxiXHUwMDBlXGZ7qMKSXHUwMDAwj/rmKuOC+ZzTzYGUUI+Ygjf8hXJIuHBhLzBcbjxcdTAwMGUgXHUwMDE0XHUwMDA2XHUwMDE3XHUwMDAy2Lu1xIJcbsxcdTAwMTKBKOBiI5cuevnS3VxilDMtU31cdTAwMTDGQVx1MDAxOHerjs145Dogy8HfXHUwMDFlZXlcdTAwMWOBXHJcdTAwMTOFXGJRXHUwMDBlkFx1MDAwZimnJbWuXHUwMDFjWq9rm1Vx8LJcdTAwMTN3e5HsXHUwMDFm0LvTh1x1MDAwMMG7s+NTtHcgXHUwMDE3ObFcdTAwMDc8xCm1hUd8wqiB2lx1MDAwMiewXHUwMDA3Slx1MDAwZkK85lUkM32YXGZcdTAwMDahNtH+mISxno9qXHUwMDFlvnf2XGboKVlLudlVecxcdTAwMTRpOMe7h3bRKqVyb1xyXHUwMDA3p/yjeP+2u1B7aZnns2tcdTAwMDXultsp//959sGWnnOImLhcdTAwMWGX3Mn60jm3Osfbes4x5JkjXHUwMDFkXHUwMDEyjFx1MDAwNPIpc9vdOP0gXHUwMDFlzelcdTAwMDc36Vx1MDAxNlx1MDAxMFx1MDAxM2dqXHUwMDA1/bDdXHUwMDAzJpxunH1siNBvgHi/jttcXCzhNpHq6Fx1MDAxNcxGJ8NltKbi6jyHufi1XHUwMDFjZlx1MDAxObIx9+elXHUwMDA1sjHC1PBd4UroJWSP30dcdTAwMTTh9JK2PpzA8fHh/UXn+GrbkU1cZrJNXHUwMDBmZVx1MDAxZoCBKLH7jSNcdTAwMWJ4wrdcdTAwMGazzVx1MDAwMkB8XHUwMDAxaakj22RcdTAwMDRzSnyn/D8ge7ta6tchu/V7kd36Xd1cdCRLf+YjVFx1MDAxMMPJf+I3g9VcdN9WaHPfQ0Ig7HNTVajUXHUwMDE05POxaV2Q4a+cYJ9xVkL+dnYnXFxAxrEh3n9gd7L6aql0J1x1MDAxMHBOXHUwMDA0XHUwMDAzXHUwMDA0mX6UIVfkRV/ge7b8melhOFx1MDAwMIYksdre12pW1u6YTLNcdTAwMDJMkSGCXHUwMDE5IZBQiF2tXHUwMDE1TmHPkDvEXHUwMDA19Vx1MDAwMcBcdTAwMWNcdTAwMTjdmld/ZrOyMzPQlMPhlTZ1V6SkeVx1MDAxZqrxQVx1MDAxZItvOvljL508ePZ4UnnZP+48/lx1MDAwMDn7PfwifQ==POI

Now let's change the input by modifying it with some change, which we denote by ΔI\Delta I:

eyJ2ZXJzaW9uIjoiMSIsImVuY29kaW5nIjoiYnN0cmluZyIsImNvbXByZXNzZWQiOnRydWUsImVuY29kZWQiOiJ4nO1b23LayFx1MDAxNn33V1DM44k1fb/kXHI7doJjXHUwMDFiZ4jt2KemUjJcYlDAXHUwMDEykYRtnMpfzHedbzpbwkY3XHUwMDEw8lx1MDAwNIhSM3owILW6t7r3Wnuv3vK3nVqtXHUwMDFlTMdW/XWtbj10zJHd9cz7+qvw/J3l+bbrwCVcdTAwMTL99t2J14laXHUwMDBlgmDsv/799/hcdTAwMGWj497O7rJG1q3lXHUwMDA0PrT7L/yu1b5Ff1x1MDAxM+N4Vicwnf7Iim6ILsVDMYyyZ09dJ1x1MDAxYVx1MDAxNisqKSdI8HlcdTAwMGLbf1x1MDAwM+NcdTAwMDVWXHUwMDE3LvfMkW/FV8JT9a9N5+ikf+te0eCPO6/hnF1cXJw042F79mjUXHUwMDBlpqPZQ5mdwcRLXHUwMDE45Vx1MDAwN547tC7tbjBcYkfPnJ/f57swXHUwMDA18V2eO+lcdTAwMGZcdTAwMWPL91P3uGOzY1x1MDAwN9PwXHUwMDFjilx1MDAxZnA2XHUwMDBir2vxmVx1MDAwN/jFXHUwMDE5MrCEQ3OEJcNyfjW8n1ximbFk31x1MDAxZLleaMlvTLFer1x1MDAxN9tyY3aGfTDI6c7bXHUwMDA0nun4Y9ODJYrb3T89o4xcclx1MDAxZVh2f1x1MDAxMITWxMb5VjTRmirOeLxcYuFcYuNmN17x6Oz4vqdN670tjs98NVx1MDAxZD1OxXC0X3+6/me8XHUwMDA0nnlrNcNunclolJxFp/s0i9/iTp9cXIg+nflcdTAwMWU/adj+IOt6SfdLuWBgPcSPn/BcdTAwMTd+cTlcdTAwMTnactjbu7ratXpnb6RNP9Tn7b6/Wtzt7OZhXHUwMDAzff5MPj9+dK56zZPLSbN1JNvpUZ7HNz3PvS/bL328bFxyTlx1MDAwMnZcdTAwMWM0jr5Mzib7XWXvlus3N92TcdecwVx1MDAwNVx1MDAwYk2UloxcdTAwMGIt6Pz6yHaG2bVcdTAwMTi5nWGMsJ2EwTlop+Y1gWqawGxcdTAwMGXVmlGOVMKIVahevEpVR7XQXHUwMDA2XHUwMDEyXHUwMDE4Y1wikdRY8TSqpTb4xnCNqUFoeHAlXHUwMDA1XHUwMDEz0F1cdTAwMWXnhGdxziTRTEmOt4b01IVcdTAwMWOk1+nFsVWuXHUwMDEztO3HcL1cYkqdPTRv7dE0td6Re8Nkn9VTp1x1MDAxYSO7XHUwMDFmenm9XHUwMDAzplpeXG5cdTAwMDCBXHIhct7g1u52k3GvXHUwMDAz45i2Y3nNMuHK9ey+7Zijj3kz4Imtd89LiY3EYt6Yvlx1MDAxNV6NoFZcYt5cdTAwMTl5LEAv5owsgy9BmmhCVfmYXFxMk1x1MDAxNUWvwMrATFxuxFxiZ0qIuJdcYr2aXHUwMDE4SGOBpVx1MDAxMlpKrjaGZMZcclx1MDAwNv6OITeQYI+KfX5cdTAwMGVkZEiEsVx1MDAwMlgohJmQKmHNXGbYXG5jrihcIvHN21x1MDAwZuFkdVxi31xi3v3A9II92+naTj9t2FPiWlx1MDAwNolcdTAwMTFDdCahlbvIQIQgqoDWMVwiSCGg90S7vjlcdTAwMGXdx9BCK8Ikp5gwQEvu6S2nu9qqvd7uuz3C2tMvrHPTXG6a6Ms0sJdZXHUwMDA1ljBcYjeSYKZcdTAwMTGiNGeUNKighIXoXHUwMDA1pqc6b9TI9IN99/bWXHUwMDBlYPbPXFzbXHSys1x1MDAxY01nIySOgWXmXFxcdTAwMDBcdTAwMWUqeVxyXFzbziT+47DTtNvF32oxXGKjXHUwMDFm8+9/vlrYeik4ortzsIi720l+vjy30cvIUSvwUoFZ+dSmeIWrSo5cdTAwMTJcdTAwMWJcYqFw0jk4Xexq20htmMGj1EbCeitMWcx2XHUwMDA1qVxyRDSqXHUwMDE4VrIquU1R/r8pXXH+0HHaty0qrlx1MDAwZdX1gVx1MDAxZYuvaPjpp+mKXHUwMDFmy8haSzKykdVcdTAwMGJcbvKxwFx1MDAxZC9LxlKmZjOv1nozr2XUXHUwMDAy+r8g74KDXGJcdTAwMTa3WMUtrc6YvbXPXHUwMDA3p+JDiyD/3cVcdTAwMDVcIq2qc1x1MDAwYpPIYEIgzaREIEa2yi3IUOEsa8j+OORLckG2tYBbiMZcZjGNf1x1MDAwNW6p1t7Cj3FAc7tcdTAwMWPQ3Jb6XHUwMDEydPmWaJjjUYlcdTAwMTN7gqtYoHjFq8pcdTAwMDJKXHUwMDFhjEohpFx1MDAxNpxgjkVGf2GDXHUwMDEx+Fx1MDAwYsmHXHUwMDE2UiT2NyopwLBgXGaIjeGfuYlacVx1MDAwNVZcdTAwMWOtMlqHa1hcdTAwMTJcdTAwMDBcdTAwMDJTmGBFRaLZs1x1MDAwMENcdTAwMTJzSTmIc6S5XHUwMDEwuYcvJcBeJFx1MDAwYilcdTAwMTJcdTAwMWPWXHUwMDFmU1x1MDAwMipcdTAwMGKcYYFcdTAwMDAjXHUwMDFjUVxyRmkqlaQqZ9S/XHUwMDAyLMGQxXUjxLJnn0lSXHUwMDExXGLhkEC8YIuqNb2enlx1MDAxZrpvXHUwMDBl+kP7+LThnN/z86pzJKe6oGxEhchYsu2yXHUwMDExlkhSXHUwMDE0XHUwMDFhuIL0gv5Ra3xldq/Pr9yjt839T87wzq165ejsvnt47bZcdTAwMWWaZsBuxnvDXHUwMDBm0zeN47JKzFXi61x1MDAwM1x1MDAxZU4/dy7v5Z1/cGK/v79bg8JcdTAwMGKGXHUwMDAzc+S1UVf7/vuGstrDybhkv1x1MDAxYsjuXG7BvXR3hS/dXcGIQjqgXHUwMDExKp/8LF6lqlx1MDAwM1uogspcdTAwMTFEjspVjrBimFxiTNQqXHS0Pqj/00tHK0LWTytcdTAwMWSxRNzJxuVQ1XOGYoCvgm8xT1ZcdTAwMTS+XHUwMDAyy4LSXHUwMDEx1cjQXGYrREG1YM0293JHKeXCOcWcstmhXHUwMDEz209PyFx1MDAxNpBAQy96VelokzG84sKlXHUwMDE4ibWC0lx1MDAxMVx1MDAwMSmwQLmspXR0efdcdTAwMWU93PVcdTAwMWKm5U3ltb8rWjf7u8usSpSOlOaK5Iz6p5WOsrCIu9tJfr44uZFL93eBV5ikXHUwMDAy6/K1o+Ilrio7SlRQO9psciPj0FSQzIRvOICnw7pXJJkpyvh/QEmUyPgl59us6dT+U/vfX9uu7GRcdTAwMDfdaH1HLVx1MDAxNTfAulx1MDAwNCNOyidHPYdcdTAwMWVcdTAwMWO0b4dvP55J9cfhebfXI49Vhz+EmYLyzmbhXHUwMDBmskqCsiFahi+6aVx1MDAxMr/jVCRtXHUwMDE4XHUwMDA0aVwisfhcdTAwMTXYoFr6/8fYoFx1MDAxOVx1MDAwMXPbNZ7soJtcdTAwMTVLXHUwMDFhLX3PXHUwMDBla0xcdTAwMTmRgpav91x1MDAxNq9+VVx0QVx0XHUwMDAz8mGtXHUwMDE1xuBe8XbDs1iSmIbbXHUwMDBigNuEcNyAVlx1MDAxMlx1MDAxMOqUVIhIolx1MDAxMjSd0kpIUCE4VkBcdJCb57RSqOqoXHUwMDE029tcdTAwMDT55bRSccyq5Ys8QNSQhGBcdTAwMDJyXHQnmi0q8jBOWO7pS2mlXHUwMDE3KbhUlUervFXpKo/iOGfUr6eVXHUwMDE2gyO6O1x1MDAwN4u4u53kZ5ZcdTAwMWTLvJO0jEIjIaGQXHUwMDAxwVkxRDRiSmXKXHUwMDFmWFx1MDAxYjjMYKlgQnEhWVx1MDAwZfOgXHUwMDAwRZiDSMI5oTpB7XPMM2pgXHUwMDAyUlx1MDAwMDBNIGvBiZJSns2ynNRDqoPQyznpZ/N0krTWzkbPWVx1MDAxNeVMXHUwMDBiomhOXHUwMDBmz1h/aVRUkmmJeKk3LLPMlzJ8jWJnrWBb6pXhXHUwMDExOjVl4SvHwC+UXG5CV3WXXHUwMDFhPO/Oeay+lKTW+Fx1MDAxMjNQXHSjRCrgeymQTOyczrlcdTAwMTUzQyRRTVfU9ddBqlx1MDAwNeyFTlx1MDAxYf7p9Lht+Z/en04+XFy1L6dM5dkrLVx1MDAwN0PyklxihVlcdTAwMGaCZ5VcdTAwMWOiXFyau1xiMVx1MDAxNCNYK1x0l1C8aTFnLmLAvXBIXHUwMDExbsaxXHUwMDA1zEX+ZaqyXG7reduHgFx1MDAxYU29NZD4f1i6vKghaViB12V0+8tcdIn/LUJ6llCeNfFcdTAwMTNcdTAwMGLyYlx1MDAxOVa+WJXSWyll9HdUWMbunFx1MDAwNpshcueJrermeNxcdTAwMGVg7uZcdTAwMWNUv7Ot+728XHUwMDEz/9aLjlx1MDAxMNFcdTAwMTGeQ1x1MDAwN7aiyPV95/v/XHUwMDAxN9fpOiJ9POIPO + ΔOI + ΔIreuse

We would like to avoid computing the entire output again, and ideally reuse the previously computed OO and only adjust it by a change ΔO\Delta O. This would be great especially if the output doesn't change much.