Thesis name: Scuba diving equipment, systems of equipment organization and their comparison Thesis aim: To draw out historical information, to describe diving equipment and its function. To process individual systems of diving equipment's orders and to describe pro-and- cons of each of those systems. Method: Studying of accessible sources. Content analysis of technical literature and other sources. Retrieval of equipment's technical parametres. Analysis and processing of information. Results: The outcome is evaluation of different systems of diving equipment's orders. Comparison and recommendation of suitability for different kinds of scuba diving with equipment. Keywords: Diving equipment, systems of diving equipment's orders, buoyancy compensator, configuration, scuba diving with equipment

Data-centers increasingly deploy commodity servers with high-speed network interfaces to enable low-latency communication. However, achieving low latency at high data rates crucially depends on how the incoming traffic interacts with the system's caches. When packets that need to be processed in the same way are consecutive, i.e., exhibit high temporal and spatial locality, CPU caches deliver great benefits. This licentiate thesis systematically studies the impact of temporal and spatial traffic locality on the performance of commodity servers equipped with high-speed network interfaces. The results are that (i) the performance of a variety of widely deployed applications degrade substantially with even the slightest lack of traffic locality, and (ii) a traffic trace from our organization's link to/from its upstream provider reveals poor traffic locality as networking protocols, drivers, and the underlying switching/routing fabric spread packets out in time (reducing locality).  To address these issues, we built Reframer, a software solution that deliberately delays packets and reorders them to increase traffic locality. Despite introducing µs-scale delays of some packets, Reframer increases the throughput of a network service chain by up to 84% and reduces the flow completion time of a web server by 11% while improving its throughput by 20%. / Datacenter distribuerar alltmer rå varuservrar med höghastighets-nätverksgränssnitt för att möjliggöra kommunikation med låg latens. Att uppnå låg latens vid höga datahastigheter beror dock mycket på hur den inkommande trafiken interagerar med systemets cacheminnen. När paket som behöver bearbetas på samma sätt är konsekutiva, dvs. uppvisar hög tids- och rumslig lokalitet, ger cacher stora fördelar. I denna licentiatuppsats studerar vi systematiskt effekterna av tidsmässig och rumslig trafikplats på  prestanda för rå varuservrar utrustade med höghastighetsnätgränssnitt.Vå ra resultat visar att (i) prestandan för en mängd allmänt distribuerade applikationer försämras avsevärt med till och med den minsta bristen på trafikplats, och (ii) visar ett trafikspår från vår organisation dålig trafikplats som nätverksprotokoll, drivrutiner och den underliggande omkopplingen/dirigera tygspridningspaket i tid (minska lokaliteten). För att ta itu med dessa problem byggde vi Reframer, en mjukvarulösning som medvetet fördröjer paket och ordnar dem för att öka trafikplatsen. Trots införandet av µs-skalafördröjningar för vissa paket visar vi att Reframer ökar genomströmningen för en nätverkstjänstkedja med upp till 84% och minskar flödet för en webbserver med 11% samtidigt som dess genomströmning förbättras med 20%. / <p>QC 20210512</p> / ULTRA

An ordering on bases in Banach spaces is defined as a natural generalization of the notion of equivalence. Its theory is developed with emphasis on its behavior with respect to shrinking and boundedly-complete bases. We prove that a bounded operator mapping a shrinking basis to a boundedly-complete one is weakly compact. A well-known result concerning the factorization of a weakly compact operator through a reflexive space is then reinterpreted in terms of the ordering. Next, we introduce a class of Banach spaces whose norm is constructed from a given two-dimensional norm N. We prove that any such space XN is isomorphic to an Orlicz sequence space. A key step in obtaining this correspondence is to describe the unit circle in the norm N with a convex function ϕ. The canonical unit vectors form a basis of a subspace YN of XN . We characterize the equivalence of these bases and the situation when the basis is boundedly-complete. The criteria are formulated in terms of the norm N and the function ϕ. 1

