数据库索引调优技术综述

索引调优是数据库调优的重要组成部分,一直受到广泛关注.由于索引调优问题的理论复杂性和大数据时代的到来,通过DBA手动调优的方案已经无法满足现代数据库的发展需求,调优方案逐渐开始向自动化、智能化的方向发展.随着机器学习技术的发展,越来越多的索引选择方案开始引入机器学习技术,并取得了一定的研究成果.将索引调优问题的解决方案归结为一种基于搜索的调优范式,归纳了其研究内容,阐述了其面临的挑战,对调优范式内的索引配置空间的生成、索引配置的评价以及索引配置的枚举与搜索3方面的研究成果进行了归纳、总结和对比.对动态工作负载下的索引选择问题(index selection problem,ISP)所面临的新挑战进行了分析,并基于在线反馈控制回路框架对其解决方案进行梳理.讨论了索引调优工具的发展与现状,通过对现有研究的分析论述,为后来研究者提供参考和研究思路,并对索引选择方案的未来进行了展望.

APLI:一种基于持久化内存的高性能学习索引

持久化内存(Persistent Memory,PM)已成为容量有限的DRAM的最有潜力的补充或者替代品.学习索引(Learned Index,LI)作为一种感知数据分布的索引结构,在大数据集上能够以较小的内存使用量展现远优于B+树的性能而被广泛关注.最近,一些研究者尝试将学习索引部署在持久化内存中,然而现有的持久化学习索引存在读写性能次优化、结构扩展性不足、动态负载性能不统一等问题.为此,本文在深入分析了持久化内存和学习索引特性的基础上,提出了一种自适应的持久化学习索引结构APLI.APLI由两部分组成:1)高效的混合介质的持久化学习索引树(EPL-Tree),提供稳定的读写性能和结构扩展;2)轻量级的哈希表(SW-Table),用于快速感知负载变化并提升热点访问的性能.在持久化内存真实设备上的评估表明,相比现有的持久化索引结构,APLI读写性能最高分别提升3.2倍和3.3倍,而且拥有更稳定的结构扩展性能.另外,APLI能在较小的DRAM空间占用前提下,实现各种负载场景下的稳定高性能访问.

纪录片理论与“索引性”之争

“index”这个概念在中文里既可以翻译成“索引”也可以翻译成“指示”,但中文的索引和指示并不是同义的概念,索引对于影像来说是与对象的一一对应,指示则是相对符号而言的象征。尼科尔斯强调了“index”概念指示性的一面,因此将虚构影像和动画都纳入了纪录片范畴。这种片面的做法不仅导致尼科尔斯对“声音”索引性的无限夸大,同时也导致像“间接索引”这种似是而非概念的出现。这些说法和概念无论是从历史上看还是从逻辑上看,都是站不住的。

搜索引擎平台优化策略何以提升消费者福利?

本文通过构造搜索引擎平台优化策略的一般性分析框架,及与之相匹配的两阶段理论模型,考察搜索引擎平台优化策略的作用机理,探索搜索引擎平台优化策略对消费者福利及搜索引擎平台利润的影响,从而推动搜索引擎平台优化策略的有效应用。研究发现:短期来看,搜索引擎平台优化策略的排序均衡将违背消费者检索意愿,虽激励了低质量销售商参与付费位置拍卖活动,维持付费位置拍卖市场稳定性,增加搜索引擎平台利润,却损害了消费者福利;长期来看,搜索引擎平台优化策略的排序均衡将契合消费者检索意愿,激励高质量销售商最大限度吸引消费者注意力,推动消费者实施购买行为,提升消费者福利,并通过降低均衡投标金额,一定程度地激励低质量销售商持续参与付费位置拍卖活动,进而实现协调双边用户的需求。并且,搜索引擎平台优化策略的排序均衡对搜索引擎平台利润有“先降后升”的“U”型曲线的影响。产业实践案例显示,中文主流搜索引擎平台的优化策略遵循长短期效应。

ZFT索引:基于分段线性回归的学习型多维索引

传统索引方式一般是一种通用的数据结构,不特别针对数据分布和特征设计或优化其索引方式,随着数据空间维度或数据量的增加,可能会导致存储消耗大且查询效率急剧下降。针对这些问题提出ZFT索引(Z-order Fiting-tree Index),它主要分为离线和在线两个部分。离线构造部分使用Z-order曲线将多维空间中的数据点映射到一维空间中,构建线性回归模型学习映射后数据的分布与特征;在线部分完成点查询和范围查询。实验结果表明,ZFT索引的空间效率和查询效率明显优于传统的R树以及UB树,并且在范围查询和模型训练速度上都优于ZM索引。

