NDLI: Solving the Join Ordering Problem via Mixed Integer Linear Programming

Please wait, while we are loading the content...

The Next 700 Transaction Processing Engines

ACIDRain: Concurrency-Related Attacks on Database-Backed Web Applications

Azure Data Lake Store: A Hyperscale Distributed File Service for Big Data Analytics

Enabling Signal Processing over Data Streams

Incremental View Maintenance over Array Data

Massively Parallel Processing of Whole Genome Sequence Data: An In-Depth Performance Study

Transaction Repair for Multi-Version Concurrency Control

Wide Table Layout Optimization based on Column Ordering and Duplication

Landmark Indexing for Evaluation of Label-Constrained Reachability Queries

Accelerating Pattern Matching Queries in Hybrid CPU-FPGA Architectures

Heterogeneity-aware Distributed Parameter Servers

Approximate Query Processing: No Silver Bullet

Controlling False Discoveries During Interactive Data Exploration

Beta Probabilistic Databases: A Scalable Approach to Belief Updating and Parameter Learning

Discovering Your Selling Points: Personalized Social Influential Tags Exploration

Interactive Mapping Specification with Exemplar Tuples

Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?

Two-Level Sampling for Join Size Estimation

Determining the Impact Regions of Competing Options in Preference Space

Exploiting Common Patterns for Tree-Structured Data

Schema Independent Relational Learning

An Experimental Study of Bitmap Compression vs. Inverted List Compression

Fast Searchable Encryption With Tunable Locality

Living in Parallel Realities: Co-Existing Schema Versions with a Bidirectional Database Evolution Language

ZipG: A Memory-efficient Graph Store for Interactive Queries

Utility-Aware Ridesharing on Road Networks

Optimizing Iceberg Queries with Complex Joins

Pufferfish Privacy Mechanisms for Correlated Data

Online Deduplication for Databases

Crowdsourced Top-k Queries by Confidence-Aware Pairwise Judgments

Scaling Locally Linear Embedding

Leveraging Re-costing for Online Optimization of Parameterized Queries with Guarantees

Visual Graph Query Construction and Refinement

Crowdsourced Data Management: Overview and Challenges

What Are We Doing With Our Lives?: Nobody Cares About Our Concurrency Control Research

Cicada: Dependably Fast Multi-Core In-Memory Transactions

OctopusFS: A Distributed File System with Tiered Storage Management

Complete Event Trend Detection in High-Rate Event Streams

Incremental Graph Computations: Doable and Undoable

Distributed Provenance Compression

Concerto: A High Concurrency Key-Value Store with Integrity

Query Centric Partitioning and Allocation for Partially Replicated Database Systems

Efficient Ad-Hoc Graph Inference and Matching in Biological Databases

A Memory Bandwidth-Efficient Hybrid Radix Sort on GPUs

Distributed Algorithms on Exact Personalized PageRank

Approximate Query Engines: Commercial Challenges and Research Opportunities

MacroBase: Prioritizing Attention in Fast Data

Database Learning: Toward a Database that Becomes Smarter Every Time

Coarsening Massive Influence Networks for Scalable Diffusion Analysis

Foofah: Transforming Data By Example

Optimization of Disjunctive Predicates for Main Memory Column Stores

A General-Purpose Counting Filter: Making Every Bit Count

Efficient Computation of Regret-ratio Minimizing Set: A Compact Maxima Representative

Extracting and Analyzing Hidden Graphs from Relational Databases

Scalable Kernel Density Classification via Threshold-Based Pruning

Automatic Database Management System Tuning Through Large-scale Machine Learning

Cryptanalysis of Comparable Encryption in SIGMOD'16

Synthesizing Mapping Relationships Using Table Corpus

All-in-One: Graph Processing in RDBMSs Revisited

Distance Oracle on Terrain Surface

The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates

Bolt-on Differential Privacy for Scalable Stochastic Gradient Descent-based Analytics

QFix: Diagnosing Errors through Query Histories

Falcon: Scaling Up Hands-Off Crowdsourced Entity Matching to Build Cloud Services

Dynamic Density Based Clustering

Handling Environments in a Nested Relational Algebra with Combinators and an Implementation in a Verified Query Compiler

Demonstration of the Cosette Automated SQL Prover

Data Management in Machine Learning: Challenges, Techniques, and Systems

BatchDB: Efficient Isolated Execution of Hybrid OLTP+OLAP Workloads for Interactive Applications

Monkey: Optimal Navigable Key-Value Store

LittleTable: A Time-Series Database and Its Uses

DEX: Query Execution in a Delta-based Storage System

ROBUS: Fair Cache Allocation for Data-parallel Workloads

Fast Failure Recovery for Main-Memory DBMSs on Multicores

Spanner: Becoming a SQL System

DAG Reduction: Fast Answering Reachability Queries

FPGA-based Data Partitioning

Parallelizing Sequential Graph Computations

Approximate Query Processing for Interactive Data Science

Data Canopy: Accelerating Exploratory Statistical Analysis

Staging User Feedback toward Rapid Conflict Resolution in Data Fusion

Debunking the Myths of Influence Maximization: An In-Depth Benchmarking Study

QIRANA: A Framework for Scalable Query Pricing

A Top-Down Approach to Achieving Performance Predictability in Database Systems

BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart

FEXIPRO: Fast and Exact Inner Product Retrieval in Recommender Systems