The subject of the present study is an analysis of five ditransitive verbs: give, lend, send, offer and show. The study focuses on the position of the two objects and on the factors that have an impact on the object ordering. An attempt is here made to provide a systematic overview of the position of the two objects with respect to their realization (i.e. substantival or pronominal). As regards the realization of the two objects, four types are distinguished: i. both Oi /Oprep and Od realized by nouns; ii. both Oi /Oprep and Od realized by pronouns; iii. Oi /Oprep realized by a noun and Od by a pronoun; iv. Oi /Oprep realized by a pronoun and Od by a noun. The position of the objects is assumed to be associated with the distribution of communicative dynamism or in other words with the principle of end-focus, i.e. that given information tends to precede new information. The second principle that operates in the ordering the two objects is the principle of end-weight. Of the three (or four, including intonation) factors whose interplay determines the FSP function of a clause element, in the case of ditransitive complementation the most important role is played by the contextual factor. Therefore, particular attention is paid to the context-dependence / independence of the two objects. The present...

Querying and efficiently analyzing complex data is required to gain valuable business insights, to support machine learning applications, and to make up-to-date information available. Therefore, this thesis investigates opportunities and challenges of selecting the most efficient execution strategy for analytical queries. These challenges include hard-to-capture data characteristics such as skew and correlation, the support of arbitrary data types, and the optimization time overhead of complex queries. Existing approaches often rely on optimistic assumptions about the data distribution, which can result in significant response time delays when these assumptions are not met. On the contrary, we focus on robust query optimization, emphasizing consistent query performance and applicability. Our presentation follows the general select-project-join query pattern, representing the fundamental stages of analytical query processing. To support arbitrary data types and complex filter expressions in the select stage, a novel sampling-based selectivity estimator is developed. Our approach exploits information from filter subexpressions and estimates correlations that are not captured by existing sampling-based methods. We demonstrate improved estimation accuracy and query execution time. Further, to minimize the runtime overhead of sampling, we propose new techniques that exploit access patterns and auxiliary database objects such as indices. For the join stage, we introduce a robust optimization approach by developing an upper-bound join enumeration strategy that connects accurate filter selectivity estimates –e.g., using our sampling-based approach– to join ordering. We demonstrate that join orders based on our upper-bound join ordering strategy achieve more consistent performance and faster workload execution on state-of-the-art database systems. However, besides identifying good logical join orders, it is crucial to determine appropriate physical join operators before query plan execution. To understand the importance of fine-grained physical operator selections, we exhaustively execute fixed join orders with all possible operator combinations. This analysis reveals that none of the investigated query optimizers fully reaches the potential of optimal operator decisions. Based on these insights and to achieve fine-grained operator selections for the previously determined join orders, the thesis presents a lightweight learning-based physical execution plan refinement component called. We show that this refinement component consistently outperforms existing approaches for physical operator selection while enabling a novel two-stage optimizer design. We conclude the thesis by providing a framework for the two-stage optimizer design that allows users to modify, replicate, and further analyze the concepts discussed throughout this thesis.:1 INTRODUCTION 1.1 Analytical Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.2 Select-Project-Join Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Basics of SPJ Query Optimization . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.1 Plan Enumeration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.2 Cost Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.3 Cardinality Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.4 Robust SPJ Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4.1 Tail Latency Root Cause Analysis . . . . . . . . . . . . . . . . . . . 17 1.4.2 Tenets of Robust Query Optimization . . . . . . . . . . . . . . . . . 19 1.5 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.6 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 SELECT (-PROJECT) STAGE 2.1 Sampling for Selectivity Estimation . . . . . . . . . . . . . . . . . . . . . . 24 2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.1 Combined Selectivity Estimation (CSE) . . . . . . . . . . . . . . . . 29 2.2.2 Kernel Density Estimator . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.3 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3 Beta Estimator for 0-Tuple-Situations . . . . . . . . . . . . . . . . . . . . . 33 2.3.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.2 Beta Distribution in Non-0-TS . . . . . . . . . . . . . . . . . . . . . . 35 2.3.3 Parameter Estimation in 0-TS . . . . . . . . . . . . . . . . . . . . . . 37 2.3.4 Selectivity Estimation and Predicate Ordering . . . . . . . . . . . 39 2.3.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4 Customized Sampling Techniques . . . . . . . . . . . . . . . . . . . . . . 53 2.4.1 Focused Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.4.2 Conditional Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.4.3 Zone Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3 JOIN STAGE: LOGICAL ENUMERATION 3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.1.1 Point Estimates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.1.2 Join Cardinality Upper Bound . . . . . . . . . . . . . . . . . . . . . 64 3.2 Upper Bound Join Enumeration with Synopsis (UES) . . . . . . . . . . . . 66 3.2.1 U-Block: Simple Upper Bound for Joins . . . . . . . . . . . . . . . . 67 3.2.2 E-Block: Customized Enumeration Scheme . . . . . . . . . . . . . 68 3.2.3 UES Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.3.1 General Performance . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.3.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4 JOIN STAGE: PHYSICAL OPERATOR SELECTION 4.1 Operator Selection vs Join Ordering . . . . . . . . . . . . . . . . . . . . . 77 4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2.1 Adaptive Query Processing . . . . . . . . . . . . . . . . . . . . . . 80 4.2.2 Bandit Optimizer (Bao) . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.3 TONIC: Learned Physical Join Operator Selection . . . . . . . . . . . . . 82 4.3.1 Query Execution Plan Synopsis (QEP-S) . . . . . . . . . . . . . . . 83 4.3.2 QEP-S Life-Cycle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3.3 QEP-S Design Considerations . . . . . . . . . . . . . . . . . . . . . . 87 4.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.4.1 Performance Factors . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.4.2 Rate of Improvement . . . . . . . . . . . . . . . . . . . . . . . . . . 92 4.4.3 Data Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.4.4 TONIC - Runtime Traits . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5 TWO-STAGE OPTIMIZER FRAMEWORK 5.1 Upper-Bound-Driven Join Ordering Component . . . . . . . . . . . . . 101 5.2 Physical Operator Selection Component . . . . . . . . . . . . . . . . . . 103 5.3 Example Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . 103 6 CONCLUSION 107 BIBLIOGRAPHY 109 LIST OF FIGURES 117 LIST OF TABLES 121 A APPENDIX A.1 Basics of Query Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 A.2 Why Q? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 A.3 0-TS Proof of Unbiased Estimate . . . . . . . . . . . . . . . . . . . . . . . . 125 A.4 UES Upper Bound Property . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 A.5 TONIC – Selectivity-Aware Branching . . . . . . . . . . . . . . . . . . . . . 128 A.6 TONIC – Sequences of Query Execution . . . . . . . . . . . . . . . . . . . 129