基于改进的K-means聚类分区均匀化空间学习索引

传统空间索引的体量随数据量的增加而膨胀,查询效率较低。学习索引的体量不随数据量的增加而膨胀,同时避免了层级比较查询,性能优异。将学习索引应用于空间索引存在2个难点:一是选取合适的降维方法实现空间数据的排序;二是对降维后数据序列进行有效的简化分布计算,使其易于拟合。基于此,提出了一种网格混合聚类分区学习索引(grid-ml),用z曲线进行降维,用双层网格结构优化查询策略,用改进的K-means聚类算法进行数据分区,实现数据分布均匀化。对比实验发现,grid-ml构建速度快、存储空间小、查询效率高,较传统空间索引优势显著。

生成式人工智能驱动的索引编制方法及其在学术规范和评价中的应用

为提高索引编制的效率与质量,应用生成式人工智能的实验方法,针对传统基于规则和概率的索引软件的不足,提出了运用生成式人工智能RAG技术编制索引的方案,即以期刊的卷为单位,利用大语言模型基于论文摘要中的索引词对全文进行主题标引。设计了论文摘要索引数据库系统,能够实现基于大模型海量知识涌现和推理的文本概念抽取和主题标引,从摘要中提取关键信息和新兴知识。探讨了将索引、论文摘要、学术规范与评价关联起来的实际方式,展示了生成式人工智能在索引学和索引编制领域的潜在价值,能够为生成式人工智能技术在图书情报领域的应用推广提供参考。

基于分区层次图的海量高维数据学习索引构建方法

学习索引是破解海量高维数据近似最近邻搜索问题的关键。然而,现有学习索引技术结果仅局限于单个分区中,且依赖于近邻图的构建。随着数据维度和规模的增长,索引难以对分区边界数据进行精确判断,并且构建时间复杂度增大,可扩展性难以保障。针对上述问题,提出了基于分区层次图的学习索引方法PBO-HNSW。该方法对分区边界数据进行重新分配,并行构建分布式图索引结构,从而有效应对近似最近邻搜索问题所面临的挑战。实验结果表明,该方法能够在百万级海量高维数据上实现毫秒级的索引构建。当召回率为0.93时,PBO-HNSW方法构建时间仅为基线方法的36.4%。

O-OFDM索引调制的分步优化信号映射方法

【目的】采用随机映射以及传统星座图会导致已有光正交频分复用(O-OFDM)-索引调制(IM)系统的误码率(BER)性能无法达到最优,因此,文章基于激活子载波的最优选择以及星座图的最优旋转提出了一种分步优化信号映射方法,旨在通过分步优化信号映射方法实现O-OFDM-IM系统BER性能的改善。【方法】在发射端,首先依据信道状态信息,采用信道范数最大化准则选择最优激活子载波组合;其次,利用信道状态信息,以∂=0.5°为步长,采用穷举搜索算法得到最优星座图;之后,将通过旋转获得的最优星座图加载到激活的子载波上进行信号传输;最后在接收端利用最大似然(ML)检测算法对原始信号进行恢复来实现最小的系统错误概率。【结果】仿真表明,在强湍流、BER=10-4和调制阶数为16的条件下,采用文章所提方法后,(4,2)O-OFDM-IM系统的信噪比(SNR)降低了约1.45 dB。此外,随着湍流强度的增大,BER性能的改善更明显。如,8正交幅度(QAM)、BER=10-4时,(4,2)O-OFDM-IM系统的SNR在强湍流下降低了约1.35 dB,在弱湍流下则降低了1.2 dB。【结论】由仿真结果可知,在已知信道状态信息的前提下,文章所提方法可有效改善湍流信道下系统的BER性能。

SEGY地震数据自适应快速索引处理

随着油气田勘探技术的不断进步,勘探精度越来越高,产生物探地震成果数据量也越来越大。一个工区成果动辄几个TB甚至几十个TB,而这些成果数据中90%以上为SEGY格式地震数据体、如果采用常规方法对文件依次遍历,耗费资源且效率低,结合地震数据体的特性建立相匹配的索引将极大的提高数据遍历及提取的效率与速度。通过分析国内外地震数据管理现状和发展趋势,结合油田地震资料管理现状,设计和研发一套地震SEGY数据体自适应快速索引生成技术,已实现工业化应用。

面向科技文献多维语义组织的混合倒排索引构建方法

