最新未读
FastScan快速PQ扫描论文阅读笔记 Cache locality is not enough high-performance nearest neighbor search with product quantization fast scan论文简介Cache locality is not enough high-performance nearest neighbor search with product quantization fast scan 是一篇发表于 VLDB2015 的经典论文。
主要贡献1、提出了一个通过寄存器 LUTs 代替 mem LUTs 来加速 PQ 查表的设计，并通过 SIMD 加速优化
论文内容1. 相关工作：PQ 及 IVFPQ1.1. Product Quantization量化器的构建思路：
PQ 的核心压缩思想是让距离 向量 x 最近的数据集特征向量 c 代替 x 。如下图：
q 是一个映射函数，它将一个 实数域的d 维向量映射到一个候选集 C 中，对于任何一个输入向量 x ，它都能跟给出一个对应的映射 label ，也就是某个质心 ci 代表 x 。
有了上面的形式化定义，我们还需要思考这个函数具体怎么设计，因此有最简单的映射函数为：
这里 ||x - ci|| 指的是向量 x 与 ci 之间的欧几里得范数，也就是欧氏距离。q(x) 也就是一个让距离最小的函数。
因此，一 ...
前言笔者在前几天的一次面试中被面试官问到了一个很发散的问题，Java 新建线程启动一次 IO 都做了什么？
这个问题想简单的话，两三句话就说完了。但是这是我们展示自己知识体系的好机会，加上我认为当时自己的回答不太健全，所以我们从头捋顺一下相关知识点，将它们串联起来。
本文阅读的 java 源码为 jdk-23.0.2 ，版本较新，可能会涉及新版本特性。和老版本 1.8 的源码布局稍有不同。这是我们选择的 openjdk 源码仓库：
https://github.com/openjdk/jdk/releases/tag/jdk-23%2B2
java源码的目录为：
jdk/src/java.base/share/classes/java
，这里存放了很多重要的基础包。
1、启动一次 IO ，都做了什么？1.1 JAVA 的 IO 工具类要确定都做了什么，我们首先要限定我们IO方法的具体调用路径。
众所周知， java 的 IO 分为 同步IO 和 异步IO 两种。 java.io 包中为我们提供了 同步IO 工具，而 java.nio ...
论文简介High-Dimensional Approximate Nearest Neighbor Search with Reliable and Efficient Distance Comparison Operations 是一片发表于 SIGMOD 2023 的论文。
论文贡献1、论文通过 “是否更新候选集“ 为指标，将 相似度计算DCO 分为了两类，能够更新候选集的为 positive ，否则为 negative 。通过实验论证了 HNSW 、 IVF 、 IVF-PQ 中大量 DCO 都是无效的 。
2、论文提出了动态随机投影 ADSampling 用于替换传统的 FDScanning 也就是 DCO ，并且几乎没有精度损失，论文将其称为 AKNN+ 。
3、在 HNSW+ 和 IVF+ 上 ，论文通过一个缓存友好的存储布局进一步优化了性能，将其命名为 HNSW++ 和 IVF++ 。
主要内容1、AKNN Algorithms and Their DCOsDCOs 指的就是相似度计算消耗。这章节比较简单，主要内容可以用下面的图来概括：
简单来说，在大部分索引中，大部分 ...
论文简介Similarity Search in the Blink of an Eye with Compressed Indices 是一篇 Intel Labs 发表于 2023 年 VLDB 的论文。
论文贡献1、提出了一种新的压缩算法，名为 Locally-adaptive Vector Quantization (LVQ)， LVQ 是在 标量量化 Scalar quantization 的基础上进行局部优化的压缩算法，通过更低的压缩率、实现了更少的精度损失，并提供了两级压缩的概念以应对不同级别的精度需求。
2、提供了开源实现，并将其集成于传统的图基向量索引上： https://github.com/IntelLabs/ScalableVectorSearch
3、提供了一个新的数据集： https://github.com/IntelLabs/DPR- dataset- generator
主要内容Locally-adaptive Vector Quantization (LVQ)一、前言：标量量化 Scalar quantization
标量量化是一个非常古老的有损压缩 ...
写在前面pgvector 是 PG 的向量索引插件，其最低需要 PG versuib >= 13 。虽然其性能较差，但其对 PG 生态的贡献是有意义的，下图是其 github 的官方描述：
https://github.com/pgvector/pgvector
这是一张 HNSW 索引构建时函数栈调用情况的全面火焰图：
本篇文章，我们将从 hnswbuild 出发，在阅读并理解其构建流程的基础上，学习 PostgreSQL 的相关源码。
源码阅读1、hnswbuildhnswbuild 与 hnswbuildempty 是索引构建的入口函数，下图是 hnswhandler 的定义：
hnswhandler 是 pgvector 定义的 PG 索引实现接口结构体，结构体中储存了 pgvector 实现的索引相关函数。IndexAmRoutine amroutine 是 pg 定义的 index AM 接口结构体类型， AM 的全称是 Access Method（访问或者说是存取方法），它是服务于索引引擎层的可拓展结构。索引引擎实现了一个接口，它主要的用途是从A ...
写在前面本次阅读选用了 17.0.0 版本的 PG ，
首先看一张图，在缓存命中率极低的情况下，函数栈调用大概是上面的火焰图。我们先按照这个调用栈进行阅读。
源码阅读1、ReadBuffer_commonReadBuffer_common 函数几乎是 ReadBuffer 函数的全部调用子栈，所以先从他看起：
下面的是 ReadBufferMode mode 这个 读类型参数的具体枚举类型：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263/* * ReadBuffer_common -- common logic for all ReadBuffer variants * * smgr is required, rel is optional unless using P_NEW. */static pg_attribute_always_inline BufferReadBuffer_commo ...
目标描述本教程的目标是配置一套 PostgreSql 的本地开发调试环境。
本教程所需的前置环境和目标环境为：
操作系统：Windows + WSL Ubuntu 22.04
IDE：VS Code
即，我们将在 Windows + WSL Ubuntu 22.04 的环境中，使用 VS Code IDE 进行 PostgreSql 的调试开发。
我们推荐将 PostgreSql 安装至 WSL 中，在 Windows 中使用 VSC Remote 连接 WSL 进行开发调试。因为 WSL 的配置非常简单，且能够直接在 Windows 系统上使用 Linux ，而 Linux 的环境配置非常简单；在 Windows 上使用 VSC 方便快捷，能够地减少学习 Linux 的学习成本。
配置步骤由于我们的目标不是为开源社区做贡献，而是为了解决我们的个性化问题，因此追求最新版本的 PG 可能会得不偿失（最新版本的软件往往可能会出现较大的变更，不利于初步学习。如果你有研究成果开源化的需求，可以考虑使用最新版本的 PG 源码）。
在这里我选用了 v17.0 的 PG 源码进行学习， v17.0 ...
论文简介High Dimensional Similarity Search with Satellite System Graph: Efficiency, Scalability, and Unindexed Query Compatibility 是一篇发表于 JOURNAL OF IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 2020 （TPAMI 2021）的期刊论文
@article{fu2021high, title={High dimensional similarity search with satellite system graph: Efficiency, scalability, and unindexed query compatibility}, author={Fu, Cong and Wang, Changxu and Cai, Deng}, journal={IEEE Transactions on Pattern Analysi ...
论文简介Two-stage routing with optimized guided search and greedy algorithm on proximity graph 是王梦召在2021年发表于 Knowledge-Based Systems 上的期刊文章。
Abstract
随着人们对大规模检索任务的兴趣激增，邻近图现在已成为领先的范例。现有的邻近图大多采用简单的贪心算法作为近似最近邻搜索（ANNS）的路由策略，但这会导致两个问题：路由效率低和局部最优；这是因为他们忽略了不同路由阶段的特殊要求。一般来说，路由可以分为两个阶段：远离查询的阶段（S1）和靠近查询的阶段（S2）。 S1旨在快速路由到查询附近，效率占优。而S2注重的是准确地找到结果，所以准确度是最重要的。我们为每个阶段精心设计定制的路由算法，然后将它们组合在一起形成优化引导搜索和贪心算法（TOGG）的两阶段路由。对于S1，我们提出优化的引导搜索，通过查询方向的引导快速定位查询的邻域。而对于S2，我们提出了优化的贪心算法，通过敏捷地检测显式和隐式收敛路径来全面访问查询附近的顶点。最后，通过理论和实验分析，我们证明 ...
前言当程序性能达到瓶颈时，我们可以通过多种工具对程序的性能进行分析，定位到最大的CPU耗时、IO耗时，从而对程序进行更细粒度的优化。
之前只用过 Jprofiler 对 java 进行分析，没有分析过 c++ 。由于我的 C++ 开发平台是 WSL ，与原生的 linux 内核有区别，需要额外的配置才能使用分析工具，因此写了一篇笔记来避免后续再踩坑。
C++ 的性能分析工具有很多，如：
gprof：这是一个GNU的性能分析工具，主要用于分析程序的函数调用关系，以及每个函数的运行时间等。
Valgrind：这是一个用于内存调试、内存泄漏检测以及性能分析的开源工具集。其中，Valgrind的Callgrind工具可以收集程序运行时的函数调用信息，用于性能分析。
perf：这是Linux下的一个性能分析工具，可以收集CPU使用情况、缓存命中率、分支预测错误等多种性能数据。
不同的分析工具针对的重点不同，我们可能需要同时使用多种工具进行分析。
引用：
https://www.cnblogs.com/music-liang/p/18076834
gprofgprof 通常作为 GNU B ...