Content assist is one of the most powerful features in integrated development environments (IDE). While a lot of research papers exist on content assist for software programming languages (SPL), hardware description languages (HDL) aren’t covered at all. In this thesis, we improve content assist for SystemVerilog, one of the most widely used HDL, by using different ordering strategies and comparing them to each other. In the end, 6 different strategies are kept: two based on frequencies, one on the usage of the content assist, one on the name of the variable, one on the type of the variable, and one on the distance from their declaration to the cursor position. We test our implementation in 3 different open-source projects well-known and used by the SystemVerilog community: OpenTitan, SweRV, and riscv-dv. We achieve having the expected entry in the top 5 in more than 40% of cases with no prefix and up to 66% of cases with 1 character already typed. / Automatisk komplettering är en av de mest kraftfulla funktionerna i integrerade utvecklingsmiljöer (integrated development environments, IDE). Även om det finns många forskningsartiklar om automatisk komplettering för mjukvaruprogrammeringsspråk (software programming languages, SPL), täcks inte hårdvarubeskrivningsspråk (hardware description language, HDL) alls. I det här examensarbetet förbättras innehållshjälp för SystemVerilog, en av de mest använda HDL:erna, genom att använda olika ordningsstrategier och jämföra dem med varandra. Slutligen behålls 6 olika strategier: två baserade på frekvenser, en baserad på användningen av automatisk komplettering, en baserad på variabelns namn, en baserad på variabelns typ och en baserad på avståndet från deras deklaration till markörens position. Implementeringen testas i 3 olika open source-projekt som är välkända och används av SystemVerilog-användarna: OpenTitan, SweRV och riscvdv. Implementeringen föreslog den förväntade termen bland de fem första förslagen i 40% av fallen där inget prefix var givet och i 66% av fallen när ett tecken var givet