[目的/意义]为满足科研人员对科技文献内部细粒度语义信息进行高效查询的迫切需求,前期研究提出了面向科技文献的多维语义索引体系,然而基于HashMap的常见倒排索引会导致查询效率低下。本文旨在通过面向不同维度语义特征建立混合倒排索引,以改进语义查询性能。[方法/过程]本文以Treap、B+树等多种数据结构探索适合不同语义维度的倒排索引构建方法,并将其组合形成多种适用于科技文献多维语义组织的混合倒排索引构建方法,并通过对比实验,在排序查询和布尔查询条件下分析验证不同类型倒排索引构建方法的查询性能。[结果/结论]实验结果表明,组合形成的8种混合倒排索引构建方法中,表2所示的C3(HHHB)被证明在排序查询条件下具有最高的效率,而C4(TTTB)则在布尔查询条件下被证明最为高效。本文的方法能有效解决单一索引结构导致的查询效率问题。

面向主从区块链的多级索引构建方法

主从区块链是一种面向领域的、采用高效密码学原理进行大数据可信化通信及存储的新型信息处理技术.随着领域数据规模的指数级增长,现有主从区块链系统存在的查询效率低、溯源时间长等问题愈发严重.针对这些问题,提出一种面向主从区块链的多级索引构建方法(multi-level index construction method for master-slave blockchain,MSMLI).首先,MSMLI引入权重矩阵,基于主链结构将整个主从区块链进行分片,并对各个分片进行权重赋值;其次,针对每个分片内的主区块链,提出基于跳跃一致性哈希的主链索引构建方法(master chain index construction method based on jump consistent Hash,JHMI),输入节点关键值和索引槽位数量,输出主链索引;最后,引入布隆过滤器,改进基于列的选择函数,对各个主区块对应的从属区块链构建2级复合索引.在3种约束条件和2类数据集上的实验结果表明,MSMLI对比现有方法,平均能够缩减9.28%的索引构建时间,提升12.07%的查询效率,同时降低24.4%的内存开销.

面向持久化键值数据库的自适应热点感知哈希索引

针对现有键值数据库存储系统缺乏热点意识,导致系统在高度倾斜的工作负载下性能较差且不可靠,提出了一种自适应热点感知哈希索引模型,该模型基于key值摘要信息实现了一个高性能哈希表。首先,利用key的摘要信息代替key值,压缩key的存储空间,优化哈希表中桶的数据结构;其次,利用CPU的数据级并行技术以及CPU cache line,对哈希表的探查操作进行优化;最后,为解决摘要信息导致key值无法精准比较,需要额外磁盘I/O的问题,设计了一种自适应key值调度算法,该算法根据当前可用内存大小、哈希索引负载以及访问热点情况动态地调整key值的存储位置。在YCSB仿真数据集上进行了实验,实验表明,相较于最先进的哈希表,自适应热点感知哈希索引在相同内存使用率的情况下,将速度提升至1.2倍。

联合RIS子块与接收天线的索引调制方案性能分析

利用大量无源反射器件设计的可重构智能表面(RIS),具有拓展无线通信覆盖范围、降低系统成本/功耗和提升未来通信系统性能的优势;而索引调制(IM),通过激活通信资源的子集可实现信息的隐性传输,有望为无线通信带来更高的频谱效率和能量效率,因此,为进一步提升未来无线通信系统的性能,该论文融合RIS与IM技术,提出一种联合RIS子块与接收天线的IM方案。在该方案中,按照相邻原则,将RIS反射元件分割为若干子块,进而利用RIS子块索引与接收天线索引同时实现附加信息传递,即对待传输比特序列,将其分割为三部分,其中第一部比特被调制为星座符号,第二部分用于指示RIS子块划分,第三部分用于指示接收天线索引;在此基础上,根据最大似然(ML)检测的成对错误概率(PEP)解析形式,分四种情况,从理论上推导出对应的矩母函数(MGF),得到无条件PEP的解析表达式,最后得到该方案ML检测的平均误码率(ABER)性能上界。仿真结果表明,与现有RIS辅助的IM方案相比,无须增加额外频谱资源,所提方案的系统可达速率和系统差错性能方面均具有一定优势;同时,验证了ML检测的ABER上界具备严格一致性。

基于CRF的分区倒排索引压缩算法

