  Recursive queries and recursive derived tables constitute an important part
of the SQL standard. Their efficient processing is important for many real-life
applications that rely on graph or hierarchy traversal. Position-enabled
column-stores offer a novel opportunity to improve run times for this type of
queries. Such systems allow the engine to explicitly use data positions (row
ids) inside its core and thus, enable novel efficient implementations of query
plan operators.
  In this paper, we present an approach that significantly speeds up recursive
query processing inside RDBMSes. Its core idea is to employ a particular aspect
of column-store technology (late materialization) which enables the query
engine to manipulate data positions during query execution. Based on it, we
propose two sets of Volcano-style operators intended to process different query
cases.
  In order validate our ideas, we have implemented the proposed approach in
PosDB, an RDBMS column-store with SQL support. We experimentally demonstrate
the viability of our approach by providing a comparison with PostgreSQL.
Experiments show that for breadth-first search: 1) our position-based approach
yields up to 6x better results than PostgreSQL, 2) our tuple-based one results
in only 3x improvement when using a special rewriting technique, but it can
work in a larger number of cases, and 3) both approaches can't be emulated in
row-stores efficiently.