[pt] Tradicionalmente, em indústrias de produção de peças discretas, no nível tático do planejamento da produção, é calculado o plano mestre de produção (Master Production Scheduling – MPS), que estabelece a quantidade de cada bem a ser produzida por período. Com o MPS em mãos, a necessidade de matéria-prima é levantada e o requerimento de material é realizado levandose em consideração o lead time de chegada das peças, que está relacionado com o modal de transporte previamente definido pela empresa. Mais próximo da operação, o sequenciamento dos jobs é feito com o objetivo de atender ao planejamento do MPS. Normalmente, esses quatro problemas - definição do modal de transporte, elaboração do plano mestre de produção, definição do momento de compra de materiais e sequenciamento da produção - são tratados em momentos diferentes e, muitas vezes, de forma determinística. Neste trabalho é avaliado o impacto financeiro e operacional de realizar o planejamento de forma determinística e segregada. Em particular, avaliase: (i) o impacto da estocasticidade e co-otimização do planejamento da produção e das decisões de compra e (ii) a viabilidade do sequenciamento. Para (i) é proposto um modelo de otimização estocástica de dois estágios que co-otimiza as decisões de volume de produção, momentos de compra e modal de transporte. Para (ii) restrições de sequenciamento de jobs são adicionadas através de uma heurística e de um modelo de programação matemática. Avaliações empíricas são feitas por meio de dois experimentos numéricos com dados realistas de uma empresa do setor automobilístico. Para (i) observamos uma redução de custo de 7 por cento na operação para o ano de 2018 (ano do planejamento) e cerca de 3,5 por cento para 5000 cenários simulados (out-ofsample), comparando o modelo de dois estágios proposto com o procedimento normalmente adotado na indústria. Para (ii) também observamos uma redução de 8 por cento no custo de operação de 2018, e de 9,6 por cento para 50 cenários simulados (outof- sample), em relação ao modelo proposto em (i) e 13 por cento no custo de operação de 2018 e 15,6 por cento para 50 cenários simulados (out-of-sample), em comparação com o modelo típico da indústria. / [en] Traditionally, in discrete manufacturing industries, at the tactical level of production planning, the master production scheduling (MPS) is calculated, which establishes the quantity of each good to be produced per period. With the MPS in hand, the need for raw material is raised and the material requirement is carried out taking into account the lead time arrival of the parts, which is related to the transport mode previously defined by the company. Closer to the operation, the jobs scheduling is done with the purpose of meeting MPS planning. Typically, these four problems - definition of the transportation mode, preparation of master production scheduling, definition of the time to purchase materials and job scheduling - are dealt with at different times and often in a deterministic way. In this work we evaluate the financial and operational impact of carrying out the planning in a deterministic and segregated way. In particular, we assess: (i) the impact of stochasticity and co-optimization of production planning and purchasing decisions and (ii) the feasibility of job scheduling. For (i) a two-stage stochastic optimization model is proposed that co-optimizes production volume decisions, purchase moments and transportation mode. For (ii) sequencing constraints of jobs are added through a heuristic and a mathematical programming model. Empirical assessments are made through two numerical experiments with realistic data from a discrete manufacturing company. For (i) we observed 7 percent cost reduction in the operation for the year 2018 (planning year) and approximately 3.5 percent for 5000 simulated scenarios (out-of-sample), comparing the proposed two-stage model with the procedure typically adopted in the industry. For (ii) we also observed a reduction of 8 percent in the 2018 operation cost, and 9.6 percent for 50 simulated scenarios (out-of-sample), in relation to the model proposed in (i) and 13 percent in the 2018 operation cost and 15.6 percent for 50 simulated scenarios (out-of-sample), compared to the typical industry model.