TrillionG: A Trillion-scale Synthetic Graph Generator using a Recursive Vector Model

The BUDS Language for Distributed Bayesian Machine Learning

Solving the Join Ordering Problem via Mixed Integer Linear Programming

BLOCKBENCH: A Framework for Analyzing Private Blockchains

Waldo: An Adaptive Human Interface for Crowd Entity Resolution

Computing A Near-Maximum Independent Set in Linear Time by Reducing-Peeling

Efficient Computation of Top-k Frequent Terms over Spatio-temporal Ranges

Revisiting Reuse in Main Memory Database Systems

Pythia: Data Dependent Differentially Private Algorithm Selection

UGuide: User-Guided Discovery of FD-Detectable Errors

CrowdDQS: Dynamic Question Selection in Crowdsourcing Systems

Extracting Top-K Insights from Multi-dimensional Data

From In-Place Updates to In-Place Appends: Revisiting Out-of-Place Updates on Flash

Interactive Time Series Analytics Powered by ONEX

Data Management Challenges in Production Machine Learning

Bringing Modular Concurrency Control to the Next Level

Flexible and Feasible Support Measures for Mining Frequent Patterns in Large Labeled Graphs

Template Skycube Algorithms for Heterogeneous Parallelism on Multicore and GPU Architectures

Feedback-Aware Social Event-Participant Arrangement

A Cost-based Optimizer for Gradient Descent Optimization

Amazon Aurora: Design Considerations for High Throughput Cloud-Native Relational Databases

Utility Cost of Formal Privacy for Releasing National Employer-Employee Statistics

SLiMFast: Guaranteed Results for Data Fusion and Source Reliability

CDB: Optimizing Queries with Crowd-Based Selections and Joins

QUILTS: Multidimensional Data Partitioning Framework Based on Query-Aware and Skew-Tolerant Space-Filling Curves

The VADA Architecture for Cost-Effective Data Wrangling

Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges

A Demonstration of Lusail: Querying Linked Data at Scale

Graph Querying Meets HCI: State of the Art and Future Directions

Foofah: A Programming-By-Example System for Synthesizing Data Transformation Programs

Graph Exploration: From Users to Large Graphs

Virtualized Network Service Topology Exploration Using Nepal

Building Structured Databases of Factual Knowledge from Massive Text Corpora

VisualCloud Demonstration: A DBMS for Virtual Reality

Data Profiling: A Tutorial

The Best of Both Worlds: Big Data Programming with Both Productivity and Performance

How to Build a Non-Volatile Memory Database Management System

In-Browser Interactive SQL Analytics with Afterburner

Data Structure Engineering For Byte-Addressable Non-Volatile Memory

Debugging Big Data Analytics in Spark with BigDebug

Natural Language Data Management and Interfaces: Recent Development and Open Challenges

Interactive Query Synthesis from Input-Output Examples

Hybrid Transactional/Analytical Processing: A Survey

Generating Concise Entity Matching Rules

Query Processing Techniques for Big Spatial-Keyword Data

A Demo of the Data Civilizer System

Querying and Exploring Polygamous Relationships in Urban Spatio-Temporal Data Sets

Graph Data Mining with Arabesque

Alpine: Efficient In-Situ Data Exploration in the Presence of Updates

OrpheusDB: A Lightweight Approach to Relational Dataset Versioning

doppioDB: A Hardware Accelerated Database

DBridge: Translating Imperative Code to SQL

BEAS: Bounded Evaluation of SQL Queries

Safe Visual Data Exploration

Optimizing Data-Intensive Applications Automatically By Leveraging Parallel Data Processing Frameworks

DIAS: Differentially Private Interactive Algorithm Selection using Pythia

Snorkel: Fast Training Set Generation for Information Extraction

Synthesizing Extraction Rules from User Examples with SEER

Scout: A GPU-Aware System for Interactive Spatio-temporal Data Visualization

Graphflow: An Active Graph Database

Demonstration: MacroBase, A Fast Data Analysis Engine

Q*cert: A Platform for Implementing and Verifying Query Compilers

A Demonstration of Interactive Analysis of Performance Measurements with Viska

Solving the Join Ordering Problem via Mixed Integer Linear Programming

Content Provider	ACM Digital Library
Author	Trummer, Immanuel Koch, Christoph
Abstract	We transform join ordering into a mixed integer linear program (MILP). This allows to address query optimization by mature MILP solver implementations that have evolved over decades and steadily improved their performance. They offer features such as anytime optimization and parallel search that are highly relevant for query optimization. We present a MILP formulation for searching left-deep query plans. We use sets of binary variables to represent join operands and intermediate results, operator implementation choices or the presence of interesting orders. Linear constraints restrict value assignments to the ones representing valid query plans. We approximate the cost of scan and join operations via linear functions, allowing to increase approximation precision up to arbitrary degrees. We integrated a prototypical implementation of our approach into the Postgres optimizer and compare against the original optimizer and several variants. Our experimental results are encouraging: we are able to optimize queries joining 40 tables within less than one minute of optimization time. Such query sizes are far beyond the capabilities of traditional query optimization algorithms with worst case guarantees on plan quality. Furthermore, as we use an existing solver, our optimizer implementation is small and can be integrated with low overhead.
Starting Page	1025
Ending Page	1040
Page Count	16
File Format	PDF
ISBN	9781450341974
DOI	10.1145/3035918.3064039
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-05-09
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Integer linear programming Query optimization
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in