倒排索引是大型搜索引擎的核心数据结构,本质是倒排列表中整数序列的集合。倒排索引压缩可以有效减少倒排索引所占空间,提高对关键词的检索效率。本文提出的基于条件随机场(CRF)的分区倒排索引压缩算法主要关注域值分区的分区方式。该算法对序列进行预分区,并且使用条件随机场对预分区进行标注并重组,有效减少了压缩时间。根据分区类型,该算法使用相应的编码方式,进一步减少了压缩后的空间占用。与其他倒排索引压缩算法进行对比实验分析,结果表明本文算法在压缩率上超过目前一些域值分区的算法,并且在解压时间上与其他域值分区算法相当。该算法在时间和空间上取得了较好的平衡。

一种新型高效全文检索引擎的设计

为了改善常规存储方式模糊查询性能较低的问题,提出一种针对大文本文档数据的高效模糊查询方法。通过对文档建立倒排索引,将索引以及部分文档信息提取到内存中以降低磁盘输入和输出(Input/Output,I/O)。根据内存中的倒排索引和数据库中主键形成的映射查询数据,然后通过相关度算法对这些数据进行排序,并以字典树作为搜索提示,实现高效的全文检索。实验结果表明:与ElasticSearch使用相同词集时,随着测试数据量的变化,所设计的全文检索引擎的查询效率是ElasticSearch效率的80~1200倍,其效率优势随着数据量增加呈现反比例关系变化,并且在17919条文档数据下,其内存占用不超过2.5 GB,适合用于海量文档数据检索。

双模三维索引调制差分混沌移位键控系统的设计及性能分析

针对传统差分混沌移位键控系统速率低、误码性能差的问题,提出了一种双模三维索引调制差分混沌移位键控系统。该系统利用时隙、正交码和顺序索引,在选中与未选中的时隙上均传输信息比特。在接收端,通过采用降噪技术,减小了噪声的方差,提升了系统误码性能。推导了在加性白高斯噪声信道和多径瑞利衰落信道下的比特差错率公式。仿真结果显示,与相似的混沌键控系统相比,所提系统具备更高的数据速率和更为优越的误码性能。

基于可逆元胞自动机加密的扩展码索引调制方案

针对直接序列扩频系统伪随机(Pseudo Noise,PN)码资源有限且码索引调制系统误码率性能下降的问题,提出了一种基于可逆的初等元胞自动机加密的扩展码索引调制方案。首先,针对PN码资源有限的问题,提出使用混沌规则的初等元胞自动机对PN码进行迭代的方案,从而实现扩展PN码的目的;其次,针对码索引调制误码率性能下降的问题,提出了一种可逆元胞自动机加密的码索引调制方案,在发射端,把信息比特切割成调制比特和映射比特,并分别映射为调制符号和扩频码索引,使用对应索引的扩频码对同相分量进行扩频,同时使用可逆元胞自动机对映射比特进行加密,加密后的映射比特为调制符号的正交分量选取对应索引的扩频码进行扩频。仿真与分析结果表明,在相同频谱效率条件下,在加性高斯白噪声信道中,当误码率为10-5时,扩展码索引调制方案的误码率性能优于码索引调制和广义码索引调制方案约2~4 dB,优于非正交码移键控码索引调制方案约0.5 dB。

搜索引擎、人工智能与行政负担

学习成本是行政负担的重要维度之一,但是相关研究并不多。搜索引擎是公民找政府办事的主要入口之一,本文聚焦搜索引擎如何影响政民互动中的学习成本。研究显示,商业开发和政府提供的搜索引擎服务降低了公民与政府打交道的学习成本,但是也因为设计缺陷和过度商业化而增加行政负担。进一步的分析发现,随着以大语言模型为代表的生成式人工智能在搜索引擎中的深度应用,政民互动的学习成本会持续降低,并会带来合规成本和心理成本的下降。本文讨论了新一代人工智能技术对行政负担,特别是学习成本的潜在影响,并提出了对策建议和未来研究方向。

基于多级索引表的金融业务数据库精准查询方法

为提升金融业务数据库查询精准度和效率,设计了一种基于多级索引表的金融业务数据库精准查询方法。首先,构建多级索引的逻辑结构,设计多级索引表构建过程;其次,进行金融业务数据特征融合,为金融业务数据查询准备好数据条件;最后,设计金融业务数据库精准查询算法,完成基于多级索引表的金融业务数据库精准查询方法设计的全过程。实验结果表明:设计方法的金融业务数据库查询精准度均在90%以上,最高可达到98%,而且查询所需时间最短仅为5.25 s。本设计方法的适用性极强,具有较好的应用前景,以期能够为金融业务数据的精准高效查询提供参考借鉴。