[pt] A célula solar de banda intermediária (IBSC) é um dispositivo de terceira geração alternativo à célula solar de junção única e permite atingir maior eficiência mantendo a simplicidade de ter apenas uma junção pn, garantindo baixo custo e baixa complexidade de fabricação. Nesta tese, um extenso trabalho experimental é apresentado, utilizando as técnicas de microscopia de força atômica, microscopia eletrônica de transmissão, catodoluminescência e fotoluminescência, além de extenso trabalho teórico baseado em simulações realizadas com os programas nextnano e SCAPS. Através dos dados obtidos, é discutida a escolha do InGaP para a matriz da célula solar e do InAs para os pontos quânticos; a inclusão das field damping layers, que minimizam o efeito negativo do campo elétrico sobre os pontos quânticos; o desordenamento do InGaP bulk; como pontos quânticos pequenos e com cap layers de menor espessura alteram a tendência de ordenamento das camadas subsequentes de InGaP; a inclusão de uma camada de GaP para garantir a qualidade das interfaces durante o crescimento da estrutura; e a otimização dos pontos quânticos para atingir a energia ideal teórica para a banda intermediária. Cinco estruturas completas de células solares de referência e de banda intermediária baseadas nas discussões apresentadas são então propostas para crescimento futuro. Estas estruturas de IBSC devem apresentar figuras de mérito interessantes, como VOC entre 1,32 eV e 1,44 eV (1; 2), aumento entre 5 por cento e 50 por cento na ISC (3) e baixos efeitos resistivos, garantindo FF alto e eficiências superiores à das células solares de referência. / [en] The intermediate band solar cell (IBSC), an alternative to the single junction solar cell, is a third generation device that achieves greater efficiency while maintaining the simplicity of having only one pn junction, guaranteeing low cost and low complexity to manufacture. In this thesis, an extensive experimental work is presented, using atomic force microscopy, transmission electron microscopy, cathodoluminescence and photoluminescence techniques, in addition to an extensive theoretical work based in simulations performed with nextnano and SCAPS softwares. Through the obtained data, the choice of InGaP for the solar cell matrix and InAs for the quantum dots; the inclusion of field damping layers to minimize the negative effect of the electric field on the quantum dots; the disordering of bulk InGaP; the way small quantum dots with thinner cap layers alter the ordering tendency of subsequent layers of InGaP; the inclusion of a GaP layer to ensure the interfaces’ quality during the structure s growth; and the quantum dots optimization to reach the intermediate band ideal theoretical energy are discussed. Five complete structures for reference and intermediate band solar cells based in the presented discussions are then proposed for future growth. These IBSC structures should present interesting figures of merit, such as a VOC ranging between 1,32 eV and 1,44 eV (1; 2), an increase between 5 per cent and 50 per cent in ISC (3) and low resistance effects, ensuring a high FF and efficiencies superior to the reference solar cells.

