NoSQL Optimizer

This nosql optimizer will find the best physical table structure(s) to minimize the global cost of a given workload.

How to use

See todo.graphql for an example workload.

Selectivity needs to be manually specified for each eligible permutation. Each selectivity set needs to know:

• distinct number of elements that would be returned if used
• prob or worst case probability that the scalar would be found if scanning the set
• hotspot if the set is not evenly distributed

To run: Install or-tools to maven, the integer optimizer (the one included is built for Mac)

mvn install:install-file -Dfile=lib/com.google.ortools.jar -DgroupId=com.google.or-tools -DartifactId=or-tools -Dversion=7.8 -Dpackaging=jar

Then run:

MAVEN_OPTS="-Xss2048k -Djava.library.path=lib" mvn exec:java -Dexec.mainClass="Main" -Dexec.args="src/main/resources/todo.graphql"

How it works

By providing a logical data model and a workload with constraints on latency and throughput, it will permute the best possible physical structures and then use integer optimization to find the global minimum cost.

This is accomplished by clever use of the ID field & immutable non-null relationships. IDs cannot be specified in this system, it must be generated by the database. The ID component is comprised of:

• A time-uuid component to assure uniqueness & allow ordering by date
• Immutable fields, including fields that span relationships
• A cryptographic signature

This allows fields to be automatically and safely denormalized between tables.

Development

This project uses lombok to generate boilerplate for java classes. The intellij plugin is handy.

This project is very much happy-path development.

Inspiration

@article{mior2017nose,
  title={NoSE: Schema design for NoSQL applications},
  author={Mior, Michael Joseph and Salem, Kenneth and Aboulnaga, Ashraf and Liu, Rui},
  journal={IEEE Transactions on Knowledge and Data Engineering},
  volume={29},
  number={10},
  pages={2275--2289},
  year={2017},
  publisher={IEEE}
}

@article{yan2019generating,
  title={Generating application-specific data layouts for in-memory databases},
  author={Yan, Cong and Cheung, Alvin},
  journal={Proceedings of the VLDB Endowment},
  volume={12},
  number={11},
  pages={1513--1525},
  year={2019},
  publisher={VLDB Endowment}
}