Querying and efficiently analyzing complex data is required to gain valuable business insights, to support machine learning applications, and to make up-to-date information available. Therefore, this thesis investigates opportunities and challenges of selecting the most efficient execution strategy for analytical queries. These challenges include hard-to-capture data characteristics such as skew and correlation, the support of arbitrary data types, and the optimization time overhead of complex queries. Existing approaches often rely on optimistic assumptions about the data distribution, which can result in significant response time delays when these assumptions are not met. On the contrary, we focus on robust query optimization, emphasizing consistent query performance and applicability. Our presentation follows the general select-project-join query pattern, representing the fundamental stages of analytical query processing. To support arbitrary data types and complex filter expressions in the select stage, a novel sampling-based selectivity estimator is developed. Our approach exploits information from filter subexpressions and estimates correlations that are not captured by existing sampling-based methods. We demonstrate improved estimation accuracy and query execution time. Further, to minimize the runtime overhead of sampling, we propose new techniques that exploit access patterns and auxiliary database objects such as indices. For the join stage, we introduce a robust optimization approach by developing an upper-bound join enumeration strategy that connects accurate filter selectivity estimates –e.g., using our sampling-based approach– to join ordering. We demonstrate that join orders based on our upper-bound join ordering strategy achieve more consistent performance and faster workload execution on state-of-the-art database systems. However, besides identifying good logical join orders, it is crucial to determine appropriate physical join operators before query plan execution. To understand the importance of fine-grained physical operator selections, we exhaustively execute fixed join orders with all possible operator combinations. This analysis reveals that none of the investigated query optimizers fully reaches the potential of optimal operator decisions. Based on these insights and to achieve fine-grained operator selections for the previously determined join orders, the thesis presents a lightweight learning-based physical execution plan refinement component called. We show that this refinement component consistently outperforms existing approaches for physical operator selection while enabling a novel two-stage optimizer design. We conclude the thesis by providing a framework for the two-stage optimizer design that allows users to modify, replicate, and further analyze the concepts discussed throughout this thesis.:1 INTRODUCTION 1.1 Analytical Query Processing . . . . . . . . . . . . . . . . . . . 12 1.2 Select-Project-Join Queries . . . . . . . . . . . . . . . . . . . 13 1.3 Basics of SPJ Query Optimization . . . . . . . . . . . . . . . . . 14 1.3.1 Plan Enumeration . . . . . . . . . . . . . . . . . . . . . . . . 14 1.3.2 Cost Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.3.3 Cardinality Estimation . . . . . . . . . . . . . . . . . . . . . 15 1.4 Robust SPJ Query Optimization . . . . . . . . . . . . . . . . . . 16 1.4.1 Tail Latency Root Cause Analysis . . . . . . . . . . . . . . . . 17 1.4.2 Tenets of Robust Query Optimization . . . . . . . . . . . . . . 19 1.5 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.6 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2 SELECT (-PROJECT) STAGE 2.1 Sampling for Selectivity Estimation . . . . . . . . . . . . . . . 24 2.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2.1 Combined Selectivity Estimation (CSE) . . . . . . . . . . . . . 29 2.2.2 Kernel Density Estimator . . . . . . . . . . . . . . . . . . . . 31 2.2.3 Machine Learning . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3 Beta Estimator for 0-Tuple-Situations . . . . . . . . . . . . . . 33 2.3.1 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3.2 Beta Distribution in Non-0-TS . . . . . . . . . . . . . . . . . 35 2.3.3 Parameter Estimation in 0-TS . . . . . . . . . . . . . . . . . . 37 2.3.4 Selectivity Estimation and Predicate Ordering . . . . . . . . . 39 2.3.5 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.4 Customized Sampling Techniques . . . . . . . . . . . . . . . . . . 53 2.4.1 Focused Sampling . . . . . . . . . . . . . . . . . . . . . . . . 54 2.4.2 Conditional Sampling . . . . . . . . . . . . . . . . . . . . . . 56 2.4.3 Zone Pruning . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.4.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3 JOIN STAGE: LOGICAL ENUMERATION 3.1 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.1.1 Point Estimates . . . . . . . . . . . . . . . . . . . . . . . . 63 3.1.2 Join Cardinality Upper Bound . . . . . . . . . . . . . . . . . . 64 3.2 Upper Bound Join Enumeration with Synopsis (UES) . . . . . . . . . 66 3.2.1 U-Block: Simple Upper Bound for Joins . . . . . . . . . . . . . 67 3.2.2 E-Block: Customized Enumeration Scheme . . . . . . . . . . . . . 68 3.2.3 UES Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.3.1 General Performance . . . . . . . . . . . . . . . . . . . . . . 72 3.3.2 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4 JOIN STAGE: PHYSICAL OPERATOR SELECTION 4.1 Operator Selection vs Join Ordering . . . . . . . . . . . . . . . 77 4.2 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.2.1 Adaptive Query Processing . . . . . . . . . . . . . . . . . . . 80 4.2.2 Bandit Optimizer (Bao) . . . . . . . . . . . . . . . . . . . . . 81 4.3 TONIC: Learned Physical Join Operator Selection . . . . . . . . . 82 4.3.1 Query Execution Plan Synopsis (QEP-S) . . . . . . . . . . . . . 83 4.3.2 QEP-S Life-Cycle . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3.3 QEP-S Design Considerations . . . . . . . . . . . . . . . . . . 87 4.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.4.1 Performance Factors . . . . . . . . . . . . . . . . . . . . . . 90 4.4.2 Rate of Improvement . . . . . . . . . . . . . . . . . . . . . . 92 4.4.3 Data Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.4.4 TONIC - Runtime Traits . . . . . . . . . . . . . . . . . . . . . 97 4.4.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 5 TWO-STAGE OPTIMIZER FRAMEWORK 5.1 Upper-Bound-Driven Join Ordering Component . . . . . . . . . . . . 101 5.2 Physical Operator Selection Component . . . . . . . . . . . . . . 103 5.3 Example Query Optimization . . . . . . . . . . . . . . . . . . . . 103 6 CONCLUSION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 BIBLIOGRAPHY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . 117 LIST OF TABLES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121 A APPENDIX A.1 Basics of Query Execution . . . . . . . . . . . . . . . . . . . . 123 A.2 Why Q? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 A.3 0-TS Proof of Unbiased Estimate . . . . . . . . . . . . . . . . . 125 A.4 UES Upper Bound Property . . . . . . . . . . . . . . . . . . . . . 127 A.5 TONIC – Selectivity-Aware Branching . . . . . . . . . . . . . . . 128 A.6 TONIC – Sequences of Query Execution . . . . . . . . . . . . . . . 129

No description available.